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

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.

-
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

## 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;

-