## RE: [PrimeNumbers] Factors of mersenne numbers

Expand Messages
• Hi Harsh, I had some code to do this with Pari. See below. To get Pari, visit http://pari.math.u-bordeaux.fr/download.html Be careful copying the output. You
Message 1 of 11 , Jan 11, 2004
• 0 Attachment
Hi Harsh,
I had some code to do this with Pari. See below. To get Pari, visit

Be careful copying the output. You probably will be better off running the
code in Pari. Note
that the large factors are pseudoprimes. To "prove" them use the Pari
isprime(x) function.
Eg., the large factor in 2^197-1 is a proven prime as shown below.
(20:48) gp >
isprime(26828803997912886929710867041891989490486893845712448833)
%1 = 1

\\ Pari script mersenne.gp. Factoring mersenne type numbers b^p-d
\\ b=base, n = max prime, d=amount to subtract. Mersennes are base = 2,d=1
or 2^p-1.
mersenne(b,n,d) =
{ c=0;
forprime(x=2,n,
y = b^x-d;
f=factor(y);
v=component(f,1);
ln = length(v);
print1(b"^"x"-1 = ");
for(i=1,ln,
print1(v[i]",");
);
print()
)
}

Output
factors are seperated by commas. If the right side has only one number, then
2^p - 1 is prime.

2^2-1 = 3,
2^3-1 = 7,
2^5-1 = 31,
2^7-1 = 127,
2^11-1 = 23,89,
2^13-1= 8191,
2^17-1 = 131071,
2^19-1 = 524287,
2^23-1 = 47,178481,
2^29-1 = 233,1103,2089,
2^31-1 = 2147483647,
2^37-1 = 223,616318177,
2^41-1 = 13367,164511353,
2^43-1 = 431,9719,2099863,
2^47-1 = 2351,4513,13264529,
2^53-1 = 6361,69431,20394401,
2^59-1 = 179951,3203431780337,
2^61-1 = 2305843009213693951,
2^67-1 = 193707721,761838257287,
2^71-1 = 228479,48544121,212885833,
2^73-1 = 439,2298041,9361973132609,
2^79-1 = 2687,202029703,1113491139767,
2^83-1 = 167,57912614113275649087721,
2^89-1 = 618970019642690137449562111,
2^97-1 = 11447,13842607235828485645766393,
2^101-1 = 7432339208719,341117531003194129,
2^103-1 = 2550183799,3976656429941438590393,
2^107-1 = 162259276829213363391578010288127,
2^109-1 = 745988807,870035986098720987332873,
2^113-1 = 3391,23279,65993,1868569,1066818132868207,
2^127-1 = 170141183460469231731687303715884105727,
2^131-1 = 263,10350794431055162386718619237468234569,
2^137-1 = 32032215596496435569,5439042183600204290159,
2^139-1 = 5625767248687,123876132205208335762278423601,
2^149-1 = 86656268566282183151,8235109336690846723986161,
2^151-1 = 18121,55871,165799,2332951,7289088383388253664437433,
2^157-1 = 852133201,60726444167,1654058017289,2134387368610417,
2^163-1 = 150287,704161,110211473,27669118297,36230454570129675721,
2^167-1 = 2349023,79638304766856507377778616296087448490695649,
2^173-1 = 730753,1505447,70084436712553223,155285743288572277679887,
2^179-1 = 359,1433,1489459109360039866456940197095433721664951999121,
2^181-1 = 43441,1164193,7648337,7923871097285295625344647665764672671,
2^191-1 = 383,7068569257,39940132241,332584516519201,87274497124602996457,
2^193-1 = 13821503,61654440233248340616559,14732265321145317331353282383,
2^197-1 = 7487,26828803997912886929710867041891989490486893845712448833,
2^199-1 = 164504919713,4884164093883941177660049098586324302977543600799,
2^211-1 =
15193,60272956433838849161,3593875704495823757388199894268773153439,
2^223-1 =
18287,196687,1466449,2916841,1469495262398780123809,59624259998711612841
5063,
2^227-1 =
26986333437777017,7992177738205979626491506950867720953545660121688631,
2^229-1 =1504073,20492753,59833457464970183,
467795120187583723534280000348743236593,
2^233-1 =
1399,135607,622577,116868129879077600270344856324766260085066532853492178431,
2^239-1 = 479,1913,5737,176383,134000609,
7110008717824458123105014279253754096863768062879,
2^241-1=
22000409,160619474372352289412737508720216839225805656328990879953332340439,
2^251-1 = 503,54217,178230287214063289511,61676882198695257501367,
12070396178249893039969681,

Have Fun,
Cino
"Behavior is not for the pursuit of survival but because of it."

>From: "eharsh82" <harsh@...>
>Subject: [PrimeNumbers] Factors of mersenne numbers
>Date: Mon, 12 Jan 2004 02:09:24 -0000
>
>I am looking for all the factors of mersenne numbers under 2^256-1.
>that is 2^n-1, n from 1 to 256
>
>numbers.
>
>Thanks,
>Harsh Aggarwal
>
>

_________________________________________________________________
High-speed users�be more efficient online with the new MSN Premium Internet
Software. http://join.msn.com/?pgmarket=en-us&page=byoa/prem&ST=1
• ... I was less harsh on him and sent the output from Pari. :-) It took me a heck of a lot longer on a p4 2.53. Would you share your cleverness? ... Cino
Message 2 of 11 , Jan 11, 2004
• 0 Attachment
>From: D�cio Luiz Gazzoni Filho <decio@...>
>Subject: Re: [PrimeNumbers] Factors of mersenne numbers
>Date: Mon, 12 Jan 2004 00:37:34 -0200
>
>-----BEGIN PGP SIGNED MESSAGE-----
>Hash: SHA1
>
>This took all of 13.6 seconds to compute here, with PARI/GP 2.2.7, a P4 2.6
>and a little bit of cleverness. I guess you would have gotten your answer
>faster if you had figured it out yourself rather than asking for help.

I was less harsh on him and sent the output from Pari. :-)
It took me a heck of a lot longer on a p4 2.53. Would you share your
cleverness?

>On Monday 12 January 2004 00:09, eharsh82 wrote:
> > I am looking for all the factors of mersenne numbers under 2^256-1.
> > that is 2^n-1, n from 1 to 256
> > numbers.
> > Thanks,
> > Harsh Aggarwal

Cino
"Behavior is not for the pursuit of survival but because of it."

_________________________________________________________________
Let the new MSN Premium Internet Software make the most of your high-speed
experience. http://join.msn.com/?pgmarket=en-us&page=byoa/prem&ST=1
• Could I also have the factors for composite n s in 2^n-1. Thanks, Harsh ... a P4 2.6 ... answer ... help. ... your ... 2^256-1. ... these ... high-speed
Message 3 of 11 , Jan 11, 2004
• 0 Attachment
Could I also have the factors for composite n's
in 2^n-1.

Thanks,
Harsh

<hillcino368@h...> wrote:
> >From: Décio Luiz Gazzoni Filho <decio@r...>
> >Subject: Re: [PrimeNumbers] Factors of mersenne numbers
> >Date: Mon, 12 Jan 2004 00:37:34 -0200
> >
> >-----BEGIN PGP SIGNED MESSAGE-----
> >Hash: SHA1
> >
> >This took all of 13.6 seconds to compute here, with PARI/GP 2.2.7,
a P4 2.6
> >and a little bit of cleverness. I guess you would have gotten your
> >faster if you had figured it out yourself rather than asking for
help.
>
> I was less harsh on him and sent the output from Pari. :-)
> It took me a heck of a lot longer on a p4 2.53. Would you share
your
> cleverness?
>
>
> >On Monday 12 January 2004 00:09, eharsh82 wrote:
> > > I am looking for all the factors of mersenne numbers under
2^256-1.
> > > that is 2^n-1, n from 1 to 256
these
> > > numbers.
> > > Thanks,
> > > Harsh Aggarwal
>
> Cino
> "Behavior is not for the pursuit of survival but because of it."
>
> _________________________________________________________________
> Let the new MSN Premium Internet Software make the most of your
high-speed
• ... Hash: SHA1 ... Pretty simple, just perform an algebraic factorization on x^i - 1, i = 1..256, following by eval ing the factors with x = 2 and factoring
Message 4 of 11 , Jan 11, 2004
• 0 Attachment
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Monday 12 January 2004 01:21, cino hilliard wrote:
> From: Décio Luiz Gazzoni Filho <decio@...>
>
> >Subject: Re: [PrimeNumbers] Factors of mersenne numbers
> >Date: Mon, 12 Jan 2004 00:37:34 -0200
> >
> >-----BEGIN PGP SIGNED MESSAGE-----
> >Hash: SHA1
> >
> >This took all of 13.6 seconds to compute here, with PARI/GP 2.2.7, a P4
> > 2.6 and a little bit of cleverness. I guess you would have gotten your
> > help.
>
> I was less harsh on him and sent the output from Pari. :-)
> It took me a heck of a lot longer on a p4 2.53. Would you share your
> cleverness?

Pretty simple, just perform an algebraic factorization on x^i - 1, i = 1..256,
following by eval'ing the factors with x = 2 and factoring them in turn. Of
course, you need to sort the output, eliminate the occurrences of 1, and
merge any duplicate factors, but it still beats the hell out of the naïve
procedure.

Actually I think you'd gain some time by hardcoding a difference-of-squares
factorization on the (smaller) even numbers, perhaps even the other
factorizations possible with non-prime-exponent Mersennes, plus avoiding
algebraic factorization while the integer is still within reach of SQUFOF.
But that'd probably take a lot more time to code than what I did.

Décio
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.3 (GNU/Linux)

iD8DBQFAAhkjFXvAfvngkOIRAt17AJ9oOIT8y+/OfXAqLaTUA4HNQwJUUACffcJU
I/E4p31WN1QYIR7YlRCQH7w=
=yTSa
-----END PGP SIGNATURE-----
• ... Hash: SHA1 I should have noticed there was something wrong, the running time was indeed too good to be true. I had swapped the matrix indices when
Message 5 of 11 , Jan 11, 2004
• 0 Attachment
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I should have noticed there was something wrong, the running time was indeed
too good to be true.

I had swapped the matrix indices when performing factorint on the eval'ed
matrix. Basically I was factoring 1s all over the place... the 13 seconds
cost was for algebraic factorizations alone.

I fixed the script and reran it, took 640 seconds this time. (It was stuck on
a couple numbers for a lot of time, like 227 and 251.) Of course, I ran it
over all i=1..256 instead of the prime values only.

I guess I could have saved about half that time if I could pipe ECM work to
GMP-ECM and MPQS work to PPSIQS (:

Décio

On Monday 12 January 2004 01:48, Décio Luiz Gazzoni Filho wrote:
> On Monday 12 January 2004 01:21, cino hilliard wrote:
> > From: Décio Luiz Gazzoni Filho <decio@...>
> >
> > >Subject: Re: [PrimeNumbers] Factors of mersenne numbers
> > >Date: Mon, 12 Jan 2004 00:37:34 -0200
> > >
> > >-----BEGIN PGP SIGNED MESSAGE-----
> > >Hash: SHA1
> > >
> > >This took all of 13.6 seconds to compute here, with PARI/GP 2.2.7, a P4
> > > 2.6 and a little bit of cleverness. I guess you would have gotten your
> > > help.
> >
> > I was less harsh on him and sent the output from Pari. :-)
> > It took me a heck of a lot longer on a p4 2.53. Would you share your
> > cleverness?
>
> Pretty simple, just perform an algebraic factorization on x^i - 1, i =
> 1..256, following by eval'ing the factors with x = 2 and factoring them in
> turn. Of course, you need to sort the output, eliminate the occurrences of
> 1, and merge any duplicate factors, but it still beats the hell out of the
> naïve procedure.
>
> Actually I think you'd gain some time by hardcoding a difference-of-squares
> factorization on the (smaller) even numbers, perhaps even the other
> factorizations possible with non-prime-exponent Mersennes, plus avoiding
> algebraic factorization while the integer is still within reach of SQUFOF.
> But that'd probably take a lot more time to code than what I did.
>
> Décio
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.3 (GNU/Linux)

iD8DBQFAAh6SFXvAfvngkOIRApNxAJ9HTvCwMzMs9CODC8CG0X/A6nFH5ACfYhvD
KzKA/+pu0pLONjy4nh/To/8=
=nd8w
-----END PGP SIGNATURE-----
• ... these ... Will Edgington collects factors of Mersenne Numbers. He regularly updates the files with all known factors for exponents up to 200,000. He
Message 6 of 11 , Jan 11, 2004
• 0 Attachment
--- In primenumbers@yahoogroups.com, "eharsh82" <harsh@u...> wrote:
> I am looking for all the factors of mersenne numbers under 2^256-1.
> that is 2^n-1, n from 1 to 256
>
these
> numbers.

Will Edgington collects factors of Mersenne Numbers. He regularly
updates the files with all known factors for exponents up to 200,000.
He responds to email requests for factors of small numbers of higher
exponents. He collects all exponents through 2^30 and prime exponents
much higher. His web site is

http://www.garlic.com/~wedgingt/mersenne.html

Dario Alpern also has all these factors available in his Java
Factoring applet at

http://www.alpertron.com.ar/ECM.HTM

William
-
ElevenSmooth: Distributed Factoring of 2^3326400-1
http://ElevenSmooth.com
• Hi Decio, The Pari script I posted using the Pari Factor() function took 13.5 min to test primes only. This is the one for composites (I e-mailed direct to
Message 7 of 11 , Jan 11, 2004
• 0 Attachment
Hi Decio,

The Pari script I posted using the Pari Factor() function took 13.5 min to
test primes only.
This is the one for composites (I e-mailed direct to him)
mrsenne(b, n, d) =
c=0;for(x=2,n,if(!isprime(x),y=b^x-d;f=factor(y);v=f[,1];ln=
length(v);print1(b"^"x"-"d"=");for(i=1,ln,print1(v[i]","););print()))
Also I got this for 2^254-1
*** Warning: MPQS: the factorization of this number will take several
hours
It was not true as is stated below.

For the second request from Harsh to do the composits, it took 24 min.That
is a total of 37.5 min.
I realized that the request made was for a small number and figured that an
would surface much faster than coding a factorization project. However, for
n = 1024 there is
no other way. Assuming your results are correct, your method is 37.5/10.7 =
3.5 times faster
than the Pari function. I have been looking at the Lucus Lehmer test. Maybe
it will help speed the
calculation of factors. I would like to try your method. Can you post the
script so i can play?
Maybe Pari could use a mersenne function similar to the one above but with

>From: D�cio Luiz Gazzoni Filho <decio@...>
>Subject: Re: [PrimeNumbers] Factors of mersenne numbers
>Date: Mon, 12 Jan 2004 02:12:02 -0200
>
>-----BEGIN PGP SIGNED MESSAGE-----
>Hash: SHA1
>
>I should have noticed there was something wrong, the running time was
>indeed
>too good to be true.
>
>I had swapped the matrix indices when performing factorint on the eval'ed
>matrix. Basically I was factoring 1s all over the place... the 13 seconds
>cost was for algebraic factorizations alone.
>
>I fixed the script and reran it, took 640 seconds this time. (It was stuck
>on
>a couple numbers for a lot of time, like 227 and 251.) Of course, I ran it
>over all i=1..256 instead of the prime values only.
>
>I guess I could have saved about half that time if I could pipe ECM work to
>GMP-ECM and MPQS work to PPSIQS (:
>
>D�cio
>
>On Monday 12 January 2004 01:48, D�cio Luiz Gazzoni Filho wrote:
> > On Monday 12 January 2004 01:21, cino hilliard wrote:
> > > From: D�cio Luiz Gazzoni Filho <decio@...>
> > >
> > > >Subject: Re: [PrimeNumbers] Factors of mersenne numbers
> > > >Date: Mon, 12 Jan 2004 00:37:34 -0200
> > > >
> > > >-----BEGIN PGP SIGNED MESSAGE-----
> > > >Hash: SHA1
> > > >
> > > >This took all of 13.6 seconds to compute here, with PARI/GP 2.2.7, a
>P4
> > > > 2.6 and a little bit of cleverness. I guess you would have gotten
>your
>for
> > > > help.
> > >
> > > I was less harsh on him and sent the output from Pari. :-)
> > > It took me a heck of a lot longer on a p4 2.53. Would you share your
> > > cleverness?
> >
> > Pretty simple, just perform an algebraic factorization on x^i - 1, i =
> > 1..256, following by eval'ing the factors with x = 2 and factoring them
>in
> > turn. Of course, you need to sort the output, eliminate the occurrences
>of
> > 1, and merge any duplicate factors, but it still beats the hell out of
>the
> > na�ve procedure.
> >
> > Actually I think you'd gain some time by hardcoding a
>difference-of-squares
> > factorization on the (smaller) even numbers, perhaps even the other
> > factorizations possible with non-prime-exponent Mersennes, plus avoiding
> > algebraic factorization while the integer is still within reach of
>SQUFOF.
> > But that'd probably take a lot more time to code than what I did.
> >
> > D�cio

_________________________________________________________________
High-speed users�be more efficient online with the new MSN Premium Internet
Software. http://join.msn.com/?pgmarket=en-us&page=byoa/prem&ST=1
• ... Mersenne numbers are but a special case of the factorizations collected by the Cunningham project. They form the 2- table in that project. The Cunningham
Message 8 of 11 , Jan 12, 2004
• 0 Attachment
> From: eharsh82 [mailto:harsh@...]
> Sent: 12 January 2004 03:25
> Subject: [PrimeNumbers] Re: Factors of mersenne numbers
>
> Could I also have the factors for composite n's
> in 2^n-1.
>
> Thanks,
> Harsh

Mersenne numbers are but a special case of the factorizations collected by the Cunningham project. They form the 2- table in that project.

The Cunningham project web page is at http://www.cerias.purdue.edu/homes/ssw/cun/index.html

I also maintain a copy of the Cunningham project tables in a slightly different format, one which I believe is more amenable to programmatic accesss. These tables can be found at http://research.microsoft.com/~pleyland/factorization/cunningham/main.htm

Paul
• ... Hash: SHA1 ... OK, the script that I had would only factor and throw away the results (I didn t want them, I just wanted to time how long it would take).
Message 9 of 11 , Jan 12, 2004
• 0 Attachment
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Monday 12 January 2004 03:09, cino hilliard wrote:
> Hi Decio,
>
> The Pari script I posted using the Pari Factor() function took 13.5 min to
> test primes only.
> This is the one for composites (I e-mailed direct to him)
> mrsenne(b, n, d) =
> c=0;for(x=2,n,if(!isprime(x),y=b^x-d;f=factor(y);v=f[,1];ln=
> length(v);print1(b"^"x"-"d"=");for(i=1,ln,print1(v[i]","););print()))
> Also I got this for 2^254-1
> *** Warning: MPQS: the factorization of this number will take several
> hours
> It was not true as is stated below.
>
> For the second request from Harsh to do the composits, it took 24 min.That
> is a total of 37.5 min.
> I realized that the request made was for a small number and figured that an
> would surface much faster than coding a factorization project. However, for
> n = 1024 there is
> no other way. Assuming your results are correct, your method is 37.5/10.7
> = 3.5 times faster
> than the Pari function. I have been looking at the Lucus Lehmer test. Maybe
> it will help speed the
> calculation of factors. I would like to try your method. Can you post the
> script so i can play?

OK, the script that I had would only factor and throw away the results (I
didn't want them, I just wanted to time how long it would take). I've made it
output numbers much like your format, and here it is (hoping that there
aren't many bugs):

mersenne(b, n, d) =
{
for(k = 1,n,
polfact = factor(x^k-d);

x = b;
factors = eval(polfact);
kill(x);

myfactors = matrix(2,0);
for(j = 1,matsize(factors)[1],
myfactors = vecsort(
concat(
myfactors~,
factorint(factors[j,1]^factors[j,2])~
),1
)~;
);

print1(b"^"k"-"d" = ");
i = 1;
while(i < matsize(myfactors)[1],
if(myfactors[i,1] != myfactors[i+1,1],
print1(myfactors[i,1]);
if(myfactors[i,2] > 1,
print1("^"myfactors[i,2]);
);
print1(",");
i++;
,
count = 0;
start = i;
while(i <= matsize(myfactors)[1] &&
myfactors[i,1] == myfactors[start,1],
count += myfactors[i,2];
i++;
);
print1(myfactors[start,1]"^"count",");
);
);
if(i == matsize(myfactors)[1],
print1(myfactors[i,1]);
if(myfactors[i,2] > 1,
print1("^"myfactors[i,2]);
);
print();
,
print();
);
);
}

> Maybe Pari could use a mersenne function similar to the one above but with

The problem here is that when you type factorint(2^64-1), say, PARI/GP parses
this as factorint(18446744073709551615), losing the `algebraic structure' if
I may call it that. There'd have to be a function that took a string as input
or something.

Décio
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.3 (GNU/Linux)

iD8DBQFAAon1FXvAfvngkOIRAgFDAJ4tKrUHscJvMeu8f+glPKGkyHpXjgCeN/bU
bsUYEitTLHLgF2EucpIVldI=
=kWAt
-----END PGP SIGNATURE-----
Your message has been successfully submitted and would be delivered to recipients shortly.