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

Help finding order of b=2^32 mod large primes

Expand Messages
  • George Marsaglia
    I am writing the section on random number generators for the new edition of the Abramowitz and Stegun Handbook of Mathematical Functions. I plan a section on
    Message 1 of 1 , Jul 29, 2001
    • 0 Attachment
      I am writing the section on random number generators
      for the new edition of the Abramowitz and Stegun
      Handbook of Mathematical Functions.

      I plan a section on multiply-with-carry RNG's, which
      are simple to program, have immense periods and seem
      to pass tests of randomness at least as well as other RNG's.

      MWC RNG's are based on finding primes m of the form
      m = a*2^r + 1
      and then the period of the MWC RNG is
      the order of b=2^32 for that prime m.

      The following candidate m's came from lists,
      many of which were provided by members of this group,
      or from use of primeform or pfgw.
      They may be included in the table,
      if the order of b mod m can be found.

      I welcome the contributions any of this group's
      readers who may wish to confirm primality
      or find the order of b=2^32 for those m's.
      I have found the prime factors of m-1 for
      the non-trivial cases, and have found some of
      the orders, but seek additional ones or confirmation
      for those already found.

      Possible m's; find order of b=2^32, that is,
      find the smallest k for which b^k = 1 mod m.

      m = 3*2^916773+1
      m = 7*2^283034+1
      m = 9183*2^262112+1
      m = 137*2^261147+1
      m = 29*2^261031+1
      m = 29*2^252227+1
      m = (2^597+1)*2^32180+1
      the prime factors of m-1 are
      2,3,5153543358319177,
      1616721141393989482351447740066663923511303121,
      25827119250999351443374505513011778112393876592372931367907
      267823007376498379256993682056860433753700498963798805883563,

      m = (2^1197+1)*2^30154+1
      (m-1) has prime factors 2,778051,1697347,P183 (get P183 by division)

      m = (2^1197+1)*2^28164+1
      (m-1) has the prime factors of the previous (m-1).

      m = (2^1185+1)*2^30429+1
      (m-1) has prime factors 2,2371,18859377449506801,P169 (by division)

      m = (2^371+1)*2^28990+1
      the prime factors of m-1 are 2,18351945672220987,
      10471846336802440580575859,90338901802490793533882683,
      277043655441107331501889854077610037519928691


      m = (9*2^238+1)*2^7954+1
      m-1 has prime factors 2,13,1574402396173,
      194232716021434134986699570110629178468739387962178095993753;

      Note: primes of the form m = a*2^r -1 are even better, but unless
      m is a safeprime (q=(m-1)/2 is prime, so that q is a Sophie Germain prime),
      factoring m-1 for such large m's is usually hopeless.

      George Marsaglia
    Your message has been successfully submitted and would be delivered to recipients shortly.