# Deterministic random numbers generator using $p^n \mod q$

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
}

-

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.

-
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.