# Pseudo Random Generator (PRG) from Rabin function

I'm trying to make a PRG using the Rabin function. The code (in Java) I wrote to implement the function is:

poublic static int rabinFunction(int m, int publicKey) {
return (int) Math.pow(m, 2) % publicKey;
}


A trivial usage (using the numbers from the wikipedia link) would be:

int m = 20;
int pq = 7 * 11;

// output will be 15
int output = rabinFunction(20, 77);


I'm using this one way function to create a pseudo random generator. Basically, I run the Rabin function and use the least significant bit from the function output as part of my pseudorandom value. I use the return value from the previous execution as the seed for the next execution and I repeat this process until I've generated enough bits to encrypt my message. The issue I'm having is that the Rabin function returns the same values after 4 iterations:

rabinFunction(20, 77); //==> 15
rabinFunction(15, 77); //==> 71
rabinFunction(71, 77); //==> 36
rabinFunction(36, 77); //==> 64
rabinFunction(64, 77); //==> 15! Back to where we started, etc


I'm assuming that using the output from a previous execution of the Rabin function as the seed for a new one isn't correct. Can someone explain why this is wrong? Thanks in advance.

• Might not cause your immediate problem, but should use a BigInteger class instead of Math.Pow and double. Commented Apr 12, 2013 at 17:09
• Why double? The Rabin function can only return an integer. Commented Apr 12, 2013 at 17:11
• Your immediate problem is the unfortunate choice of the modulus. Commented Apr 12, 2013 at 17:12
• Math.pow calculates as and returns double, which you then round to an int, and reduce modulo your modulus. With bigger numbers this will get you into poblems. Actually, when squaring integers, simply writing x * x is the easiest way. Commented Apr 12, 2013 at 17:52
• You might be interested in knowing that a rather similar PRNG called Blum Blum Shub already existed. Commented Aug 19, 2013 at 22:05

• @CodesInChaos: actually, $x^{16} = x$ does not hold in general; it doesn't for $x=2$ with $x^{16} = 9$. However, $x^{32} = x^{2}$ does hold, hence you'll always end up with a cycle at most 4. This happens because $p-1=6$ and $q-1=10$ are both divisors of $32-2$ Commented Apr 12, 2013 at 17:23
• @CodesInChaos: actually, it's $x^{\lambda(n)+1} = x \ (\bmod\ n)$ Commented Apr 12, 2013 at 17:57