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.

  • $\begingroup$ Might not cause your immediate problem, but should use a BigInteger class instead of Math.Pow and double. $\endgroup$ Commented Apr 12, 2013 at 17:09
  • $\begingroup$ Why double? The Rabin function can only return an integer. $\endgroup$ Commented Apr 12, 2013 at 17:11
  • $\begingroup$ Your immediate problem is the unfortunate choice of the modulus. $\endgroup$ Commented Apr 12, 2013 at 17:12
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Apr 12, 2013 at 17:52
  • $\begingroup$ You might be interested in knowing that a rather similar PRNG called Blum Blum Shub already existed. $\endgroup$
    – Dan D.
    Commented Aug 19, 2013 at 22:05

1 Answer 1


The modulus 77 leads to a short period.

  • $\begingroup$ Ok, so how would I increase the period? $\endgroup$ Commented Apr 12, 2013 at 17:16
  • 4
    $\begingroup$ A better choice of modulus. The product of two large primes (say 512 bits each) should do the job. $\endgroup$ Commented Apr 12, 2013 at 17:17
  • $\begingroup$ Ok, last question, is it ok that the original seed is small or is that somehow related to p and q? In other words, would a larger seed value also make a difference. $\endgroup$ Commented Apr 12, 2013 at 17:18
  • $\begingroup$ @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$ $\endgroup$
    – poncho
    Commented Apr 12, 2013 at 17:23
  • 1
    $\begingroup$ @CodesInChaos: actually, it's $x^{\lambda(n)+1} = x \ (\bmod\ n)$ $\endgroup$
    – poncho
    Commented Apr 12, 2013 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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