Loading ...
Sorry, an error occurred while loading the content.

RE: [PrimeNumbers] Factors of mersenne numbers

Expand Messages
  • cino hilliard
    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

      http://pari.math.u-bordeaux.fr/download.html

      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@...>
      >To: primenumbers@yahoogroups.com
      >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
      >
      >Could you please provide me with a website where I can download these
      >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
    • cino hilliard
      ... 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@...>
        >To: primenumbers@yahoogroups.com
        >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
        > > Could you please provide me with a website where I can download 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
        experience. http://join.msn.com/?pgmarket=en-us&page=byoa/prem&ST=1
      • eharsh82
        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

          --- In primenumbers@yahoogroups.com, "cino hilliard"
          <hillcino368@h...> wrote:
          > >From: Décio Luiz Gazzoni Filho <decio@r...>
          > >To: primenumbers@yahoogroups.com
          > >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
          > > > Could you please provide me with a website where I can download
          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
          > experience. http://join.msn.com/?pgmarket=en-us&page=byoa/prem&ST=1
        • Décio Luiz Gazzoni Filho
          ... 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@...>
            >
            > >To: primenumbers@yahoogroups.com
            > >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?

            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-----
          • Décio Luiz Gazzoni Filho
            ... 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@...>
              > >
              > > >To: primenumbers@yahoogroups.com
              > > >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?
              >
              > 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-----
            • elevensmooth
              ... 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
                >
                > Could you please provide me with a website where I can download
                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
              • cino hilliard
                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
                  answer, albiet slow
                  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
                  your speed up.

                  >From: D�cio Luiz Gazzoni Filho <decio@...>
                  >To: primenumbers@yahoogroups.com
                  >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@...>
                  > > >
                  > > > >To: primenumbers@yahoogroups.com
                  > > > >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?
                  > >
                  > > 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
                • Paul Leyland
                  ... 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
                    > To: primenumbers@yahoogroups.com
                    > 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
                  • Décio Luiz Gazzoni Filho
                    ... 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
                      > answer, albiet slow
                      > 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
                      > your speed up.

                      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.