Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I figured that I can create a deterministic "random" numbers generator by utilizing a bit of "magic" that I picked up from some cryptography. However I seem to have missed a detail.

Basically the function $\displaystyle f(n) = p^n \mod q$ should for $\displaystyle n$ in the range $\displaystyle [1,q-1]$ produce all the numbers in the same range, but in a scrambled order, however that is only true for some pairs of $\displaystyle p$ and $\displaystyle q$.

How exactly do I find and verify such pairs?

Update:
I now know why I missed that detail, I'm think my computer will be done finding a few suitable number pairs by brute force long before I will be done understanding a more efficient approach.

I think I'll run two of these generators in tandem, using their sum mod limit to generate a number in the field $[0;limit-1]$. For each pair I'll choose $q$ close to 2^32, $p$ close to 2^16, and assert that $p$ is prime, $q$ is prime, $(q-1)/2$ is prime and that $p$ is a primitive root of $q$.

Thanks for your input, but I'll leave the question open to anyone who can explain a computationally efficient method of asserting primitive rootness status of two numbers in a way that I understand.

Update:
I have found the pairs 65539 (mod 4294967087) and 65537 (mod 4294965887), this gives the following JavaScript function:

function seed(state1,state2){
    var mod1=4294967087
    var mul1=65539
    var mod2=4294965887
    var mul2=65537
    state1=state1%mod1
    state2=state2%mod2
    function random(limit){
        state1=(state1*mul1)%mod1
        state2=(state2*mul2)%mod2
        return (state1+state2)%limit
    }
    return random
}
share|improve this question

3 Answers 3

Assuming $\displaystyle q$ is a prime, you need $\displaystyle p$ to be a Primitive Root of $\displaystyle q$.

It is known that every prime $\displaystyle q$ has a primitive root.

In fact $\displaystyle q$ can also be a power of an odd prime or twice the power of an odd prime, see here: http://www.math.uiuc.edu/~hildebr/453/notes/nt-notes5.pdf.

It (according to the wiki link below) has been shown that the least primitive root of $\displaystyle q$, $\displaystyle g_q$ satisfies $\displaystyle g_q < C\sqrt[4]{q}$

and by assuming the generalized Riemann Hypothesis, in fact that $\displaystyle g_p = O(\log^6 q)$.

See here: Magnitude of Primitive Roots.

So given a $\displaystyle q$, you should be able to simply do a scan to find the least primitive root relatively quickly.

If you are interested in $\displaystyle p$ also being prime, see also: Artin's Conjecture on Primitive Roots.

share|improve this answer

The wiki article has an algorithm for testing primitive roots; it requires you to factor $q-1$. But once you've done that, together with the GRH bound mentioned in Moron's answer you should at least be able to locate a primitive root in polynomial time.

But this is a really inadvisable way of generating "random" numbers. Given even two consecutive values of the sequence you can predict all of the others. There are much better methods described, for example, here.

share|improve this answer
    
It's not for cryptographic usage, in fact the seed will be public, so it's predictable in any case. This method has a guaranteed period and spread evenly across the entire field, that seems pretty neat to me, that is why I choose it. –  eBusiness Nov 17 '10 at 11:45
up vote 0 down vote accepted

Asserting $p$ to be a primitive root of prime $q$

$p$ is a primitive root of $q$ iff $p^n \mod q$ is different for each $n$ in the range $[0;q-2]$.

When $p$ and $q$ are internally primary integers greater than $1$, $p^n \mod q$ will always describe a repeating series beginning with $1$ for $n=0$. No other value in the series is 1 until the series start repeating.

The series cannot be longer than $q-1$.

Given this knowledge it is possible to validate a potential primitive root of $q$ by calculating only a few select values of $p^n \mod q$.

The computation

First assert that $p^{q-1} \mod q$ is $1$. If this is true the length of the non-repeating series must be a factor of $q-1$.

Prime factorize $q-1$, for every distinct prime factor of $q-1$ as $f$, compute $p^{(q-1)/f} \mod q$. If none of the results are $1$, $p$ must be be a primitive root of $q$.


This is evident as any series length that is a factor of $q-1$, but isn't $q-1$ would have caused at least one of the results to be $1$.

Computationally efficient methods

The biggest hurdle in this technique is the prime factorization of $q-1$, for small numbers a simple brute force search up to the square root of the number being factorized may suffice, but much faster methods exist. Those methods are outside the scope of this answer, but they can for instance be used through a mathematics tool or this website without much effort.

Computing $p^n \mod q$ can be done efficiently for large values of all three variables using exponentiation by squaring. Here is the recursive algorithm from Wikipedia modified to do modular exponentiation with integers:

Function exp_by_squaring(x,n,m)
   if n=0 then return 1;
   else if n=1 then return x;
   else if n is even then return exp_by_squaring(x*x mod m, n/2, m);
   else if n is odd then return x * exp_by_squaring(x*x mod m, (n-1)/2, m) mod m;
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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