5
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ You know that $\phi(p) = p-1 = a \cdot 2^{32r}$ and the order or $b$ is a divisor of $\phi(p)$. So there are at most $64r + 2$ possible values for the order of $b$: $a^{\{0,1\}} \cdot 2^{\{0, 1, \ldots, 32r\}}$. $\endgroup$ – TMM May 4 '13 at 14:04
  • $\begingroup$ I want to upvote both you and kcrisman, but I don't have the rep yet...hopefully this comment will help get me there. Anyway, doesn't your full post contradict what you're saying here in this comment? The order of b for this example is a * 2^858, and since r = 27, the order is apparently not a^{0, 1} * 2^{0, 1, ...,32r}, since r does not cleanly divide into 858. $\endgroup$ – Mike S May 4 '13 at 15:02
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You should also really consider investing some time in an elementary number theory text or course; I think that a lot of your difficulties will be eased in that case, and if you are implementing something like this you obviously have the chops to assimilate this material. Plus, number theory is beautiful :) $\endgroup$ – kcrisman May 4 '13 at 14:02
  • $\begingroup$ Thank you! I'm in the middle of compiling Sage, so I haven't put it to use yet, but your clear usage example - and TMM corroborating the answer it produced - shows this is exactly what I'm looking for. The RNG is really just an indulgent subproject of a subproject of a project I'm working on, so I don't deal with this kind of math (or huge numbers) often, but I may follow your advice someday and learn some basic number theory if I ever find the time. :) In the meantime, I'll try to digest TMM's post below. Whenever I get the rep to do so, I'll upvote your answer and his. $\endgroup$ – Mike S May 4 '13 at 15:18
  • 1
    $\begingroup$ Sounds great. I'm surprised that one can't upvote one's own question's answers... Anyway, remember that there are a lot of binaries available as well, and the online servers are in many ways more convenient. And I look forward to hearing you did pick up that number theory ;-) $\endgroup$ – kcrisman May 6 '13 at 12:45
  • 2
    $\begingroup$ Hello to the downvoter - any particular reason on this? Both of these answers seem appropriate to the question... $\endgroup$ – kcrisman Feb 21 '14 at 15:10
1
$\begingroup$

If you are still looking for a solution, Mathematica's MultiplicativeOrder can do this. Unlike Sage, Mathematica is not free, but for smaller inputs you can use Wolfram Alpha.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.