## Testing new algorithm for factoring

Expand Messages
• Hi all, I m currently testing out a new algorithm for finding factors of composite Mersenne numbers. Two numbers that I am testing the algorithm on are 2^83 -1
Message 1 of 8 , Jun 26, 2004
• 0 Attachment
Hi all,

I'm currently testing out a new algorithm for finding factors of composite
Mersenne numbers.

Two numbers that I am testing the algorithm on are 2^83 -1 and 2^47777783 -1.

Is there anyone that has the complete set of factors for 2^83 - 1and is
there anyone that can confirm that factors for 2^47777783 -1 include
2*47777783 + 1 and 24*47777783 - 1. If so can you get back to me.

Currently I'm only able to test about one factor a second on my 2.8GHz
Pentium, so next I need to be able to sieve numbers before I put them
through the software.

Also, if anyone has any idea about how long it should take to test a
potential divisor for numbers at the 2^47777783 -1 range then I would be
interested to hear.

Regards,

Kevin.
• ... The first I can answer instantly. The latter takes time. According to the cunningham tables, of which I keep copies on my web site, the factors of 2^83-1
Message 2 of 8 , Jun 26, 2004
• 0 Attachment
> Is there anyone that has the complete set of factors for 2^83
> - 1and is
> there anyone that can confirm that factors for 2^47777783 -1 include
> 2*47777783 + 1 and 24*47777783 - 1. If so can you get back to me.

The first I can answer instantly. The latter takes time.

According to the cunningham tables, of which I keep copies on my web site, the factors of 2^83-1 are 167 and 57912614113275649087721

Paul
• ... Using PARI/GP on a 450 MHZ Pentium II: ? e=47777783;cnt=10000;x=gettime;for(a=1,cnt,if(Mod(2,2*a*e+1)^e-1==0, print(2*a, * ,e, +1 divides 2^ ,e, -1 )));
Message 3 of 8 , Jun 26, 2004
• 0 Attachment
> Is there anyone that has the complete set of factors for 2^83 - 1and is
> there anyone that can confirm that factors for 2^47777783 -1 include
> 2*47777783 + 1 and 24*47777783 - 1. If so can you get back to me.
>
> Currently I'm only able to test about one factor a second on my 2.8GHz
> Pentium, so next I need to be able to sieve numbers before I put them
> through the software.
>
> Also, if anyone has any idea about how long it should take to test a
> potential divisor for numbers at the 2^47777783 -1 range then I would be
> interested to hear.

Using PARI/GP on a 450 MHZ Pentium II:

? e=47777783;cnt=10000;x=gettime;for(a=1,cnt,if(Mod(2,2*a*e+1)^e-1==0,
print(2*a,"*",e,"+1 divides 2^",e,"-1")));
print("Elapsed time to test ",cnt," numbers is == ",
gettime," milliseconds")
2*47777783+1 divides 2^47777783-1
24*47777783+1 divides 2^47777783-1
Elapsed time to test 10000 numbers is == 795 milliseconds

So the factors for 2^47777783-1 include both 2*47777783+1 and 24*47777783+1
and it takes about 80 microseconds to test each "small" potential divisor.
• Saturday, June 26, 2004 9:07 AM [GMT+1=CET], ... select(mod(2^47777783, 2*k*47777783+1)=1, k, 1, 1000000) ==== [1, 12] (67.5 s with DERIVE on a P4-2800Mh) Its
Message 4 of 8 , Jun 26, 2004
• 0 Attachment
Saturday, June 26, 2004 9:07 AM [GMT+1=CET],
Kevin Acres <research@...> escribió:

> Hi all,
>
> I'm currently testing out a new algorithm for finding factors of
> composite Mersenne numbers.
>
> Two numbers that I am testing the algorithm on are 2^83 -1 and
> 2^47777783 -1.
>
> Is there anyone that has the complete set of factors for 2^83 - 1and
> is there anyone that can confirm that factors for 2^47777783 -1
> include 2*47777783 + 1 and 24*47777783 - 1. If so can you get back to
> me.
>
> Currently I'm only able to test about one factor a second on my 2.8GHz
> Pentium, so next I need to be able to sieve numbers before I put them
> through the software.
>
> Also, if anyone has any idea about how long it should take to test a
> potential divisor for numbers at the 2^47777783 -1 range then I would
> be interested to hear.
>
> Regards,
>
> Kevin.

select(mod(2^47777783, 2*k*47777783+1)=1, k, 1, 1000000) ====> [1, 12]

(67.5 s with DERIVE on a P4-2800Mh)

Its says, only 2*47777783 + 1 and 24*47777783 - 1 are the only factors of
2^47777783 -1, with k <= 10^6, written in the form 2*k*47777783+1.

I don't took in acount that k must be 0 or 1 (mod 4).

Saludos,

Ignacio Larrosa Cañestro
A Coruña (España)
ilarrosa@...
• Hi Jack, Thanks for the response. I know that there is a technique for finding small divisors in a very short time, given that they exist. I ve seen the
Message 5 of 8 , Jun 26, 2004
• 0 Attachment
Hi Jack,

Thanks for the response. I know that there is a technique for finding
small divisors in a very short time, given that they exist. I've seen the
algorithm at http://www.mersenne.org/math.htm .

Currently, I'm doing the full 47,000,000 bit arithmetic rather than take
the short cut at the moment.

I suppose what I was really trying to find out was a good estimate of the
time taken to do a full division on such a large number.

Kevin.

At 08:43 PM 26/06/2004, Jack Brennen wrote:
> > Is there anyone that has the complete set of factors for 2^83 - 1and is
> > there anyone that can confirm that factors for 2^47777783 -1 include
> > 2*47777783 + 1 and 24*47777783 - 1. If so can you get back to me.
> >
> > Currently I'm only able to test about one factor a second on my 2.8GHz
> > Pentium, so next I need to be able to sieve numbers before I put them
> > through the software.
> >
> > Also, if anyone has any idea about how long it should take to test a
> > potential divisor for numbers at the 2^47777783 -1 range then I would be
> > interested to hear.
>
>Using PARI/GP on a 450 MHZ Pentium II:
>
>? e=47777783;cnt=10000;x=gettime;for(a=1,cnt,if(Mod(2,2*a*e+1)^e-1==0,
> print(2*a,"*",e,"+1 divides 2^",e,"-1")));
> print("Elapsed time to test ",cnt," numbers is == ",
> gettime," milliseconds")
>2*47777783+1 divides 2^47777783-1
>24*47777783+1 divides 2^47777783-1
>Elapsed time to test 10000 numbers is == 795 milliseconds
>
>So the factors for 2^47777783-1 include both 2*47777783+1 and 24*47777783+1
>and it takes about 80 microseconds to test each "small" potential divisor.
>
>
>
>
>
>
>
>Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
>The Prime Pages : http://www.primepages.org/
>
>
>
>
>
>
• Saturday, June 26, 2004 1:30 PM [GMT+1=CET], ... It must be 24*47777783 + 1, obviously. It s a persistent typo ... ... Also for k = 4*909957,
Message 6 of 8 , Jun 26, 2004
• 0 Attachment
Saturday, June 26, 2004 1:30 PM [GMT+1=CET],
Ignacio Larrosa Cañestro <ilarrosa@...> escribió:

> Saturday, June 26, 2004 9:07 AM [GMT+1=CET],
> Kevin Acres <research@...> escribió:
>
>> Hi all,
>>
>> I'm currently testing out a new algorithm for finding factors of
>> composite Mersenne numbers.
>>
>> Two numbers that I am testing the algorithm on are 2^83 -1 and
>> 2^47777783 -1.
>>
>> Is there anyone that has the complete set of factors for 2^83 - 1and
>> is there anyone that can confirm that factors for 2^47777783 -1
>> include 2*47777783 + 1 and 24*47777783 - 1. If so can you get back to
>> me.
>>
>> Currently I'm only able to test about one factor a second on my
>> 2.8GHz Pentium, so next I need to be able to sieve numbers before I
>> put them through the software.
>>
>> Also, if anyone has any idea about how long it should take to test a
>> potential divisor for numbers at the 2^47777783 -1 range then I would
>> be interested to hear.
>>
>> Regards,
>>
>> Kevin.
>
> select(mod(2^47777783, 2*k*47777783+1)=1, k, 1, 1000000) ====> [1, 12]
>
> (67.5 s with DERIVE on a P4-2800Mh)
>
> Its says, only 2*47777783 + 1 and 24*47777783 - 1 are the only
> factors of 2^47777783 -1, with k <= 10^6, written in the form
> 2*k*47777783+1.

It must be 24*47777783 + 1, obviously. It's a persistent typo ...

> I don't took in acount that k must be 0 or 1 (mod 4).
>

Also for k = 4*909957, 2*4*909957*47777783 + 1 is a factor of
2^47777783 -1. No others factos with k <= 4*10^6.

Saludos,

Ignacio Larrosa Cañestro
A Coruña (España)
ilarrosa@...
• Kevin Acres wrote: I m currently testing out a new algorithm for finding factors of composite Mersenne numbers. New algorithms are welcome, of course, but any
Message 7 of 8 , Jun 26, 2004
• 0 Attachment
Kevin Acres wrote:
I'm currently testing out a new algorithm for finding factors of
composite Mersenne numbers.

New algorithms are welcome, of course, but any that are used for
finding factors of Mersenne numbers that don't take advantage of the
restricted form of Mersenne numbers in every way known is likely to be
considerably slower than existing methods.

Two numbers that I am testing the algorithm on are 2^83 -1 and
2^47777783 -1.

Others have already mentioned the factors in my data and one that
isn't (the largest of the latter Mersenne), but you (and others on the
list) might like to know that I maintain a large database of
information about all Mersenne numbers (including those with a
composite exponent). Part of the data is on my web site, but I don't
have enough web-accessible disk space for all of it, so feel free to
send me direct queries about specific numbers that aren't on the web
site.

Currently I'm only able to test about one factor a second on my
2.8GHz Pentium, so next I need to be able to sieve numbers before I
put them through the software.

Sieving is also used by the fastest known programs, notably George
Woltman's Prime95.

Also, if anyone has any idea about how long it should take to test
a potential divisor for numbers at the 2^47777783 -1 range then I
would be interested to hear.

For programs that take advantage of the form of Mersenne numbers and
the restrictions on their factors, the time for a single potential
divisor is in the microseconds on a fairly modern CPU until the
Mersenne exponent itself gets larger than 31 bits (2^31) or so and
probably a ways past that.

Ignacio Larrosa Canestro <ilarrosa@...> writes:
Also for k = 4*909957, 2*4*909957*47777783 + 1 is a factor of
2^47777783 -1. No others factos with k <= 4*10^6.

Thanks for the new factor. Was this last search restricted to trial
factors that are 1 modulo 8 ? I try to record how far trial factoring
has been done as well as any factors found.

Will

http://www.garlic.com/~wedgingt/mersenne.html
• Sunday, June 27, 2004 12:27 AM [GMT+1=CET], ... No, I search for factors equals to 1 or 7 modulo 8. Its says, for factors 2*(4*k)*47777783 + 1 2*(4*k +
Message 8 of 8 , Jun 26, 2004
• 0 Attachment
Sunday, June 27, 2004 12:27 AM [GMT+1=CET],
Will Edgington <wedgingt@...> escribió:

> Ignacio Larrosa Canestro <ilarrosa@...> writes:
> Also for k = 4*909957, 2*4*909957*47777783 + 1 is a factor of
> 2^47777783 -1. No others factos with k <= 4*10^6.
>
> Thanks for the new factor. Was this last search restricted to trial
> factors that are 1 modulo 8 ? I try to record how far trial factoring
> has been done as well as any factors found.
>
No, I search for factors equals to 1 or 7 modulo 8. Its says, for factors

2*(4*k)*47777783 + 1

2*(4*k + 1)*47777783 + 1

with k <= 10^6

Saludos,

Ignacio Larrosa Cañestro
A Coruña (España)
ilarrosa@...
Your message has been successfully submitted and would be delivered to recipients shortly.