Blum-Blum-Shub

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

sn+1 = sn2 mod d

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

(d - m)2 = d2 - 2dm + m2m2 (mod d)

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

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

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

a2na2 (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でもある周期で帰ってきます。
あらためて一般的に書くまでもないですね。apqのいずれに対しても互いに素なら上の議論が成り立ちます。

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

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