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

Question

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
}

Answer 1

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.

Answer 2

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.