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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .