Blum-Blum-Shub

Problem 375で使われている擬似乱数は

s_n+1 = s_n² mod d

ここで法dはd = pqでpとqは4n+3型の素数です。これをBlum-Blum-Shubというそうです。
知りたいのはこの数列が戻ってくるかです。まず、初項に戻ってこないかもしれないのは当然です。自乗の剰余になれない数があるからです。例えば、

(d - m)² = d² - 2dm + m² ≡ m² (mod d)

このようなペアがあるため、自乗の剰余になる数は約半分以下ということになります。
問題なのは2項目以降です。例えば、d = 77、s₀ = 5としてみましょう。

5 -> 25 -> 9 -> 4 -> 16 -> 25

周期4で第2項に帰ってくることがわかります。
一般に、第2項に帰ってくるというのは初項をaと書いて、

a²ⁿ ≡ a² (mod pq)

が成り立つn > 1があるということです。
もう一度例に戻って7と11の法について考えましょう。オイラーの定理から、

2^n_p ≡ 1 (mod 3)

が成り立つn_p > 0があります。2と(p - 1)/2が互いに素であることがポイントです。よって、

2^n_p+1 ≡ 2 (mod 6)

より、

5^2n_p+1 ≡ 5² (mod 7)

要するに、法7に対して周期n_pで25に帰ってくることになります。法11に対しても同様に周期n_qで25に帰ってくることになります。だから、法77でもある周期で帰ってきます。
あらためて一般的に書くまでもないですね。aがpとqのいずれに対しても互いに素なら上の議論が成り立ちます。

aがpの倍数なら、法pに関しては周期1、法qに関しては、aがqの倍数なら上の議論が成り立って、そうでなければ周期1で、やっぱり第2項に帰ってきます。

なぜこんなことを確認したかったかというと、Problem 375のコードを初期値に依存しないコードを書きたかったからです。第2項は必ず帰ってくるので、それを待っていればいいだけです。