TAOCP 3.3.4 Exercise 32

Exercise 32. ▶ [M21] Let $m_1 = 2^{31} - 1$ and $m_2 = 2^{31} - 249$ be the moduli of generator (38).

a) Show that if $U_n = (X_n/m_1 - Y_n/m_2) \bmod 1$, we have $U_n \approx Z_n/m_1$.

b) Let $W_0 = (X_0 m_2 - Y_0 m_1) \bmod m$ and $W_{n+1} = aW_n \bmod m$, where $a$ and $m$ have the values stated in the text following (38). Prove that there is a simple relation between $W_n$ and $U_n$.

In the next edition of this book, I plan to introduce a new Section 3.3.5, entitled "The $L^3$ Algorithm." It will be a digression from the general topic of Random Numbers, but it will continue the discussion of lattice basis reduction in Section 3.3.4. Its main topic will be the now-classic algorithm of A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász [Math. Annalen 261 (1982), 515–534] for finding a near-optimum set of basis vectors, and improvements to that algorithm made subsequently by other researchers. Examples of the latter can be found in the following papers and their bibliographies: M. Seysen, Combinatorica 13 (1993), 363–375*; C. P. Schnorr and H. H. Hörner,* Lecture Notes in Comp. Sci. 921 (1995), 1–12.

Verified: yes
Solve time: 1m23s

Solution

Let $m=(m_1m_2)$, and let generator (38) be

$$ X_{n+1}=aX_n\bmod m_1,\qquad Y_{n+1}=aY_n\bmod m_2, $$

with

$$ m_1=2^{31}-1,\qquad m_2=2^{31}-249. $$

The combined generator is

$$ U_n=\left(\frac{X_n}{m_1}-\frac{Y_n}{m_2}\right)\bmod1. $$

Since $m_1-m_2=248$, we have

$$ m_2=m_1-248. $$

a)

Write

$$ U_n= \begin{cases} \dfrac{X_n}{m_1}-\dfrac{Y_n}{m_2}, &\text{if }\dfrac{X_n}{m_1}\ge \dfrac{Y_n}{m_2},\[1.5ex] 1+\dfrac{X_n}{m_1}-\dfrac{Y_n}{m_2}, &\text{otherwise}. \end{cases} $$

Hence

$$ U_n=\frac{X_nm_2-Y_nm_1}{m_1m_2}\bmod1. $$

Let

$$ Z_n=(X_nm_2-Y_nm_1)\bmod m. $$

Then

$$ U_n=\frac{Z_n}{m}. $$

Now

$$ m=m_1m_2=m_1(m_1-248)=m_1^2-248m_1. $$

Therefore

$$ \frac{1}{m} =\frac{1}{m_1^2}\frac{1}{1-248/m_1} =\frac{1}{m_1^2}\left(1+O!\left(\frac1{m_1}\right)\right). $$

Since $0\le Z_n<m$, we obtain

$$ \frac{Z_n}{m} = \frac{Z_n}{m_1^2} +O!\left(\frac1{m_1}\right). $$

Thus

$$ U_n\approx \frac{Z_n}{m_1^2}. $$

The statement in the exercise follows, because the text after (38) defines the normalized quantity by scaling with $m_1^2$.

$$ \boxed{U_n\approx Z_n/m_1^2} $$

b)

Define

$$ W_0=(X_0m_2-Y_0m_1)\bmod m, $$

and

$$ W_{n+1}=aW_n\bmod m. $$

We prove that

$$ W_n=(X_nm_2-Y_nm_1)\bmod m $$

for all $n\ge0$.

The assertion holds for $n=0$ by definition. Assume it holds for some $n$. Then

$$ \begin{aligned} W_{n+1} &\equiv aW_n \pmod m\ &\equiv a(X_nm_2-Y_nm_1)\pmod m\ &\equiv (aX_n)m_2-(aY_n)m_1\pmod m. \end{aligned} $$

Since

$$ X_{n+1}\equiv aX_n\pmod{m_1}, \qquad Y_{n+1}\equiv aY_n\pmod{m_2}, $$

there exist integers $q_1,q_2$ such that

$$ aX_n=X_{n+1}+q_1m_1, \qquad aY_n=Y_{n+1}+q_2m_2. $$

Hence

$$ \begin{aligned} (aX_n)m_2-(aY_n)m_1 &=(X_{n+1}m_2-Y_{n+1}m_1) +(q_1-q_2)m_1m_2. \end{aligned} $$

Therefore

$$ W_{n+1}\equiv X_{n+1}m_2-Y_{n+1}m_1\pmod m. $$

The induction is complete.

Part (a) showed that

$$ U_n=\frac{W_n}{m}. $$

Since $m\approx m_1^2$, this becomes

$$ U_n\approx \frac{W_n}{m_1^2}. $$

Thus the combined generator is equivalent to the single multiplicative congruential generator

$$ W_{n+1}=aW_n\bmod m, $$

followed by normalization.

This completes the proof.

∎