# Conditions for maximum period of quadratic congruential method (PRNG)

$$X_{n} = (d^2X_{n-1} + aX_{n-1} + c) \operatorname{mod} m$$

Knuth lists out the necessity and sufficiency of 4 conditions (Exercise 8 in page 49 of "The art of computer programming Vol.II"):

1. $$c$$ is relatively prime to $$m$$
2. $$d$$ and $$a-1$$ are both multiples of $$p$$, for all odd primes $$p$$ dividing $$m$$
3. $$d \equiv a-1$$(mod 2) when $$2|m$$; $$d$$ is even and $$d \equiv a-1$$(mod 4) when $$4|m$$
4. $$d \not \equiv 3c$$ (mod 9) when $$9|m$$

Knuth writes in the answer to exercise 8:

If $$p \leqslant 3$$, it's easy to establish the necessity of condition (iii) and (iiii) by trial and error method

I do try to find my own way to prove (the necessity of) condition (iii) and (iiii). Here's how i prove the first one:

Assume $$m=p^e$$. Firstly, we consider the case when $$p=2,e=1$$

So, the sequence $$X_n$$ with ($$X_0 = 0$$ and $$m=2$$) has the period of $$2$$ when:
$$X_2 = X_0 = 0$$

We can prove: $$X_2=dc+a+1 \operatorname{mod}$$ 2 (due to the relatively prime $$c$$)

Obviously, we have: $$d \equiv a-1 (\operatorname{mod} 2)\space \tag1$$

If $$e \geqslant 2$$ then $$4|m$$. The same sequence $$X_n$$ with $$(X_0=0,m=4)$$ must have the period of 4 which means: $$X_0\not=X_1\not=X_2\not=X_3$$

$$X_2 \not=X_0$$. So, $$X_2 = 2$$ and $$X_3 \not=X1$$. The fact then implies: $$aX_2 \not\equiv 0 (\operatorname{mod} 4)\space\tag2$$

Due to (1), (2), $$a \operatorname{mod} 4$$ and $$d \operatorname{mod} 4$$ can only adopt odd and even values. After some trials on $$X_2 = dc + a + 1 \operatorname{mod} 4= 2$$ (c is odd), we easily prove: $$d \equiv a-1(\operatorname{mod} 4)$$

I have also proved the condition (iiii) by my "trial and error method" but i'm not sure if they are what Knuth mentions. So my first question:
1. What's exactly "trial and error method" applying for this situation?

Finally, the proof of condition (ii) confuses me:

If $$d \not\equiv 0(\operatorname{mod} p)$$ then $$dx^2+ax+c \equiv d(x+a_1)^2 + c_1(\operatorname{mod} p^e)$$ for some integers $$a_1$$, $$c_1$$ and for all integers x

$$d\not\equiv 0 (\operatorname{mod} p)$$ leads to d relatively prime to $$p^e$$. But i can't go on any further from this.

1. Why does $$dx^2+ax+c\equiv d(x+a_1)^2 + c_1(\operatorname{mod} p^e)$$ hold when $$d \not\equiv 0(\operatorname{mod} p)$$ ?

What's exactly "trial and error method" applied in this situation?

$$\newcommand{\mymod}{\operatorname{modulo}}$$As I understand, "trial and error method" here means checking all cases from a few simple natural or known perspectives until we have found a satisfactory solution or proof. It is useful and efficient in this situation because the number of cases $$\mymod 2$$ or $$\mymod 4$$ or $$\mymod 9$$ is very small.

What you have done seems pretty good.

Why does $$dx^2+ax+c\equiv d(x+a_1)^2 + c_1(\mymod{p^e})$$ hold when $$d \not\equiv 0\,(\mymod{p})$$ ?

Prime $$p\not=2$$ since it has been assumed $$p\ge5$$. Since $$d \not\equiv 0\,(\mymod p)$$, $$2d$$ and $$p^e$$ are relatively prime, which implies $$2d$$ is invertible $$\mymod p^e$$. Let $$(2d)d'\equiv1\,(\mymod p^e)$$ fro some $$d'$$. Then

\begin{aligned} dx^2+ax+c &\equiv dx^2+2dd'ax + c\\ &\equiv d(x+d'a)^2 -d(d'a)^2+c\ (\mymod p^e)\\ \end{aligned}

Letting $$a_1=d'a$$ and $$c_1=-d(d'a)^2+c$$, we are done.