Help finding order of b=2^32 mod large primes
- 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
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,
m = (9*2^238+1)*2^7954+1
m-1 has prime factors 2,13,1574402396173,
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.