Problem 375で使われている擬似乱数は
sn+1 = sn2 mod d
ここで法dはd = pqでpとqは4n+3型の素数です。これをBlum-Blum-Shubというそうです。
知りたいのはこの数列が戻ってくるかです。まず、初項に戻ってこないかもしれないのは当然です。自乗の剰余になれない数があるからです。例えば、
(d - m)2 = d2 - 2dm + m2 ≡ m2 (mod d)
このようなペアがあるため、自乗の剰余になる数は約半分以下ということになります。
問題なのは2項目以降です。例えば、d = 77、s0 = 5としてみましょう。
5 -> 25 -> 9 -> 4 -> 16 -> 25
周期4で第2項に帰ってくることがわかります。
一般に、第2項に帰ってくるというのは初項をaと書いて、
a2n ≡ a2 (mod pq)
が成り立つn > 1があるということです。
もう一度例に戻って7と11の法について考えましょう。オイラーの定理から、
2np ≡ 1 (mod 3)
が成り立つnp > 0があります。2と(p - 1)/2が互いに素であることがポイントです。よって、
2np+1 ≡ 2 (mod 6)
より、
52np+1 ≡ 52 (mod 7)
要するに、法7に対して周期npで25に帰ってくることになります。法11に対しても同様に周期nqで25に帰ってくることになります。だから、法77でもある周期で帰ってきます。
あらためて一般的に書くまでもないですね。aがpとqのいずれに対しても互いに素なら上の議論が成り立ちます。
aがpの倍数なら、法pに関しては周期1、法qに関しては、aがqの倍数なら上の議論が成り立って、そうでなければ周期1で、やっぱり第2項に帰ってきます。
なぜこんなことを確認したかったかというと、Problem 375のコードを初期値に依存しないコードを書きたかったからです。第2項は必ず帰ってくるので、それを待っていればいいだけです。