1
$\begingroup$

The problem

Let $m=p\cdot q$, where $p,q$ are primes. The LCG is $x_i=(ax_{i-1}+b)\mod m$, where $0<a<m$, $0\leq b<m$ and $0\leq x_0<m$.

I need to show that (without Hull-Dobel theorem) if $m$ is such that:

  1. $\text{GCD}(b,m)=1$,
  2. if $m$ is divisible by some prime $p$, then $(a-1)$ is divisible by $p$,
  3. if $m$ is divisible by $4$, then $(a-1)$ is divisible by $4$,

the LCG reaches it's maximum cycle length.

What I have

When $p\neq q$ the proof is pretty straight forward, from the second condition I get that $a=1$, from that $x_i=(x_0+i\cdot b)\mod m$ and then $m|i$. Also I know how to prove it when $p=q=2$.

Where I'm stuck

I don't know how to prove it when $p=q$. How should the proof go? What should I do? What am I missing?

$\endgroup$

1 Answer 1

2
$\begingroup$

When $p = q \ne 2$, from the second condition we have $a = np + 1$, where $0\le n\le p-1$ is an integer.

We now claim that $x_i \equiv (inp + 1)x_0 + \left(\frac{i(i-1)}{2}np + i\right)b \pmod{p^2}$.
For $i = 0$ it is obviously true.
Assume it is also true for $i = k$.
Then $x_{k+1} = ax_k + b \equiv (np + 1)\left((knp + 1)x_0 + \left(\frac{k(k-1)}{2}np + k\right)b\right) + b \pmod{p^2}$
$\equiv (knp + np + 1)x_0 + \left(\frac{k(k-1)}{2}np + knp + k + 1\right)b \pmod{p^2}$
$= ((k+1)np + 1)x_0 + \left(\frac{(k+1)k}{2} + k + 1\right)b$
Thus, the claim is true by induction.

Assume $\exists$ $i, j$ such that $x_i = x_j \pmod{p^2}$.
Then compute $x_i - x_j$
$= (inp + 1)x_0 + \left(\frac{i(i-1)}{2}np + i\right)b - (jnp + 1)x_0 - \left(\frac{j(j-1)}{2}np + j\right)b$
$= (i-j)npx_0 + \frac{(i-j)(i+j-1)}{2}np + (i-j)b$

Since it is divisible by $p^2$ (and hence $p$), and $\gcd{(b,p)} = 1$, we have $i-j=0\pmod p$.
Then now the first two terms are divisible by $p^2$, so we further have $i-j=0\pmod{p^2}$.

Therefore, the period attains its maximum at $p^2 = m$.

$\endgroup$
2
  • $\begingroup$ Why is does the following hold $\ldots+ b \pmod{p^2} \equiv (knp + np + 1)x_0\ldots$? $\endgroup$
    – pls_halp
    Mar 1, 2018 at 19:42
  • $\begingroup$ Direct expansion of $(np+1)\left((knp+1)x_0 + \left(\frac{k(k-1)}{2}np + k\right) b\right) + b$. Grouping the $x_0$ term gives $(kn^2 p^2 + knp + np + 1)x_0$, which simplifies to $(knp + np + 1)x_0$ mod $p^2$. Grouping the $b$ term gives $\left(\frac{k(k-1)}{2}n^2 p^2 + knp + \frac{k(k-1)}{2}np + k + 1\right)b$, which simplifies to $\left(\frac{k(k-1)}{2}np + knp + k + 1\right)b$ mod $p^2$. $\endgroup$
    – diagonal2
    Mar 2, 2018 at 7:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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