この記事は Fujitsu Advent Calendar 2018 22日目の記事です。
この記事は素因数分解の現状をまとめた一連の記事の一つです。
(2022年02月27日更新：リンクを追加しました。また、Typoを修正しました。)
(2020年06月07日更新：アニーリング計算編を作成したため、リンクを追加しました)
(2020年04月29日更新：ご指摘いただいた errata 等を中心に加筆修正しました。また、2020年03月までに達成された素因数分解記録を追記しました)
はじめに
素因数分解が何のことだったか覚えていますか？2018 を 2×1009 という素数の積に分解することで、小学校の算数で勉強しているはずです。(ちなみに $x^2-1$ を $(x-1) \times (x+1)$ と分解するのは因数分解と呼んで区別します。) ただ、素因数分解は日常生活ではあまり見かけることのない話題なので、そんな話もあったなぁと遠い目になる方も多いと思います。しかし、素因数分解は数学的に面白い問題ですし、プログラミング入門にもうってつけの話題です。さらには、標準公開鍵暗号の一つである RSA の安全性が、巨大合成数の素因数分解が難しいという事実に依存している1 ため、素因数分解の最新動向を把握することは、インターネットの安全性の保証にもつながります。このような背景をもとに、本記事は、2018年12月時点での素因数分解アルゴリズムと素因数分解記録をまとめます2。具体的には、古典計算・量子ゲート計算・アニーリング計算に分類して説明していきたいと思います。
なお、素因数分解に似た問題として、与えられた自然数が素数かどうかを判定する問題 (素数判定問題) がありますが、素数判定問題は素因数分解問題よりもずっと易しい問題であることが知られています3。具体的には、素数判定では、入力自然数サイズの多項式関数となるアルゴリズムが知られているのに対し、素因数分解では、入力合成数サイズの準指数関数となるアルゴリズムが最良です。このため、本記事は素因数分解アルゴリズムだけを扱うことにします。
古典計算による素因数分解
ＰＣ、スパコンなどの既存の計算機を総称して古典計算機と呼びます。最新のスパコンを「古典計算機」と呼ぶことに抵抗があるかもしれませんが、後述する「量子計算機」の対語として導入された用語であり、「非量子計算機」程度の意味しかありませんので、あまり深くは考えないで下さい。
以下では古典計算機を用いたいくつかの素因数分解アルゴリズムを説明します。まずは最も素朴な素因数分解アルゴリズム（素朴法）を紹介します。次に、一次合同式を用いたアルゴリズムとして、ρ法（ローほう）、$p-1$ 法（ピーマイナスいちほう）、楕円曲線法（だえんきょくせんほう）を紹介します。さらに、二次合同式を用いたアルゴリズムとして、Dixson法（ディクソンほう）、二次篩法（にじふるいほう）、数体篩法（すうたいふるいほう）を紹介します。最後に、最良の素因数分解アルゴリズムである数体篩法による素因数分解の実験記録をまとめます。
いろいろな素因数分解アルゴリズム
素朴法
最も単純な素因数分解アルゴリズムは、素因数分解したい合成数 $N$ に対し、小さい素数から順に $2, 3, 5, ...$ と試し割りしていく方法です。これを 素朴法 (Naive Method) と呼びます。自然数 $x$ 以下の素数の個数を $\pi(x)$ とかくことにすると、素朴法は最悪で $\pi(\sqrt{N})$ 回の試し割り算を計算することになります。素数定理4 によると、大きな自然数 $x$ に対しては、$\pi(x) \approx x/\log{x}$ と近似できるので、素朴法の最悪計算量（計算の手間）は $2\sqrt{N}/\log{N}$ となります。これは、自然数 $N$ のサイズに関する指数関数となっており、巨大な $N$ に対しては非力です。
一次合同式を利用した素因数分解アルゴリズム
素朴法よりも性能の良い素因数分解アルゴリズムとして、合同式を用いた方法を紹介します。
合成数 $N$ が素数 $p$ で割り切れると仮定します。このとき、2 つの自然数 $x, y$ の差が $p$ の倍数となるとき、つまり $x \equiv y \pmod{p}$ のとき、$x-y$ と $N$ の最大公約数 $\gcd(x-y,N)$ は $p$ (の倍数)になる可能性が高いです。そこで自然数 $x, y$ を適切な方法で生成し、$\gcd(x-y,N)$ の計算により $N$ の素因数 $p$ を求めようとする素因数分解法が考えられます。
Pollard は $f(t)=t^2+1 \bmod{N}$ という関数に対し、ある自然数 $a$ をもとに $f(a), f(f(a)), f(f(f(a))),...$ を計算していくことで自然数 $x,y$ を生成する素因数分解法を考案しました。これをρ法 ($\rho$ Method)と呼びます。ρ法は $p$ 通りの値の中から取り出した 2 つの値が一致するという性質を使っているので、誕生日の逆理より、計算量は $\sqrt{p}$ に比例します。このため、大きな素因数を見つけるには不向きです。なお、ρ法という名称は、$f(a),f(f(a)),f(f(f(a))),...$ という値が途中からループになるところから命名されています。
$p-1$ 法 ($p-1$ method) は、ρ法とは異なる方法で一次合同式を利用する素因数分解アルゴリズムです。素数 $p$ と、$p$ と互いに素な自然数 $a$ に対し、$a^{p-1} \equiv 1 \pmod{p}$ が成立します (Fermat の小定理)。よって、自然数 $M$ が $p-1$ の倍数ならば $a^M \equiv 1 \pmod{p}$ が成立し、$a^M-1$ は $p$ の倍数となるので、$\gcd(a^M-1,N)$ は高い確率で $p$ となり、$N$ の素因数 $p$ を見つけられます。これが $p-1$ 法の動作原理です。しかしわれわれは素数 $p$ の値を知らないので、$M$ を定めることができません。そこで $M$ が $p-1$ の倍数になる確率を高めるために、$M$ は素数(のべき)を小さい順に掛け合わせて定義します。このため、$p-1$ 法は、$p-1$ が小さな素数の積になっている場合に有効です。逆に大きな素因数を持つ場合には素因数分解が困難ということになります。
$p-1$ 法の欠点を克服した素因数分解アルゴリズムとして楕円曲線法 (Elliptic Curve Method)が有名です。$p-1$ 法では $p-1$ が小さな素数の積で表せるかがポイントでしたが、$p-1$ という値は $p-1$ 法が使用している (Fermat の小定理を考えている) 乗法群 ${\rm GF}(p)^*$ の位数を意味しています。楕円曲線法は $\bmod{p}$ の楕円曲線群を使用します。このとき、楕円曲線のパラメーター(係数)を変えると、楕円曲線群の位数は $p-1$ を中心に変化するため、$p-1$ が小さな素数の積で表せない場合でも、楕円曲線群の位数が小さな素数の積で表せる可能性が残るので、楕円曲線法が素因数 $p$ を発見する確率は高まることになります。実際、楕円曲線法は小さな素因数を見つけるのに向いており、最大の発見例としては、947 ビットの合成数 $N$ から 274 ビットの素数 $p$ を発見しています。
本節で紹介したρ法、$p-1$ 法、楕円曲線法は、素朴法よりも性能の良い素因数分解アルゴリズムですが、計算量が素因数 $p$ に依存するという特徴を持っています。
二次合同式を利用した素因数分解法 (平方差法)
素因数分解したい合成数 $N$ が素数 $p$ で割り切れると仮定します。
このとき、2 つの自然数 $x, y$ が $x^2 \equiv y^2 \pmod{N}$ となるとき $x^2-y^2=(x-y)(x+y)$ は $N$ の倍数なので、$x-y$ または $x+y$ が $p$ になる、つまり、$\gcd(x-y,N)=p$ となる可能性が高く、素因数分解が可能です。この原理による素因数分解法を平方差法と呼びます。このような自然数 $x,y$ を見つけるには戦略が必要です。そこで目標を「$x^2 \bmod{N}$ が小さな素数の積で表せるような $x$ をたくさん集める」に変更します。この目標が達成できると、式をうまく抜き出すことで、$x,y$ を構成することが可能となります。例えば $N=187$ に対し、$16^2 \equiv 3 \times 23 \pmod{N}$, $24^2 \equiv 3 \times 5 \pmod{N}$, $26^2 \equiv 5 \times 23 \pmod{N}$ が成立するので、これらの式の左辺・右辺を掛け合わせることで $(16 \times 24 \times 26)^2 \equiv (3 \times 5 \times 23)^2 \pmod{N}$、つまり $73^2 \equiv 158^2 \pmod{N}$ という当初の目標式が得られます。ではどうやって「$x^2 \bmod{N}$ が小さな素数の積で表せるような $x$ をたくさん集める」のでしょうか？この集め方にはさまざまな方法が考案されており、それによって素因数分解アルゴリズムが変わってくることになります。
Dixonは、$x$ をランダムに生成し、$x^2 \bmod{N}$ が小さな素数の積になっているものだけを集める、というアルゴリズムを考案しました (Dixon 法)。Dixon法はシンプルで理解しやすいのですが、$x^2 \bmod{N}$ は $N$ とほぼ同じサイズの自然数となるため、もともとの $N$ の素因数分解を、$N$ と同程度のサイズのたくさんの自然数の素因数分解に帰着しており、効率はあまり良くありません。
二次篩法(Quadratic Sieve Method) は上記のような $x$ をシステマティックに生成するために、$x_k=\lfloor \sqrt{N} \rfloor+k$ という記号を導入します。ここで、$\lfloor a \rfloor$ は実数 $a$ を越えない最大整数をあらわします。このとき $x_k^2 - N \approx 2k\sqrt{N} + k^2$ となるので、この右辺が素因数分解できれば、$x_k^2 \bmod{N}$ が素因数分解できたことになります。ここで右辺は $N$ に比べてずっと小さいため、Dixon 法よりも素因数分解が簡単になっていることに注意してください。さらに二次篩法には、$x_k^2-N$ がある素数 $q$ で割り切れるならば、$x_{k+q}^2-N$ も同じ素数 $q$ で割り切れるという性質が成立します。したがって、さまざまな $k$ の値に対し、どの $x_k^2-N$ が素数 $q$ で割り切れるかをチェックし、素数 $q$ を変化させることで、試し割りをほとんどすることなく、どの $x_k^2-N$ が小さな素数の積で表せるかを知ることができます。このトリックを篩法と呼びます。このように二次篩法は優れたアルゴリズムですが、$N$ が大きくなるにつれて探索に必要な $k$ の範囲が広がってしまい、性能が劣化します。そこで、同様な性質を持つ二次多項式を複数利用して、性能劣化を防ぐ改良が考案されています (複数多項式二次篩法 (Multiple Polynomial Quadratic Sieve Method)。二次篩法は1990年代前半までは最も性能の良い素因数分解アルゴリズムであり、RSA-129の素因数分解に成功しましたが、それ以降はもっと性能の良い数体篩法にとって代わられました。
数体篩法 (Number Field Sieve Method)は、篩法の性能をさらに高めるために、左辺も右辺も素因数分解できるようなような関係式 $p_1^{e_1} \times p_2^{e_2} \times \dots \times p_m^{e_m} \equiv q_1^{f_1} \times q_2^{f_2} \times \dots \times q_n^{f_n} \pmod{N}$ を大量に集めます。このような関係式を効率的に生成するために、数体におけるイデアル分解を利用します。与えられた合成数 $N$ に応じて数体を定義する方法を一般数体篩法 (General Number Field Sieve Method)、あらかじめ指定された多項式を用いる方法を特殊数体篩法 (Special Number Field Sieve Method)と呼びます。特殊数体篩法は素因数分解できる合成数に強い制限 (特殊な型の合成数) を受けます。数体篩法は1980年代に考案された素因数分解アルゴリズムですが、1990年代の後半になって実装が効率化され、1996年にRSA-130を分解して以来、素因数分解の世界記録には全て数体篩法が用いられています。
素因数分解記録
本節では、古典計算機による素因数分解の世界記録をいくつかの観点でまとめます。現時点での世界記録は、2020 年 2 月に発表された 829 ビットの素因数分解です。一般数体篩法が使用されましたが、詳細は明らかにされていません。数体篩法の計算量は、合成数サイズの準指数関数になるため、もっと大きな合成数に対しては、素因数分解できる目処は立っていません。このことから、RSA の鍵長は 2048 ビット以上に設定することが推奨されています。
一般数体篩法による素因数分解理録の変遷
次に、一般数体篩法により素因数分解記録の変遷を次表にまとめます。この表は世界記録の更新の履歴をまとめただけなので、現時点での世界記録のトップ7ではないことに注意下さい。1990年代から2000年代にかけて記録が飛躍的に伸びていますが、これは、この時期に一般数体篩法の効率的な実装が実現されたからです。
| 分解日 | 合成数 | サイズ | 桁数 | 文献 | 備考 |
|---|---|---|---|---|---|
| 1999年08月22日 | RSA155 | 512 | 155 | CDL+00 | |
| 2002年01月19日 | C158 | 524 | 158 | BFK02 | C158 は $2^{853}+1$ の約数 |
| 2003年04月01日 | RSA160 | 530 | 160 | BFK+03 | |
| 2003年12月03日 | RSA576 | 576 | 174 | F+03 | |
| 2005年05月02日 | C176 | 582 | 176 | AKS+05 | C176 は $11^{281}$ の約数} |
| 2005年05月09日 | RSA200 | 663 | 200 | BBF+05 | |
| 2009年12月12日 | RSA768 | 768 | 232 | KAF+10 | |
| 2019年12月02日 | RSA240 | 795 | 240 | BGG+19 | |
| 2020年02月28日 | RSA250 | 829 | 250 | BGG+20 |
RSA Challenge の状況 (900 ビット以下)
素因数分解記録の変遷を別の角度から見るために、RSA Challenge の分解状況を次表にまとめまう。RSA Challenge とは、RSA 社が主催した素因数分解コンテストであり、いくつかの合成数については、最初の分解者に対して賞金が与えられました。現在はこのコンテストは終了しています。
| 分解日 | 合成数 | サイズ | 桁数 | 分解法 | 備考 |
|---|---|---|---|---|---|
| 1991年04月01日 | RSA-100 | 330 | 100 | 二次篩法 | |
| 1992年04月14日 | RSA-110 | 364 | 110 | 二次篩法 | |
| 1993年07月09日 | RSA-120 | 397 | 120 | 二次篩法 | |
| 1994年04月26日 | RSA-129 | 426 | 129 | 二次篩法 | |
| 1996年04月10日 | RSA-130 | 430 | 130 | 一般数体篩法 | |
| 1999年02月02日 | RSA-140 | 463 | 140 | 一般数体篩法 | |
| 2004年04月16日 | RSA-150 | 496 | 150 | 一般数体篩法 | |
| 1999年08月22日 | RSA-155 | 512 | 155 | 一般数体篩法 | |
| 2003年04月01日 | RSA-160 | 530 | 160 | 一般数体篩法 | |
| 2009年12月29日 | RSA-170 | 563 | 170 | 一般数体篩法 | |
| 2003年12月03日 | RSA-576 | 576 | 174 | 一般数体篩法 | |
| 2010年05月08日 | RSA-180 | 596 | 180 | 一般数体篩法 | |
| 2010年11月08日 | RSA-190 | 629 | 190 | 一般数体篩法 | |
| 2005年11月02日 | RSA-640 | 640 | 193 | 一般数体篩法 | |
| 2005年05月09日 | RSA-200 | 663 | 200 | 一般数体篩法 | |
| 2013年09月26日 | RSA-210 | 696 | 210 | 一般数体篩法 | |
| 2012年07月02日 | RSA-704 | 704 | 212 | 一般数体篩法 | |
| 2016年05月13日 | RSA-220 | 729 | 220 | 一般数体篩法 | |
| 2018年08月15日 | RSA-230 | 762 | 230 | 一般数体篩法 | |
| 2020年02月17日 | RSA-232 | 768 | 232 | 一般数体篩法 | |
| 2009年12月12日 | RSA-768 | 768 | 232 | 一般数体篩法 | |
| 2019年12月02日 | RSA-240 | 795 | 240 | 一般数体篩法 | |
| 2020年02月28日 | RSA-250 | 829 | 250 | 一般数体篩法 | |
| RSA-260 | 862 | 260 | |||
| RSA-270 | 895 | 270 | |||
| RSA-896 | 896 | 270 |
数体篩法のハードウェア化
前節までに紹介した素因数分解記録は全てソフトウェア実装によるものです。本節では、数体篩法のハードウェア化の試みをまとめます。
ASIC
一般数体篩法では、関係式探索と呼ばれる処理に膨大な計算リソースを必要とします。そこで 2000 年代に入り、ハードウェア化 (ASIC化) による高速化が議論されました。中でも 2003 年に提案された TWIRL は、1024 ビット合成数の素因数分解 (に必要な関係式探索処理) を約 1 年で処理可能な ASIC チップの設計法であり、製造費も約 10 億円と試算されたことから、大きな注目を集めました。しかし、この提案は理論検討であり、実際の実験報告がないことや、実際に製造した場合にメインの ASIC チップがウェハ 1 枚分の面積を占めることなどから、否定的な分析結果が報告されています。
FPGA
2007 年に富士通は関係式探索処理を FPGA に実装し、423 ビットの合成数の素因数分解 (に必要な関係式探索処理) の実験結果を報告しました。しかし、単純な延長で 1024 ビット合成数を分解するのは厳しいと報告されており、同様な設計でのハードウェア実装の実用性は低いと考えられています。
まとめ
古典計算による素因数分解アルゴリズムと、素因数分解記録についてまとめました。現時点での世界記録は、数体篩法による 829 ビット合成数の素因数分解であり、記録が大きく更新される見込みは立っていません。Keep Factoring!
量子ゲート計算を用いた素因数分解の現状についてはこちらの記事を参照下さい。
また、アニーリング計算を用いた素因数分解の現状についてはこちらの記事を参照下さい。
-
2020年04月29日加筆。2020年03月までの分解記録を追加しました。 ↩