第3章素因数分解と離散対数

この章の目標

• 素因数分解と離散対数のアルゴリズムの速さを $L$ 記法で比べ、指数時間と準指数時間の違いを説明できる
• フェルマー法・ポラードの $\rho$ 法・$p - 1$ 法が成功する条件を証明し、RSA の素数に課される条件の理由を説明できる
• 二次ふるい法の仕組み（平方の合同、滑らかな数、$\mathbb{F}_2$ 上の線形代数）を小さい数で実行できる
• ベビーステップ・ジャイアントステップ法とポーリッヒ–ヘルマン法を証明し、離散対数の難しさが群の位数の最大の素因数で決まることを説明できる
• 推奨される鍵長（NIST SP 800-57 など）が、どのアルゴリズムの計算量から来ているかを説明できる

前提：第1章、第2章、04-algebra 第1章、04-algebra 第2章。3.5 節では $\mathbb{F}_2$ 上のベクトルの一次従属（02-linear-algebra 第2章）を使う。

RSA 暗号（第2章）の公開鍵 $(n, e)$ から秘密鍵を求める最も直接的な方法は、$n$ を素因数分解することである。ディフィー–ヘルマン鍵共有や DSA では、公開鍵 $y = g^x$ から秘密の $x$ を求めることが離散対数問題そのものである。試し割り（第1章）よりずっと速い攻撃法があり、その速さが鍵の長さを決める。

この章の目的は二つある。一つは推奨される鍵長の根拠を理解することである。RSA の法には 2048 ビット以上が必要なのに楕円曲線の鍵は 256 ビットで足りるのは、使える攻撃法の計算量が違うからである。もう一つは特別な構造をもつ鍵の危険を理解することである。$p$ と $q$ が近い、$p - 1$ が小さい素数の積である、群の位数が小さい素数の積である――こうした鍵では、難しい問題が易しい問題に変わる。

なお、これらの問題が難しいことは証明されていない。わかっているのは、知られている最良のアルゴリズムの計算量だけである。鍵長の推奨はそれに基づく見積もりで、改訂されうる。量子計算機が実用になれば、どちらの問題も多項式時間で解ける（第7章）。

3.1 計算量の物差し：$L$ 記法

$N$ のビット長を $\ell(N) \approx \log_2 N$ とする（第1章）。試し割りは約 $\sqrt{N} = 2^{\ell(N)/2}$ 回の割り算を要する指数時間、反復二乗法は $\ell(N)$ の多項式時間であった。素因数分解の現代的なアルゴリズムはその中間にあり、次の記法で比べる。

定義 3.1（$L$ 記法, $L$-notation）$0 \leq \alpha \leq 1$, $c > 0$ に対し

$$L_N[\alpha, c] = \exp\Bigl((c + o(1))(\log N)^{\alpha}(\log\log N)^{1 - \alpha}\Bigr) \qquad (N \to \infty)$$

とおく。ここで $\log$ は自然対数、$o(1)$ は $N \to \infty$ のとき $0$ に近づく量である。

$\alpha = 0$ なら $L_N[0, c] = (\log N)^{c + o(1)}$ でビット長の多項式、$\alpha = 1$ なら $L_N[1, c] = N^{c + o(1)}$ でビット長の指数関数である。$0 < \alpha < 1$ の場合を準指数時間 (subexponential time) という。$N$ が RSA の法のように同じくらいの大きさの 2 つの素数の積のとき、この章の方法は次のように並ぶ（$\rho$ 法から下は、証明されていない仮定を含むヒューリスティックな見積もり）。

試し割りも、小さい素因数を取り除く最初の段階としては今も使われる。

3.2 フェルマー法

奇数 $N$ が $N = x^2 - y^2 = (x - y)(x + y)$ と書ければ、$N$ の分解が得られる。逆に $N = ab$（$1 \leq a \leq b$、ともに奇数）なら、$x = (a + b)/2$, $y = (b - a)/2$ とおけば $N = x^2 - y^2$ である。そこで $x = \lceil \sqrt{N} \rceil, \lceil \sqrt{N} \rceil + 1, \dots$ の順に $x^2 - N$ が平方数かどうかを調べる。これをフェルマー法 (Fermat's factorization method) という。$a$ と $b$ が近いほど $(a + b)/2$ は $\sqrt{N}$ に近く、早く見つかる。

例 3.2 $N = 58447$ とする。$\sqrt{N} = 241.7\cdots$ なので $x = 242$ から始める。

よって $N = (244 - 33)(244 + 33) = 211 \cdot 277$ である。

命題 3.3（近い素数の積）$N = pq$（$p < q$ は奇素数）とする。フェルマー法が調べる $x$ の個数は $(q - p)^2/(8\sqrt{N}) + 1$ 未満である。特に $q - p \leq 2\sqrt{2}N^{1/4}$ ならば、最初の $x = \lceil \sqrt{N} \rceil$ で成功する。

証明. $x \geq \lceil \sqrt{N} \rceil$ で $x^2 - N = y^2$ ならば、$N = (x - y)(x + y)$ は $N$ の分解なので $(x - y, x + y) = (1, N)$ または $(p, q)$ であり、$x = (N + 1)/2$ または $x_0 := (p + q)/2$ である。$x_0 < (N + 1)/2$ なので、フェルマー法は $x_0$ で止まり、調べる個数は $x_0 - \lceil \sqrt{N} \rceil + 1 \leq x_0 - \sqrt{N} + 1$ である。ここで

（最後は相加相乗平均の不等式で、$p \neq q$ より等号は成り立たない）なので、$x_0 - \sqrt{N} < (q - p)^2/(8\sqrt{N})$。$q - p \leq 2\sqrt{2}N^{1/4}$ ならこれは $1$ 以下で、調べる個数は $2$ 未満、すなわち $1$ である。$\square$

逆に、$p, q < 2^{k/2}$（$k$ は $N$ のビット長）なら $(\sqrt{q} + \sqrt{p})^2 < 2^{k/2 + 2}$ なので、調べる個数は $x_0 - \sqrt{N} > (q - p)^2/2^{k/2 + 3}$ より多い。RSA の鍵生成の規格 FIPS 186-5 は $\lvert p - q \rvert > 2^{k/2 - 100}$ を要求しており、このとき個数は $2^{k/2 - 203}$ を超える（$k = 2048$ なら $2^{821}$）。一方、「$p$ の次の素数を $q$ にする」ような生成法は命題 3.3 で直ちに破られる。

3.3 ポラードの $\rho$ 法

$N$ の未知の素因数を $p$ とする。$f(x) = x^2 + c$（$c \neq 0, -2$）と初期値 $x_0$ をとり、$x_{i+1} = f(x_i) \bmod N$ で数列を作る。$x_i \bmod p$ は同じ漸化式 $x_{i+1} \equiv f(x_i) \pmod{p}$ に従い、$\mathbb{Z}/p\mathbb{Z}$ は有限集合なので、いずれ $x_i \equiv x_j \pmod{p}$（$i < j$）となる。そのとき $p \mid \gcd(x_j - x_i, N)$ で、$p$ が未知でも $\gcd$ は計算できる。すべての組 $(i, j)$ を試す必要はなく、次の補題により $(i, 2i)$ の組だけを調べればよい。

補題 3.4（フロイドの循環検出, Floyd's cycle detection）$S$ を有限集合、$F\colon S \to S$ を写像、$x_0 \in S$, $x_{i+1} = F(x_i)$ とする。$x_T \in \lbrace x_0, \dots, x_{T-1} \rbrace$ となる最小の $T \geq 1$ をとり、$x_T = x_\mu$（$0 \leq \mu < T$）、$\lambda = T - \mu$ とおく。

1. $i < j$ について、$x_i = x_j$ であるための必要十分条件は $i \geq \mu$ かつ $\lambda \mid j - i$ である。
2. $x_i = x_{2i}$ となる $i \geq 1$ が存在し、その最小値は $T = \mu + \lambda$ 以下である。

証明. $T$ は鳩の巣原理により $\lvert S \rvert$ 以下で存在し、$T$ の最小性から $x_0, \dots, x_{T-1}$ は相異なる。$x_{\mu + \lambda} = x_\mu$ に $F$ を繰り返し施せば $x_{k + \lambda} = x_k$（$k \geq \mu$）なので、$k \geq \mu$ なら $x_k = x_{k'}$（$\mu \leq k' < T$, $k' \equiv k \pmod{\lambda}$）である。$k < \mu$ なら $k' = k$ とおく。(1) $i \geq \mu$, $\lambda \mid j - i$ なら $x_j = x_i$ である。逆に $x_i = x_j$ なら $x_{i'} = x_{j'}$ で、$x_0, \dots, x_{T-1}$ は相異なるから $i' = j'$。$i < \mu$ なら $i' = i$ は $j'$（$j \geq \mu$ なら $j' \geq \mu$、$j < \mu$ なら $j' = j > i$）と異なり矛盾するので $i \geq \mu$ であり、$i \equiv i' = j' \equiv j \pmod{\lambda}$。(2) $\max(\mu, 1)$ 以上の最小の $\lambda$ の倍数を $i$ とすると、$i \geq \mu$, $\lambda \mid 2i - i$ なので (1) より $x_i = x_{2i}$。$\mu \geq 1$ なら $i \leq \mu + \lambda - 1$、$\mu = 0$ なら $i = \lambda$ である。$\square$

点列の添字を並べると、長さ $\mu$ の「尾」の先に長さ $\lambda$ の輪がつながった、文字 $\rho$ の形になる。これが名前の由来である。

ポラードの $\rho$ 法 (Pollard's rho method) では、$(x_i, x_{2i}) \bmod N$ を $i = 1, 2, \dots$ と同時に更新し、$d = \gcd(x_{2i} - x_i, N)$ を計算する。$1 < d < N$ なら $d$ が非自明な約数である。補題 3.4 を $S = \mathbb{Z}/p\mathbb{Z}$ に適用すると、$p$ についての $T$ 以下の段で必ず $p \mid d$ となる。$d = N$ となるのは他の素因数でも同時に一致が起きたときで、そのときは $c$ を変えてやり直す。

例 3.5 $N = 18841$, $f(x) = x^2 + 1$, $x_0 = 2$ とする。

$N = 83 \cdot 227$ である。計算する人には見えない $\bmod 83$ の列は $2, 5, 26, 13$ の尾（$\mu = 4$）の先で $4 \to 17 \to 41 \to 22 \to 70 \to 4$ と回る（$\lambda = 5$）ので、補題 3.4 のとおり $i = 5$ で一致する。

手間の見積もりには、次の誕生日の議論を使う。

補題 3.6（誕生日の議論, birthday paradox）$S$ を $m$ 元集合とし、$S$ から $S$ への写像 $m^m$ 個の中から $F$ を一様ランダムに選ぶ。$x_0 \in S$ を固定し、補題 3.4 の $T$ を考えると、$k \geq 0$ について

$$P(T > k) = \prod_{i=1}^{k}\Bigl(1 - \frac{i}{m}\Bigr) \leq e^{-k^2/(2m)}, \qquad E[T] \leq 1 + \sqrt{\frac{\pi m}{2}}$$

が成り立つ。

証明. $T > k$ は $x_0, \dots, x_k$ が相異なることと同値である。$x_0, \dots, x_{i-1}$ が相異なるという条件のもとで、$x_{i-1}$ は $x_0, \dots, x_{i-2}$ のどれとも異なるので、$F(x_{i-1})$ の値はまだ使われておらず $S$ 上一様に分布する。よって $x_i = F(x_{i-1})$ が $x_0, \dots, x_{i-1}$ と異なる条件付き確率は $1 - i/m$ で、これを掛けて等式を得る。$k \geq m$ なら積は $0$ である。$k < m$ なら各因子は正なので、$1 - t \leq e^{-t}$ より積は $\exp(-k(k + 1)/(2m)) \leq e^{-k^2/(2m)}$ 以下である。$T$ は正の整数値をとるので、$e^{-t^2/(2m)}$ が減少関数であることを使って

である。$\square$

$x^2 + c$ はランダムな写像ではない（$x$ と $-x$ が同じ値に写る）が、経験的にはほぼ同じようにふるまう。これを仮定すると、$\rho$ 法はおよそ $\sqrt{p}$ 段（各段は法 $N$ の乗算 3 回と $\gcd$ 1 回）で素因数 $p$ を見つける。この見積もりはヒューリスティックで、証明されていない。次のコードで、$p$ の大きさと段数の関係を確かめる。

from math import gcd

def rho(N, c=1, x0=2):
    """ポラードのρ法（フロイドの方法）。見つけた約数と反復回数を返す"""
    f = lambda t: (t * t + c) % N
    x = y = x0
    i = 0
    while True:
        i += 1
        x, y = f(x), f(f(y))          # x = x_i, y = x_{2i}
        d = gcd(x - y, N)
        if d != 1:
            return d, i

q = 2**61 - 1                          # メルセンヌ素数
for p in [10007, 1000003, 100000007, 10000000019]:
    d, i = rho(p * q)
    print(f"p = {p:>11}  見つけた約数 = {d:>11}  反復 {i:>6} 回  sqrt(p) = {p**0.5:9.0f}")

p =       10007  見つけた約数 =       10007  反復     40 回  sqrt(p) =       100
p =     1000003  見つけた約数 =     1000003  反復   1276 回  sqrt(p) =      1000
p =   100000007  見つけた約数 =   100000007  反復   8587 回  sqrt(p) =     10000
p = 10000000019  見つけた約数 = 10000000019  反復 157220 回  sqrt(p) =    100000

段数はばらつく（ここでは $0.4\sqrt{p}$ から $1.6\sqrt{p}$ 程度）が、どれも $\sqrt{p}$ と同じ桁にあり、$p$ が $10^6$ 倍になっても段数は数千倍にしかならない。小さい素因数を見つけるには向いているが、RSA の法では $p \approx 2^{1024}$ なので約 $2^{512}$ 段かかる。

3.4 ポラードの $p - 1$ 法

定義 3.7（滑らかな数）$B \geq 2$ とする。正の整数 $m$ の素因数がすべて $B$ 以下のとき、$m$ は $B$-滑らか ($B$-smooth) であるという。さらに、$q^e \mid m$, $q^{e+1} \nmid m$ となる素数べき $q^e$ がすべて $B$ 以下のとき、$m$ は $B$-べき滑らか ($B$-powersmooth) であるという。

$M_B = \operatorname{lcm}(1, 2, \dots, B) = \prod_{q \leq B} q^{\lfloor \log_q B \rfloor}$（積は $B$ 以下の素数 $q$ にわたる）とおくと、$m \mid M_B$ と $m$ が $B$-べき滑らかであることは同値である。

定理 3.8（$p - 1$ 法, Pollard's $p - 1$ method）$N \geq 2$ を整数、$p$ を $N$ の素因数、$a$ を $p \nmid a$ となる整数、$M$ を $p - 1$ の倍数とする。

1. $p \mid \gcd(a^M - 1, N)$ である。
2. さらに、$N$ の素因数 $q$ で $q \nmid a$ かつ $\operatorname{ord}_q(a) \nmid M$ となるものがあれば、$\gcd(a^M - 1, N)$ は $N$ の非自明な約数である。

証明. (1) フェルマーの小定理（04-algebra 第1章 系 1.35）より $a^{p-1} \equiv 1 \pmod{p}$ で、$M = (p - 1)t$ と書けば $a^M = (a^{p-1})^t \equiv 1 \pmod{p}$。(2) 位数の性質（同 命題 1.40 (1)）より $a^M \not\equiv 1 \pmod{q}$ なので、$q \nmid \gcd(a^M - 1, N)$ である。よってこの $\gcd$ は $N$ ではなく、(1) より $p$ 以上である。$\square$

$p - 1$ 法では、$B$ を決めて $M = M_B$ とし、$a = 2$ について $a^{M} \bmod N$ を素数べき $q^{\lfloor \log_q B \rfloor}$ ごとの冪剰余で計算し、$\gcd(a^M - 1, N)$ を求める。$M_B \leq B^{\pi(B)}$（$\pi(B)$ は $B$ 以下の素数の個数）なので、乗算は $O(\pi(B)\log B)$ 回である。定理 3.8 により、 $N$ のある素因数 $p$ について $p - 1$ が $B$-べき滑らかであれば $p$ が $\gcd$ を割り、さらに他のある素因数 $p'$ について $\operatorname{ord}_{p'}(a) \nmid M_B$、すなわち $\operatorname{ord}_{p'}(a)$ が $B$-べき滑らかでなければ、分解に成功する（$p' - 1$ が $B$-べき滑らかでないだけでは足りない）。

例 3.9 $N = 16833407 = 4201 \cdot 4007$ とする。$4200 = 2^3 \cdot 3 \cdot 5^2 \cdot 7$ は $25$-べき滑らかだが、$4006 = 2 \cdot 2003$ は大きい素因数をもつ。$a = 2$ とすると、$M_{20} = 232792560$ は $5^2$ で割り切れないので $\operatorname{ord}_{4201}(2) = 525 = 3 \cdot 5^2 \cdot 7$ で割り切れず、$\operatorname{ord}_{4007}(2) = 2003$ でも割り切れない。よって $\gcd(2^{M_{20}} - 1, N) = 1$ で失敗する。$M_{25} = 26771144400$ では $2^{M_{25}} \equiv 11279686 \pmod{N}$, $\gcd(11279686 - 1, N) = 4201$ で分解できる（$B < 2003$ なら $2003 \nmid M_B$ なので、$q = 4007$ について定理 3.8 (2) の条件がみたされる）。

ランダムに選んだ大きな素数 $p$ では、$p - 1$ が計算できる程度の $B$ でべき滑らかになることはまずない（2020 年に分解された RSA-250 の 2 つの素因数 $p, q$ でも、$p - 1$ は 77 桁、$q - 1$ は 83 桁の素因数をもつ）。$p - 1$ 法は群 $(\mathbb{Z}/p\mathbb{Z})^\times$ の位数 $p - 1$ が滑らかなときに働く。この群を、曲線ごとに位数が変わる楕円曲線の群 $E(\mathbb{F}_p)$ に取り替えたのが、レンストラの楕円曲線法である（21 第5章 5.7 節）。

3.5 二次ふるい法の考え方

現在の主な素因数分解法は、次の簡単な事実に基づいている。

命題 3.10（平方の合同）$x^2 \equiv y^2 \pmod{N}$ かつ $x \not\equiv \pm y \pmod{N}$ ならば、$\gcd(x - y, N)$ は $N$ の非自明な約数である。

証明. $N \mid (x - y)(x + y)$ である。$\gcd(x - y, N) = N$ なら $x \equiv y$ となって仮定に反する。$\gcd(x - y, N) = 1$ なら、04-algebra 第1章 命題 1.9 より $N \mid x + y$ となり、やはり仮定に反する。$\square$

奇数 $N$ が相異なる素因数を $k \geq 2$ 個もてば、中国剰余定理により $y^2$（$\gcd(y, N) = 1$）の法 $N$ の平方根は $2^k$ 個あり、$\pm y$ はそのうち 2 個だけである。したがって $x$ が平方根の中から「でたらめに」選ばれていれば、$1/2$ 以上の確率で成功する。問題は、そのような $x, y$ の作り方である。

$m = \lceil \sqrt{N} \rceil$ とし、$Q(t) = t^2 - N$ を $t = m, m + 1, \dots$ について考える。$t^2 \equiv Q(t) \pmod{N}$ であり、$t$ が $\sqrt{N}$ に近ければ $Q(t) \approx 2(t - \sqrt{N})\sqrt{N}$ は $N$ よりずっと小さい。素数 $p \nmid N$ が $Q(t)$ を割れば $N \equiv t^2 \pmod{p}$ なので、$p = 2$ を除いて $\left(\frac{N}{p}\right) = 1$ である。そこで $B$ 以下の素数のうち $p = 2$ と $\left(\frac{N}{p}\right) = 1$ をみたすものを集めて因子基底 (factor base) $\mathcal{F} = \lbrace p_1, \dots, p_k \rbrace$ とし、$Q(t)$ が $\mathcal{F}$ の素数だけの積になる $t$（関係式, relation）を集める。

命題 3.11（関係式から平方の合同へ）$t_1, \dots, t_r$ が $Q(t_i) = \prod_{j=1}^{k} p_j^{e_{ij}}$ をみたすとする。$r > k$ ならば、空でない部分集合 $S \subset \lbrace 1, \dots, r \rbrace$ で、すべての $j$ について $\sum_{i \in S} e_{ij}$ が偶数になるものが存在する。このとき

$$X = \prod_{i \in S} t_i, \qquad Y = \prod_{j=1}^{k} p_j^{\frac{1}{2}\sum_{i \in S} e_{ij}}$$

は $X^2 \equiv Y^2 \pmod{N}$ をみたす。

証明. $v_i = (e_{i1} \bmod 2, \dots, e_{ik} \bmod 2) \in \mathbb{F}_2^k$ とおく。$r > k$ なので $v_1, \dots, v_r$ は一次従属であり（02-linear-algebra 第2章 命題 2.22）、すべては $0$ でない $c_i \in \mathbb{F}_2 = \lbrace 0, 1 \rbrace$ で $\sum c_iv_i = 0$ となる。$S = \lbrace i \mid c_i = 1 \rbrace$ とすればよい。このとき $X^2 = \prod_{i \in S} t_i^2 \equiv \prod_{i \in S} Q(t_i) = Y^2 \pmod{N}$ である。$\square$

$X \equiv \pm Y$ なら別の一次従属関係を試す。関係式はふるいで見つける。奇素数 $p \in \mathcal{F}$ について $p \mid Q(t) \iff t \equiv \pm r_p \pmod{p}$（$r_p^2 \equiv N$）なので、$p$ で割り切れる $t$ は公差 $p$ の 2 つの等差数列をなす。エラトステネスのふるいと同じように、区間の中のこれらの $t$ に $\log p$ を足していけば、割り算をせずに、合計が $\log Q(t)$ に近い $t$ として滑らかな $Q(t)$ の候補が見つかる。これが二次ふるい法 (quadratic sieve) である。

例 3.12 $N = 22969$, $B = 13$ とする。$N \bmod 13 = 11$ は法 $13$ の平方非剰余なので、因子基底は $\mathcal{F} = \lbrace 2, 3, 5, 7, 11 \rbrace$ である。たとえば $N \equiv 4 \pmod{5}$ だから $5 \mid Q(t) \iff t \equiv 2, 3 \pmod{5}$ で、$t = 152, 153, 157, 158, \dots$ がふるいで印をつけられる。$m = 152$ から始めると

3 つのベクトルの和は $0$ なので $S = \lbrace 152, 153, 155 \rbrace$ ととると、$135 \cdot 440 \cdot 1056 = 2^8 \cdot 3^4 \cdot 5^2 \cdot 11^2$ より $Y = 2^4 \cdot 3^2 \cdot 5 \cdot 11 = 7920$、$X = 152 \cdot 153 \cdot 155 \equiv 21516 \pmod{N}$ である。$X \not\equiv \pm Y$ で、$\gcd(21516 - 7920, N) = \gcd(13596, 22969) = 103$。よって $N = 103 \cdot 223$ である。

計算量の見積もり（概略）　鍵は滑らかな数の割合である。次の定理を使う。

定理 3.13（カンフィールド–エルデシュ–ポメランス, 1983 年）$\varepsilon > 0$ を固定する。$u \to \infty$ のとき、$u \leq \log x/((1 + \varepsilon)\log\log x)$ の範囲で一様に、$x$ 以下の正の整数のうち $x^{1/u}$-滑らかなものの割合は $u^{-u(1 + o(1))}$ である。

（主張のみ。解説は Crandall–Pomerance, Prime Numbers にある。）値 $Q(t)$ は $N^{1/2 + o(1)}$ 程度なので、これらがランダムな整数と同じ割合で滑らかになると仮定する。$B = L_N[1/2, b]$ とおくと $u = \log N^{1/2}/\log B \approx \frac{1}{2b}\sqrt{\log N/\log\log N}$, $\log u \approx \frac{1}{2}\log\log N$ なので、滑らかになる割合は $u^{-u} \approx 1/L_N[1/2, 1/(4b)]$ である。関係式は約 $L_N[1/2, b]$ 個（因子基底の大きさ程度）必要なので、調べる $t$ は約 $L_N[1/2, b + 1/(4b)]$ 個で、ふるいなら 1 個あたりの手間は $L_N[1/2, o(1)]$ である。一次従属の計算は、ほとんどの成分が $0$ の約 $B \times B$ 行列について約 $B^2 = L_N[1/2, 2b]$ の手間である。$\max(b + 1/(4b), 2b)$ は $b = 1/2$ で最小値 $1$ をとるので、全体で $L_N[1/2, 1]$ となる。

数体ふるい法（紹介）$f(m) \equiv 0 \pmod{N}$ となる整数 $m$ と多項式 $f$ を選び、$f$ の根 $\alpha$ で生成される環 $\mathbb{Z}[\alpha]$ と $\mathbb{Z}$ の両方で滑らかさを考え、環準同型 $\mathbb{Z}[\alpha] \to \mathbb{Z}/N\mathbb{Z}$, $\alpha \mapsto m$ で両側の平方を法 $N$ の平方の合同に移す。滑らかであってほしい数が二次ふるい法よりずっと小さくなり、計算量は（ヒューリスティックに）$L_N[1/3, (64/9)^{1/3}]$ に下がる（主張のみ）。2020 年 2 月には 829 ビットの RSA-250 が数体ふるい法で分解された（公開ソフトウェア CADO-NFS による。参照用の CPU で約 2700 コア年と報告されている）。

3.6 離散対数問題

定義 3.14（離散対数問題, discrete logarithm problem）$G$ を位数 $n$ の巡回群、$g$ をその生成元とする。$h \in G$ に対し、$g^x = h$ となる $x \in \mathbb{Z}/n\mathbb{Z}$ を $h$ の（$g$ を底とする）離散対数といい、$\log_g h$ と書く。$g, h$ から $\log_g h$ を求める問題を離散対数問題（DLP）という。

$x \mapsto g^x$ は $\mathbb{Z}/n\mathbb{Z} \to G$ の同型なので（04-algebra 第2章 定理 2.22）、$\log_g h$ はただ一つ定まる。第2章では位数が素数の群で離散対数問題とディフィー–ヘルマン問題を考えたが、ここでは位数 $n$ を一般にする（3.8 節で $n$ の素因数分解が効いてくる）。

離散対数問題の難しさは、群の同型類ではなく群の元の表し方で決まる。加法群 $\mathbb{Z}/n\mathbb{Z}$ の生成元 $g$（$\gcd(g, n) = 1$）では「$g^x = h$」は $xg \equiv h \pmod{n}$ のことで、拡張ユークリッドの互除法で一瞬で解ける。位数 $n$ の巡回群はすべて $\mathbb{Z}/n\mathbb{Z}$ と同型だが、その同型写像の計算が離散対数問題そのものなのである。$\mathbb{F}_p^\times$ には 3.10 節の準指数時間の方法があり、よく選んだ楕円曲線の群には 3.7〜3.9 節の汎用的な方法しか知られていない（第4章）。