フェルマーの小定理は、任意の素数 n と、a ≠ 0 (mod n) である自然数とから、an-1 = 1 となることを言うものです。 x の初期値を 1 とし、x := (x * a) mod n という演算を繰り返した結果、1～n-1 の範囲の全ての数を経巡って n-1 回目に 1 に戻る数列は疑似乱数の生成に利用されます。 しかし、実はそういう場合ばかりではなく、n-1 回目より前に何度か 1 に戻ってしまうケースもあります。 最初に 1 に戻るのを pcycle 回目とすると、pcycle 回毎に 1 に戻るわけですから、pcycle は n-1 の約数です。 例えば、ｎ=13 の場合の各数列は次のような感じになります。
以上のことを念頭に pcycle の可能性を絞ると、その高速計算ができます。 n-1 の約数を求める因数分解は、その平方根までの可能性と残った商をチェックすれば良いのは、前回ご説明したことの応用になります。
また、可能性が絞られた場合の掛算は、必ずしも回数分の繰り返しは要りません。
x の初期値を a とし、x := (x * x) mod n という演算を q 回繰り返すとこれで、
が得られ、これは、2q 回の掛算を繰り返したのと同じ結果です。
こうして 2 の累乗回は少ない回数で求められ、一般の乗回数は 2 進展開して応用できます。
ここにご紹介するのは、n と a とから pcycle を求める、見た目はこんな感じのプログラムで、素数を見つける前回のツールと組合せ、適当な n と a を見つけることができます。 計算例を幾つか挙げておきます。
プログラムです。