素因数分解アルゴリズム

同義語：素因数分解の算法integer factorization algorithmfactoring algorithm

概要

前提知識: 素因数分解, 計算整数論, Euclidの互除法, Fermatの小定理

素因数分解アルゴリズム（integer factorization algorithm）は、与えられた正の整数を素数の積に分解する手順（算法）である。合成数 $n$ から $1< d< n$ を満たす約数 $d$ を 1 つ見つける手順があれば、素数判定と組み合わせてくり返すことで、素因数分解の全体が得られる。素数かどうかの判定は桁数の多項式時間でできるのに対し、桁数の多項式時間で素因数分解する算法は知られていない。この差が RSA暗号の安全性の根拠になっている（計算整数論の注意「多項式時間で解ける問題と、難しいと考えられている問題」）。
この記事では、試し割り・Fermat 法・Pollard の $p-1$ 法・Pollard の $\rho$ 法の正しさと手間を証明する。$\rho$ 法については、$m$ 元の集合の無作為な写像の反復が平均 $\sqrt m$ 程度で値をくり返すことを証明し、これが経験的な評価の根拠であることを説明する。ふるい法の手間は引用する。

定義

分解の問題と素因数分解アルゴリズム

合成数 $n$ を入力とし、$1< d< n$ かつ $d\mid n$ を満たす整数 $d$（自明でない約数）を 1 つ出力する問題を 分解の問題 という。整数 $n\ge2$ を入力とし、素数 $p_1\le\dots\le p_r$ で $n=p_1\cdots p_r$ となるもの（素因数分解）を出力する問題を 素因数分解の問題 という。これらを解く算法を 素因数分解アルゴリズム といい、算法が自明でない約数を出力することを「$n$ を 分解する」という。

手間は計算整数論と同じく、入力のビット長 $\operatorname{len}(n)=\lfloor\log_2n\rfloor+1$ で測る（同記事の定義「ビット長」）。$0\le a,b< n$ の積を $n$ で割った余りと、$\gcd(a,n)$ は、どちらも時間 $O(\operatorname{len}(n)^2)$ で求まる（同記事の注意「基本演算の手間」と定理「互除法の手間」）。$\sqrt n=2^{\operatorname{len}(n)/2}$ 回程度の操作が要る算法は、ビット長について指数関数的に遅い。

分解から素因数分解へ

分解の問題を解く算法 $A$ と、素数かどうかを判定する算法があるとする。$n\ge2$ を正の整数の積として持ち、素数でない因子を $A$ で 2 つの因子に置き換えることをくり返すと、$A$ を高々 $\log_2n-1$ 回使ったところで $n$ の素因数分解が得られる。

要点：置き換えるたびに因子が 1 つ増え、因子はどれも $2$ 以上なので、因子の個数は $\log_2n$ を超えない。

詳しい証明を開く

$n=m_1\cdots m_s$（各 $m_i\ge2$）と持ち、素数でない $m_i$ を $A$ の出力 $d$ により $d$ と $m_i/d$（どちらも $2$ 以上）に置き換える。置き換えるたびに因子の個数 $s$ は 1 増え、各因子は $2$ 以上なので $2^s\le n$、すなわち $s\le\log_2n$ である。最初は $s=1$ なので、置き換えは高々 $\log_2n-1$ 回で終わり、終わったときにはすべての因子が素数である。$\square$

素数判定は多項式時間でできるので（素数判定法）、以下では分解の問題を解く算法を扱う。

直感

$n$ の素因数 $p$ は未知だが、$p\mid n$ なので、法 $n$ で数列を計算すればその法 $p$ での像も同時に計算したことになる。ある差 $x-y$ が法 $p$ で $0$ になった瞬間は、$p$ を知らなくても $\gcd(x-y,n)>1$ として検出できる。$p-1$ 法は Fermat の小定理を、$\rho$ 法は法 $p$ での数列が有限集合の中で必ず値をくり返すことを、この仕組みで使う。Fermat 法は $n$ を平方数の差 $t^2-s^2=(t-s)(t+s)$ に書く。算法ごとに「見つけやすい約数」の型が違い、RSA 暗号の法 $n=pq$ はこれらの型を避けて選ぶ。

例

主な算法と手間

$p$ は $n$ の最小の素因数とする。

算法	見つけやすい約数	手間の目安	所在
試し割り	小さい素因数	割り算 $p-1$ 回（最悪 $\sqrt n$ 回）	prop-ifa-trial
Fermat 法	$\sqrt n$ に近い約数	平方判定 $(\sqrt v-\sqrt u)^2/2+1$ 回以下	thm-ifa-fermat
$p-1$ 法	$p-1$ が $B$-冪滑らかな素因数	時間 $O(B\log B\cdot\operatorname{len}(n)^2)$	thm-ifa-pm1
$\rho$ 法	小さい素因数	経験的に反復 $\sqrt p$ 回程度	thm-ifa-rho、thm-ifa-birthday
2 次ふるい法	大きさによらない	経験的に $L_n[1/2,1]$	rem-ifa-subexp
数体ふるい法	大きさによらない	経験的に $L_n[1/3,c]$	rem-ifa-subexp

表の $u,v$、$B$-冪滑らか、$L_n[\alpha,c]$ はそれぞれ thm-ifa-fermat、def-ifa-smooth、rem-ifa-subexp で定める。

試し割り

$n\ge2$ について、$d=2,3,\dots,\lfloor\sqrt n\rfloor$ の順に $d\mid n$ かどうかを調べる。

最初に見つかる $d$ は $n$ の最小の素因数である。
どの $d$ も $n$ を割らなければ、$n$ は素数である。
割り算は高々 $\sqrt n$ 回で、手間は時間 $O(\sqrt n\operatorname{len}(n)^2)$ である。

要点：最初に割り切る $d$ より小さい約数はないので $d$ は素数であり、合成数 $n=ab$（$2\le a\le b$）では $a\le\sqrt n$ である。

詳しい証明を開く

1：$d\mid n$ で、$d$ が $1 < e < d$ を満たす約数 $e$ をもつなら $e\mid n$ なので、$e$ の段階で先に止まっている。よって $d$ は素数で、$d$ より小さい $n$ の約数で $1$ より大きいものはない。2：$n$ が合成数なら $n=ab$（$2\le a\le b$）と書け、$a^2\le ab=n$ から $a\le\lfloor\sqrt n\rfloor$ なので、$a$ 以下のどこかで止まる。3：割り算の回数は $\lfloor\sqrt n\rfloor-1$ 以下で、$d\le n$ による割り算は商のビット長が $\operatorname{len}(n)$ 以下なので時間 $O(\operatorname{len}(n)^2)$ である。$\square$

試し割りは大きい素因数しかもたない $n$ では指数関数的に遅いが、小さい素因数を除く前処理として使われる。

Fermat 法

$n\ge3$ を奇数とする。Fermat 法 は、$t_0:=\lceil\sqrt n\,\rceil$ から始めて $t=t_0,t_0+1,t_0+2,\dots$ の順に $t^2-n$ が平方数 $s^2$（$s\ge0$）かどうかを調べ、初めて平方数になったところで $t-s$ と $t+s$ を出力する算法である。$t^2-s^2=(t-s)(t+s)$ なので、出力の積は $n$ である。

Fermat 法の正しさと調べる回数

$n\ge3$ を奇数とし、$\sqrt n$ 以下の $n$ の約数のうち最大のものを $u$、$v:=n/u$ とする。

整数の組 $(u',v')$ で $u'v'=n$、$1\le u'\le v'$ を満たすものと、整数の組 $(t,s)$ で $t^2-s^2=n$、$t\ge1$、$s\ge0$ を満たすものは、$t=(u'+v')/2$、$s=(v'-u')/2$ によって一対一に対応する。
Fermat 法は $t=(u+v)/2$ で止まり、$u$ と $v$ を出力する。調べる $t$ の個数は $(\sqrt v-\sqrt u)^2/2+1$ 以下である。
$n$ が合成数なら、出力の $u$ は $n$ の自明でない約数である。$n$ が素数なら、Fermat 法は $t=(n+1)/2$ まで止まらない。

1：$n$ は奇数なので $u',v'$ も奇数で、$t=(u'+v')/2$ と $s=(v'-u')/2$ は整数であり、$t\ge1$、$s\ge0$、$t^2-s^2=u'v'=n$ を満たす。逆に $(t,s)$ が条件を満たせば、$u':=t-s$、$v':=t+s$ は $u'v'=n$、$u'\le v'$ を満たし、$v'=t+s\ge1>0$ と $u'v'=n>0$ から $u'\ge1$ である。2 つの対応は互いに逆である。
2：$h(x):=x+n/x$ は $0< x\le\sqrt n$ で狭義単調減少である（$0< x< y\le\sqrt n$ なら $h(x)-h(y)=(y-x)(n-xy)/(xy)>0$）。1 により、$t^2-n$ が平方数になる $t\ge1$ は、$\sqrt n$ 以下の約数 $u'$ について $t=h(u')/2$ と書ける値の全体である。相加相乗平均の不等式から、どの $u'$ でも $h(u')/2\ge\sqrt{u'\cdot n/u'}=\sqrt n$ で、$t$ は整数なので $t\ge t_0$ である。よって Fermat 法が最初に止まる $t$ は、これらの値の最小値 $h(u)/2=(u+v)/2$ であり（$h$ は狭義単調減少で、$u$ は最大の $u'$）、そのとき $s=\sqrt{t^2-n}=(v-u)/2$ なので出力は $t-s=u$、$t+s=v$ である。調べる個数は
$$ \frac{u+v}2-t_0+1\le\frac{u+v}2-\sqrt{uv}+1=\frac{(\sqrt v-\sqrt u)^2}2+1 $$
である（$t_0\ge\sqrt n=\sqrt{uv}$）。
3：$n$ が合成数なら $n=ab$（$2\le a\le b$）と書け、$a\le\sqrt n$ なので $u\ge a\ge2$、また $u\le\sqrt n< n$ である。$n$ が素数なら $\sqrt n$ 以下の約数は $1$ だけなので $u=1$、$v=n$ で、2 により $t=(n+1)/2$ で止まる。$\square$

とくに $(v-u)^2<8\sqrt n$ なら、$(\sqrt v-\sqrt u)^2=(v-u)^2/(\sqrt v+\sqrt u)^2\le(v-u)^2/(4\sqrt{uv})$ により調べる個数は $1$ 以下、すなわち最初の $t=t_0$ で止まる。RSA 暗号の法 $n=pq$ の $p,q$ が近すぎると、Fermat 法で直ちに分解される（Ste17 §3.4.2、pp. 62–63 に $n=23360947609=152041\cdot153649$ が 3 回目の $t$ で分解される例がある）。

$n=5959$ の Fermat 法

$77^2=5929<5959<6084=78^2$ なので $t_0=78$ である。$78^2-5959=125$、$79^2-5959=282$ は平方数でなく、$80^2-5959=441=21^2$ である。よって $5959=(80-21)(80+21)=59\cdot101$ である。thm-ifa-fermat の評価は $(\sqrt{101}-\sqrt{59})^2/2+1=3.80\ldots$ で、実際に調べた個数 $3$ はこれ以下である。

Pollard の $p-1$ 法

冪滑らか

$B\ge2$ を整数とする。正の整数 $m$ の素因数分解 $m=\prod_qq^{e_q}$ に現れる素数冪 $q^{e_q}$（$e_q\ge1$）がすべて $B$ 以下であるとき、$m$ は $B$-冪滑らか（$B$-power smooth）であるという。$M_B:=\operatorname{lcm}(1,2,\dots,B)$ とおく。

たとえば $60=2^2\cdot3\cdot5$ は $5$-冪滑らかであり、$96=2^5\cdot3$ は $2^5=32$ を含むので $31$-冪滑らかではないが $32$-冪滑らかである。

$1$ から $B$ までの最小公倍数

$B\ge2$ について次が成り立つ。

$M_B=\prod_{q\le B}q^{\lfloor\log_qB\rfloor}$ である（積は $B$ 以下の素数 $q$ にわたる）。
正の整数 $m$ が $M_B$ を割ることと、$m$ が $B$-冪滑らかであることは同値である。
$\log_2M_B\le B\log_2B$ である。

要点：$M_B$ での素数 $q$ の指数は、$B$ 以下の $q$ の冪の指数の最大値である。

詳しい証明を開く

1：素数 $q$ について、$M_B$ での $q$ の指数は $1\le k\le B$ での $k$ の $q$ の指数の最大値である。$k\le B$ なら $q^{v_q(k)}\le k\le B$ なので、その最大値は $q^e\le B$ を満たす最大の $e$、すなわち $\lfloor\log_qB\rfloor$ で、$k=q^e$ で達成される。$q > B$ なら指数は $0$ である。2：$m\mid M_B$ は、$m$ を割る各素数 $q$ について $v_q(m)\le\lfloor\log_qB\rfloor$、すなわち $q^{v_q(m)}\le B$ となることと同値である。3：1 の各因子は $B$ 以下で、因子の個数は $B$ 以下なので $M_B\le B^B$ である。$\square$

$p-1$ 法 は、限界 $B$ と $\gcd(a,n)=1$ を満たす整数 $a$（たとえば $a=2$）を選び、$x:=a^{M_B}\bmod n$ を反復二乗法で求め、$g:=\gcd(x-1,n)$ を出力する算法である。$x-1\equiv a^{M_B}-1\pmod n$ なので $g=\gcd(a^{M_B}-1,n)$ である。

$p-1$ 法の正しさと手間

$n\ge2$ と $M\ge1$ を整数、$a$ を $\gcd(a,n)=1$ を満たす整数とし、$g:=\gcd(a^M-1,n)$ とおく。

$p$ が $n$ の素因数で $p-1\mid M$ なら、$p\mid g$ である。
$g=n$ であることは、$n$ の素因数分解に現れるすべての素数冪 $q^e$ について $a^M\equiv1\pmod{q^e}$ となることと同値である。とくに、$n$ のある素因数 $q$ について $a$ の法 $q$ での位数が $M$ を割らなければ、$g< n$ である。
$M=M_B$ のとき、$g$ は時間 $O(B\log B\cdot\operatorname{len}(n)^2)$ で求まる（$M_B$ を求める手間は除く）。
したがって、$n$ のある素因数 $p$ について $p-1$ が $B$-冪滑らかで、別のある素因数 $q$ について $a$ の法 $q$ での位数が $M_B$ を割らなければ、$p-1$ 法は $n$ を分解する。

1：$\gcd(a,n)=1$ なので $p\nmid a$ であり、Fermatの小定理により $a^{p-1}\equiv1\pmod p$ である。$M=(p-1)k$ と書けば $a^M=(a^{p-1})^k\equiv1\pmod p$ なので、$p$ は $a^M-1$ と $n$ の両方を割り、$p\mid g$ である。
2：$g=n$ は $n\mid a^M-1$ と同値である。$n=\prod q^e$ の素数冪は互いに素なので、これは各 $q^e$ が $a^M-1$ を割ることと同値である。$a$ の法 $q$ での位数が $M$ を割らなければ $a^M\not\equiv1\pmod q$ なので、$q^e\nmid a^M-1$ であり $g\ne n$ である。
3：計算整数論の定理「反復二乗法の正しさと手間」により、$a^M\bmod n$ は時間 $O(\operatorname{len}(M)\operatorname{len}(n)^2)$ で求まる。lem-ifa-lcm の 3 により $\operatorname{len}(M_B)\le B\log_2B+1$ である。最後の $\gcd$ は時間 $O(\operatorname{len}(n)^2)$ である。
最後の主張は、lem-ifa-lcm の 2 により $p-1\mid M_B$ なので 1 から $p\mid g$、2 から $g< n$ による。$\square$

すべての素因数 $p$ で $p-1$ が大きい素数を含むと、現実的な $B$ では分解できない。$p-1$ 法の発想を楕円曲線の有理点の群に移し、群の位数が曲線ごとに変わることを使うのが Lenstra の楕円曲線法である（Ste17 §6.3、pp. 129、133）。

$n=5917$ と $B=5$

$n=5917=61\cdot97$、$B=5$、$M_5=60$、$a=2$ とする。$61-1=60$ は $M_5$ を割るので、thm-ifa-pm1 の 1 により $61\mid g$ である。一方 $97-1=96=2^5\cdot3$ は $5$-冪滑らかでなく、$2$ の法 $97$ での位数は $48$ で $60$ を割らない（位数は $96$ の約数で、$2^{48}\equiv1$、$2^{24}\equiv-1$、$2^{16}\equiv61\pmod{97}$ なので、$48$ を割り $24$ も $16$ も割らない約数、すなわち $48$ である）。よって $g< n$ で、実際 $2^{60}\equiv3417\pmod{5917}$、$g=\gcd(3416,5917)=61$ である。この例は Ste17 の Example 6.3.5（p. 131）と同じ数である。

Pollard の $\rho$ 法

整数係数の多項式 $f$（ふつうは $f(x)=x^2+c$、$c\ne0,-2$）と初期値 $x_0$ を選び、
$$ X_0:=x_0\bmod n,\qquad X_{i+1}:=f(X_i)\bmod n $$
とおく。$\rho$ 法 は、$k=1,2,3,\dots$ の順に $X_k$ と $X_{2k}$ を計算し、$d:=\gcd(X_{2k}-X_k,n)>1$ となった最初の $k$ で $d$ を出力する算法である。$Y_k:=X_{2k}$ は $Y_k=f(f(Y_{k-1}))$ で求まるので、各段で $f$ を $3$ 回計算すればよい。$X_k$ と $X_{2k}$ を比べる方法は Floyd の方法と呼ばれる。

反復の形

$S$ を有限集合、$g\colon S\to S$ を写像、$x_0\in S$ とし、$x_{i+1}:=g(x_i)$ とおく。$x_T\in\{x_0,\dots,x_{T-1}\}$ となる最小の $T\ge1$ をとり、$x_T=x_\mu$（$0\le\mu< T$）、$\lambda:=T-\mu$ とおく。

$T\le\lvert S\rvert$ であり、$x_0,\dots,x_{T-1}$ は相異なり、$i\ge\mu$ なら $x_{i+\lambda}=x_i$ である。
$i\ne j$ について、$x_i=x_j$ となるのは $i,j\ge\mu$ かつ $i\equiv j\pmod\lambda$ のときに限る。
$k\ge1$ について、$x_{2k}=x_k$ となるのは $k\ge\mu$ かつ $\lambda\mid k$ のときに限る。このような最小の $k$ を $k^*$ とすると $k^*\le T$ である。

要点：最初にくり返す値で数列は「尾」と「輪」に分かれ、輪の上では添字を $\lambda$ を法として見ればよい。

詳しい証明を開く

1：$T$ の最小性から $x_0,\dots,x_{T-1}$ は相異なり、それらは $S$ の元なので $T\le\lvert S\rvert$ である。$x_{\mu+\lambda}=x_T=x_\mu$ の両辺に $g$ を $j$ 回施すと $x_{\mu+j+\lambda}=x_{\mu+j}$ を得る。

2：$i,j\ge\mu$、$i\equiv j\pmod\lambda$ なら 1 を繰り返し使って $x_i=x_j$ である。逆を示す。添字 $m\ge\mu$ を、$m\equiv m'\pmod\lambda$ を満たす $m'\in\{\mu,\dots,T-1\}$ に取り替えても 1 により値は変わらず、$m < \mu$ ならそのままにする。この取り替えを $\bar m$ と書くと、$x_i=x_j$ から $x_{\bar i}=x_{\bar j}$ で、$\bar i,\bar j\le T-1$ なので 1 により $\bar i=\bar j$ である。$i < \mu$ なら $\bar i=i < \mu$ なので $\bar j < \mu$、よって $j=\bar j=i$ となり $i\ne j$ に反する。同様に $j < \mu$ もありえない。よって $i,j\ge\mu$ で、$\bar i=\bar j$ から $i\equiv j\pmod\lambda$ である。

3：$k\ne2k$ なので、2 を $i=k$、$j=2k$ に使う。$2k-k=k$ なので条件は $k\ge\mu$ かつ $\lambda\mid k$ である。$\max(\mu,1)$ 以上の $\lambda$ の倍数のうち最小のものが $k^*$ で、$\lambda$ 個の連続する整数 $\max(\mu,1),\dots,\max(\mu,1)+\lambda-1$ の中に $\lambda$ の倍数があるので $k^*\le\max(\mu,1)+\lambda-1\le\mu+\lambda=T$ である。$\square$

数列 $x_0,x_1,\dots$ は長さ $\mu$ の「尾」のあと長さ $\lambda$ の「輪」を回り、図にするとギリシア文字 $\rho$ の形になる。これが名前の由来である。

$\rho$ 法の正しさ

$n\ge2$、$f$ を整数係数の多項式、$p$ を $n$ の素因数とする。法 $p$ への還元 $r\colon\mathbb{Z}/n\mathbb{Z}\to\mathbb{Z}/p\mathbb{Z}$ について、$r(X_0),r(X_1),\dots$ は、$\mathbb{Z}/p\mathbb{Z}$ 上の写像 $\bar f(x):=f(x)\bmod p$ を $r(X_0)$ から反復した数列である。この数列に lem-ifa-rho-shape を当てたときの $\mu,\lambda,T,k^*$ を $\mu_p,\lambda_p,T_p,k^*_p$ とする。

$k\ge1$ について、$p\mid\gcd(X_{2k}-X_k,n)$ となるのは $k\ge\mu_p$ かつ $\lambda_p\mid k$ のときに限る。
$\rho$ 法は、ある $k\le k^*_p\le T_p\le p$ で止まり、$n$ の $1$ より大きい約数 $d$ を出力する。
各段の手間は時間 $O(\operatorname{len}(n)^2)$ である。

要点：$p\mid n$ なので法 $n$ の数列を法 $p$ に還元すると $\bar f$ の反復になり、$p\mid X_{2k}-X_k$ は法 $p$ の数列で $x_{2k}=x_k$ となることと同じである。

詳しい証明を開く

$p\mid n$ なので $r$ は環準同型であり、$f$ は整数係数なので $r(f(X))=\bar f(r(X))$ である。よって $r(X_{i+1})=\bar f(r(X_i))$ で、前半の主張が成り立つ。

1：$p\mid n$ なので、$p\mid\gcd(X_{2k}-X_k,n)$ は $p\mid X_{2k}-X_k$、すなわち $r(X_{2k})=r(X_k)$ と同値であり、lem-ifa-rho-shape の 3 により $k\ge\mu_p$ かつ $\lambda_p\mid k$ と同値である。

2：1 により $k=k^*_p$ では $\gcd\ge p > 1$ なので、$\rho$ 法はそれまでに止まる。止まったときの $d$ は $n$ の約数で $d > 1$ である。$k^*_p\le T_p\le\lvert\mathbb{Z}/p\mathbb{Z}\rvert=p$ は lem-ifa-rho-shape の 1 と 3 による。

3：各段では $f$ の法 $n$ での計算 $3$ 回、引き算 $1$ 回、$\gcd$ $1$ 回を行い、$f$ は固定した多項式なので、いずれも時間 $O(\operatorname{len}(n)^2)$ である。$\square$

thm-ifa-rho だけでは、最小の素因数 $p$ について段数が $p$ 以下であることしか保証されず、試し割りより速いとはいえない。また、止まったときの $d$ が $n$ に等しいこともある（ex-ifa-rho-299）。$\rho$ 法の速さの根拠は、次の定理である。

無作為な写像の反復の長さ

$S$ を $m$ 個の元からなる集合、$x_0\in S$ とし、$S$ から $S$ への写像 $g$ を $m^m$ 個のうちから一様に無作為に選ぶ。lem-ifa-rho-shape の $T$（数列 $x_i$ に現れる相異なる値の個数）について、整数 $k\ge0$ ごとに
$$ P(T>k)=\prod_{i=1}^{k}\Bigl(1-\frac im\Bigr)\le\exp\Bigl(-\frac{k(k+1)}{2m}\Bigr) $$
であり（$k\ge m$ なら左辺は $0$）、
$$ E[T]\le1+\sqrt{\frac{\pi m}2} $$
である。とくに Floyd の方法で $x_{2k}=x_k$ となる最小の $k^*$ の期待値も $1+\sqrt{\pi m/2}$ 以下である。

一様に無作為な写像は、各点 $s\in S$ での値 $g(s)$ を互いに独立に $S$ から一様に選んだものと同じである。$T>k$ は $x_0,\dots,x_k$ が相異なることと同値なので（$T$ は値が初めてくり返す添字）、その事象を $E_k$ とおく。$E_0$ はつねに成り立つ。
$0\le j< k$ とし、$E_j$ を、$x_1=a_1,\dots,x_j=a_j$（$x_0,a_1,\dots,a_j$ は相異なる）という事象 $A$ に分ける。$A$ は $g(x_0)=a_1,g(a_1)=a_2,\dots,g(a_{j-1})=a_j$ という条件で、相異なる $j$ 点 $x_0,a_1,\dots,a_{j-1}$ での $g$ の値だけで決まる。$a_j$ はこれらと異なる点なので、$g(a_j)$ は $A$ と独立に一様に分布し、$A$ のもとで $x_{j+1}=g(a_j)$ が $\{x_0,a_1,\dots,a_j\}$ の $j+1$ 点を避ける確率は $1-(j+1)/m$ である。$A$ について足し合わせると $P(E_{j+1})=P(E_j)\bigl(1-(j+1)/m\bigr)$ を得て、等式が従う。不等式は $1-t\le e^{-t}$ と $\sum_{i=1}^ki=k(k+1)/2$ による。
$T$ は正の整数値をとるので $E[T]=\sum_{k\ge0}P(T>k)$ であり、$k(k+1)\ge k^2$ と、$x\mapsto e^{-x^2/(2m)}$ が $x\ge0$ で単調減少であることから
$$ E[T]\le\sum_{k\ge0}e^{-k^2/(2m)}\le1+\int_0^\infty e^{-x^2/(2m)}\,dx=1+\sqrt{\frac{\pi m}2} $$
である（$k\ge1$ の項は $\int_{k-1}^ke^{-x^2/(2m)}\,dx$ 以下）。最後の主張は lem-ifa-rho-shape の 3 の $k^*\le T$ による。$\square$

$\rho$ 法では、法 $p$ での写像 $\bar f(x)=x^2+c$ をこの定理の $g$ に見立てる。$\bar f$ は無作為な写像ではなく（たとえば $\bar f(x)=\bar f(-x)$）、thm-ifa-birthday を当てはめることは証明されていない。しかし多くの $c$ で経験的に無作為な写像と同じように振る舞い、$k^*_p$ はおよそ $\sqrt p$ の程度になる（Cri24 §12.6.1、pp. 206–207 も、$\rho$ 法には一般の証明がなく、最小の素因数の平方根の程度の段数で成功すると期待されることを述べている）。この見積もりのもとで、$p$ を $n$ の最小の素因数とすると $p\le\sqrt n$ なので、手間は時間 $O(\sqrt p\operatorname{len}(n)^2)\subset O(n^{1/4}\operatorname{len}(n)^2)$ になる。

$n=8051$ の $\rho$ 法

$n=8051=83\cdot97$、$f(x)=x^2+1$、$x_0=2$ とする。
$$ (X_1,X_2)=(5,26),\quad(X_2,X_4)=(26,7474),\quad(X_3,X_6)=(677,871) $$
で、$\gcd(21,8051)=\gcd(7448,8051)=1$、$\gcd(194,8051)=97$ なので $k=3$ で $97$ が出力される。法 $97$ での数列は $2,5,26,95,5,26,95,\dots$ で $\mu_{97}=1$、$\lambda_{97}=3$、$k^*_{97}=3$ であり、法 $83$ での数列は $2,5,26,13,4,17,41,22,70,4,\dots$ で $\mu_{83}=4$、$\lambda_{83}=5$、$k^*_{83}=5$ である。thm-ifa-rho の 1 のとおり、$k=3$ では $97$ だけが差を割る。

$\rho$ 法が $n$ そのものを出力する例

$n=299=13\cdot23$、$f(x)=x^2+1$、$x_0=2$ とする。法 $13$ での数列は $2,5,0,1,2,\dots$ で $\mu_{13}=0$、$\lambda_{13}=4$、$k^*_{13}=4$、法 $23$ での数列は $2,5,3,10,9,13,9,\dots$ で $\mu_{23}=4$、$\lambda_{23}=2$、$k^*_{23}=4$ である。$k=1,2,3$ ではどちらの条件も満たされず $\gcd=1$、$k=4$ では両方が同時に満たされて $\gcd(X_8-X_4,299)=299$ になる。このときは $c$ か $x_0$ を取り替えてやり直す。

平方の合同とふるい法

現在の大きな整数の分解に使われる算法は、次の単純な事実に基づく。

平方の合同からの分解

$n\ge2$ と整数 $x,y$ が $x^2\equiv y^2\pmod n$、$x\not\equiv\pm y\pmod n$ を満たすなら、$\gcd(x-y,n)$ は $n$ の自明でない約数である。

要点：$n$ は $(x-y)(x+y)$ を割るが、$x-y$ も $x+y$ も割らない。

詳しい証明を開く

$d:=\gcd(x-y,n)$ とおく。$n\nmid x-y$ なので $d < n$ である。$d=1$ なら、$n\mid(x-y)(x+y)$ と $\gcd(x-y,n)=1$ から $n\mid x+y$ となり（Bézoutの等式により $1=a(x-y)+bn$ と書けるので、$x+y=a(x-y)(x+y)+bn(x+y)$ は $n$ で割り切れる）、$x\equiv-y\pmod n$ に反する。よって $1 < d < n$ である。$\square$

Fermat 法は $x^2-n=y^2$、すなわち $x^2\equiv y^2\pmod n$ を整数の等式として探す特別な場合である。Dixon の方法や 2 次ふるい法は、小さい素数だけで割り切れる数（滑らかな数）になる $x^2\bmod n$ をたくさん集め、それらの積が平方数になる組み合わせを、指数の偶奇の 1 次方程式（$\mathbb{F}_2$ 上の連立 1 次方程式）として求めて $x^2\equiv y^2\pmod n$ を作る。

劣指数時間の算法（この記事では証明しない）

$L_n[\alpha,c]:=\exp\bigl((c+o(1))(\log n)^\alpha(\log\log n)^{1-\alpha}\bigr)$ とおく。$\alpha=0$ なら $\log n$ の多項式、$\alpha=1$ なら $n$ の冪の程度で、$0<\alpha<1$ の手間を 劣指数時間 という。次の評価はこの記事では証明しない。

Dixon の方法の変種（Sho08 の Algorithm SEF）は、$n$ が奇数の合成数で $a^b$（$a,b\ge2$）の形でないとき（小さい素因数は試し割りで先に除く）、乱数を使って期待値 $L_n[1/2,2\sqrt2]$ の時間で動き、確率 $1/2$ 以上で $n$ を分解することが証明されている（Sho08 §15.3、p. 412 と Lemma 15.5）。
Pomerance の 2 次ふるい法は、経験的な見積もりで時間 $L_n[1/2,1]$ で分解する（Sho08 §15.4.2、p. 418）。同じ $L_n[1/2,1]$ の評価は、Lenstra と Pomerance の算法では証明されている（Sho08 §15.5、p. 419）。
Lenstra の楕円曲線法は、最小の素因数 $p$ について、経験的に期待値 $\exp\bigl((\sqrt2+o(1))(\log p\log\log p)^{1/2}\bigr)\operatorname{len}(n)^{O(1)}$ の時間で $p$ を見つける（Sho08 §15.5、p. 419）。
数体ふるい法は、経験的に期待値 $L_n[1/3,c]$ の時間で分解し、Coppersmith の改良で $c=1.902$ にできる（Sho08 §15.5、p. 419）。漸近的には知られている中で最も速く、RSA 暗号の公開された大きな法の分解に使われてきた（Ste17 §1.1.3、p. 10）。
ここで「経験的」とは、thm-ifa-birthday を $\rho$ 法に当てはめるときと同じように、算法の中の数が無作為な数と同じように振る舞うという証明されていない仮定のもとでの見積もりであることを表す。

反例：条件を外すと成り立たない

外す条件	反例	成り立たなくなること
ある素因数 $p$ で $p-1\mid M$（thm-ifa-pm1 の 1）	$n=253=11\cdot23$、$M=M_3=6$、$a=2$	$g>1$。実際は $g=1$
ある素因数 $q$ で $a$ の位数が $M$ を割らない（thm-ifa-pm1 の 2）	$n=91=7\cdot13$、$M=M_4=12$、$a=2$	$g< n$。実際は $g=91$
$n$ が奇数（thm-ifa-fermat）	$n=6$	停止すること
$g$ が一様に無作為な写像（thm-ifa-birthday）	$S=\mathbb{Z}/m\mathbb{Z}$（$m\ge4$）、$g(x)=x+1$、$x_0=0$	$E[T]\le1+\sqrt{\pi m/2}$。実際は $T=m$

反例の確認

各反例の確認を開く

$11-1=10$ と $23-1=22$ はどちらも $6$ を割らない。$2^6-1=63=3^2\cdot7$ なので $g=\gcd(63,253)=1$ で、$p-1$ 法は約数を見つけない。
$7-1=6$ と $13-1=12$ はどちらも $12$ を割るので、Fermatの小定理により $2^{12}\equiv1$ が法 $7$ でも法 $13$ でも成り立ち、$91\mid2^{12}-1=4095=91\cdot45$ である。よって $g=91$ で自明な約数しか得られない。
$t^2-6=s^2$ なら $(t-s)(t+s)=6$ である。$t-s$ と $t+s$ は差が $2s$ で偶奇が等しいので、積は奇数か $4$ の倍数であり、$6$ にはならない。よって $t^2-6$ はどの $t$ でも平方数にならず、Fermat 法は止まらない。
$x_i=i\bmod m$ なので $x_0,\dots,x_{m-1}$ は相異なり $x_m=x_0$ で、$T=m$ である。$m\ge4$ なら $1+\sqrt{\pi m/2}< m$ である（$m=4$ で $1+\sqrt{2\pi}=3.50\ldots$ で、差 $m-1-\sqrt{\pi m/2}$ は $m$ について増加する）。決まった写像では、反復が値をくり返すまでの長さは $\sqrt m$ の程度とは限らない。

補足

素因数分解と RSA 暗号

RSA 暗号の法 $n=pq$ では、$\varphi(n)$ が分かれば $p,q$ が求まる（RSA暗号の命題「$\varphi(n)$ と素因数分解の同値性」）。この記事の算法を避けるため、$p,q$ は同じ程度の大きさで差が大きく、$p-1$ と $q-1$ が大きい素因数をもつように選ばれる。