1
$\begingroup$

Task: Show that the sequence of integers made up of the $k$ rightmost bits generated by an LCG with $m = 2^n$ has a period of at most $2^k$.

I actually get a hint to define the output as the following: $R_i = X_i \operatorname{mod} 2^k$ and derive a recursion.

The LCG algorithm is to provide a seed $X_0$ and iterate for $i \geq 1$, $$ X_i = aX_{i-1} + c \operatorname{mod} 2^n; \ \ R_i = X_i \operatorname{mod} 2^k. $$ Deriving a recursion for $R_i$ is difficult when $c \neq 0$, so I thought to set $c = 0$. Then, $$ R_i = a^jx_0 \operatorname{mod} 2^k. $$ How can I derive from this that the period is at most $2^k$?

$\endgroup$

1 Answer 1

1
$\begingroup$

To clarify, for all nonnegative integer $x$ and positive integer $m$, the notation "$x\bmod m$" means the (unique) least nonpositive integer the difference between which and $x$ is a multiple of $m$. Or x % m in programming languages.

Verify that $$ X_i = aX_{i-1} + c \bmod 2^n $$ implies $$ R_i = aR_{i-1} + c \bmod 2^k $$ In particular, $R_{i}$ is uniquely determined by $R_{i-1}$.

Consider $R_0, R_1, \cdots, R_{2^k}$, which are $2^k+1$ integers between $0$ and $2^k-1$. Thanks to Pigeonhole principle, two of them must be the same. Suppose they are $R_i$ and $R_j$, where $0\le i<j\le 2^k$.

  • $R_i=R_j$ implies $R_{i+1}=R_{j+1}$.
  • $R_{i+1}=R_{j+1}$ implies $R_{i+2}=R_{j+2}$.
  • $R_{i+2}=R_{j+2}$ implies $R_{i+3}=R_{j+3}$.
  • $\vdots$.

So the sequence $R_0, R_1, \cdots$ has a period of $j-i$, which is at most $2^k$.

$\endgroup$
1
  • 1
    $\begingroup$ I should have included the conditions "$R_{i-1} = X_{i-1} \bmod 2^k$" and "$R_i = X_i \bmod 2^k$" . $\ k\le n$ is assumed; otherwise $R_i=X_i$ is the same as in the case of $k=n$, which has been proved. $\endgroup$
    – Apass.Jack
    May 10, 2023 at 15:11

You must log in to answer this question.

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