[Math] What software can calculate the order of $b \mod p$, where $p$ is a large prime

math-softwaremodular arithmeticnumber theoryprime factorizationprime numbers

I wasn't sure where to ask this, but Mathematics seems better than StackOverflow or Programmers.

I have no background whatsoever in number theory, and I need to find software that can calculate the order of $b \mod p$, where $b = 2^{32}$ and $p$ is of the form $p = a * b^r + 1$. I've calculated a number of suitable primes using NewPGen and PFGW (as well as Proth.exe), but I have no obvious way of calculating the order of $b \mod p$.

Does anyone know of any program that can do this?

Context, if needed:

I read here (https://stackoverflow.com/questions/5760639/complimentary-multiply-with-carry-period/8781297#8781297) that calculating the order requires factoring $\phi(p) = p – 1$. Then, for every factor $k$, the order of $b \mod p$ is the smallest $k$ such that $b^{(\phi(p)/k)}\mod p = 1$.

Factoring $p – 1$ is easy in my case, since all of my candidates are already factored for the most part (except the $a$ term), but from what I understand I need not only the prime factors but ALL factors of $p – 1$, and it seems there will always be a ton of them when $b$ is a large power of $2$. (I don't understand all of that post though, such as their calculation of the number of factors the original poster would have to test.)

Unfortunately, I'm dealing with relatively large numbers here, e.g. $p = 131071 * 2^{864} + 1$. In this example $a = 131071$ is mercifully prime, but there are $864$ different $2$ factors. Naively trying every possible combination of the $865$ prime factors would presumably require calculating $b^{phi(p)/k}\mod p$ for, uh…$\sum_{i=1}^{865} 865!/(i!(865 – i)!)$ different $k$'s, which is more than anyone could calculate in the lifetime of the universe.

Knowing $864$ of $phi(p) = p – 1$'s factors are all $2$'s makes things much more manageable, and we only need to try I think $1730$ different $k$'s ($1$ or $131072$ times anywhere from $0$ to $864$ factors of $2$). If this post is anything to go by, I MIGHT be able to get away with testing only $k$'s containing all $864$ $2$ factors, but I could easily be wrong, since the presence of a non-$2$ factor might change things: Why 4 is not a primitive root modulo p for any prime p?.

I don't know modular arithmetic though, so even if I only had to test a handful of $k$'s to obtain the order, there's no obvious way for me to calculate something as huge as $b^{(\phi(p)/k)}\mod p$ even once, when $b = 2^{32}$. The numbers are just too big…so I need some software that knows how to do this sort of thing, preferably software that can calculate the order of $b \mod p$ straight out of the box.

I've found a program that claims to be able to do this, but even the smallest and most trivial prime I'm interested in ($p = 255 * 2^{32} + 1$) is too big for it to handle:
http://www.softpedia.com/get/Science-CAD/ORDER-OF-A-MODULO-P.shtml

Additional Context:

I'm trying to find suitable parameters for complementary multiply with carry (CMWC) generators, a class of random number generators invented by George Marsaglia (https://en.wikipedia.org/wiki/Multiply_with_Carry). These generators require a prime of the form $p = a * b^r + 1$, where $a$ is some multiplier, $b$ is the base, and $r$ is the lag of the generator (which increases the period). The period of a CMWC generator is the order of $b \mod p$, and I'm trying to calculate the period of generators fitting the following description:

  • $b = 2^{32}$, which allows the generator to natively return the full range of unsigned 32-bit numbers, without incurring the cost of a remapping output function.
  • $r$ is in $[1, 32]$, with special emphasis on $r = 4, 8, 16, 32$. $r$ controls the maximum possible period of the generator, but it also controls the amount of state that needs to be stored, and I'm looking for lightweight generators that come as close as possible to maximal period. (Marsaglia calculated suitable parameters for smaller base-$2^{32} – 1$ CMWC generators, and he also provided parameters for smaller base-$2^{32}$ MWC generators…but the only base-$2^{32}$ CMWC generator he talked about was CMWC4827, with $r = 4827$…which is too large for my purposes.)
  • $a$ can be anything, but things can be a bit more efficient if $a = 2^n \pm 1$. I have a few candidate $a$'s that fit this description, but not for my preferred power-of-2 $r$ candidates, unfortunately.

Best Answer

If I'm not mistaken, Sage might help you.

sage: p = 131071*2^864+1
sage: is_prime(p) # check that it's prime
True
sage: b = mod(2^32,p) # makes a modular integer
sage: b.multiplicative_order()
251908540996674781143692700238872014353662372271648506382312691467942113675280721713248000547359389291315410905230983600885476978770662739599958129278514946363281164152553521078806838898769965654577169449156458268844603358445019507312417844944481614256657162829824

You can make an account for free at sagenb.org or other various similar Sage servers online, or download it. This functionality comes via Pari.

Related Question