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

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

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.