この記事は Fujitsu Advent Calendar 2018 22日目の記事です。
この記事は素因数分解の現状をまとめた一連の記事の一つです。
- [古典計算編] (https://qiita.com/izutetsuya/items/ff0347d26d1699ae3a94)
- 量子ゲート計算編
- アニーリング計算編 (本記事)
はじめに
本記事では、アニーリング計算による素因数分解について紹介します。アリーリング計算とは、与えられた評価関数の最小値を求める計算手法で、量子計算機上のアニーリング計算は古典計算機上のアニーリング計算よりも高性能であることがわかっていることから、近年、注目を集めている計算手法です。アニーリング素因数分解は、このアニーリング計算を用いて素因数分解をする試みです。素因数分解の観点では、(量子)アニーリング計算はブラックボックスで構いませんので、原理については以下では触れません。興味のある方は、別の記事 1 を参照下さい。
2020年06月時点で、アニーリング計算による最大の素因数分解例は32ビット合成数の素因数分解です 2。古典計算機による素因数分解記録が829ビット、量子ゲート計算機による素因数分解記録が4ビットであることを考えると、アニーリング素因数分解は古典計算機にはかないませんが、量子ゲート計算機よりも高性能であることがわかります。さまざまなベンダーが(量子)アニーリング専用計算機の開発を活発に行っていますので、アニーリング素因数分解の記録はまだ伸びる余地が大きいように思います。
アニーリング計算の前提
アニーリング計算において、最長値を求める評価関数 (Hamiltonian) は、多変数の整数係数多項式です。ただし、各変数は Boolean 値 (0 または 1) です。アニーリング計算の環境ごとに、変数の個数や係数の絶対値に対する制約が設定されます。なお、アニーリング計算のコアエンジンに入力する際には、多項式は2次式である必要がありますが、HOBO2QUBOと呼ばれる手法を適用することで、任意の3次以上の多項式を、2次の多項式に変換することが可能なので、以下では次数はあまり気にしないことにします。
いろいろな素因数分解アルゴリズム
以下では、
素因数分解したい合成数は $N=p \times q$ (RSA型) であることを仮定します。
また、簡単のため $p, q$ は同じビット長である場合を考えます。
素朴法
アニーリング素因数分解では、求めたい素因数分解できていない時は正、素因数分解できた時には 0 となるような多変数多項式が必要です。素因数分解したい合成数 $N$ に対し、素朴法 (Naive Method) は $f(x,y)=(N-xy)^2$ という多項式を使用します。$(x,y) \ne (p,q)$ ならば $f(x,y) > 0$, $(x,y)=(p,q)$ ならば $f(x,y)=0$ となっているので、確かに多項式の条件を満たします。実際にアニーリング計算するには、$x,y$ を2進展開表現して、Boolean 変数のよる表現を求めることになります。このとき、$x,y$ の最上位ビットと最下位ビットは 1 となることに注意して下さい。
例えば $N=143~(=11 \times 13)$ の場合、$f(x)=(143-xy)^2$ に $x=2^3 + x_2 2^2 + x_1 2^1 + 2^0$, $y=2^3 + y_2 2^2 + y_1 2^1 + 2^0$ を代入することで、
$$ f(x,y) = (143-(4 x_2 + 2 x_1 + 9)(4 y_2 + 2 y_1 + 9))^2
= (((256 y_1+1408) y_2+640 y_1+1296) x_1+(1408 y_1+3168) y_2 + 1232 y_1-3168)x_2 +((640 y_1+1232) y_2+456 y_1-1908) x_1+(1296 y_1-3168) y_2-1908 y_1+3844 $$
という4変数多項式を得ることができます。ここで、$x_1^2=x_1$ などの関係式を利用しました。素朴法では、素因数分解したい合成数 $N$ の平方を使用するため、多項式の係数が大きくなるという性質があります。
筆算法
筆算法 (Multiplication-table Method)は、掛け算の筆算で登場する関係式を利用した素因数分解方法です。
$N=143$ の掛け算の筆算は以下のようになります。ここで、$B_7,B_6,...,B_0$ は列番号、$z_{i,j}$ は $B_i$ から $B_j$ への桁上がりをあわらす Boolean 変数です。
このとき、素因数分解の解は以下の7連立方程式の解となります：
$B_1: x_1 + y_1 = 1 + 2z_{1,2}$
$B_2: x_2 + x_1 y_1 + y_2 + z_{1,2} = 1 + 2z_{23} + 4z_{2,4} $
$ B_3: 1 + x_2 y_1 + x_1 y_2 + 1 + z_{2,3} = 1 + 2z_{3,4} + 4z_{3,5} $
$ B_4: y_1 + x_2 y_2 + x_1 + z_{3,4} + z_{2,4} = 2z_{4,5} + 4z_{4,6} $
$ B_5: y_2 + x_2 + z_{4,5} + z_{3,5} = 2z_{5,6} + 4z_{5,7} $
$ B_6: 1 + z_{5,6} + z_{4,6} = 2z_{6,7} $
$ B_7: z_{6,7} + z_{5,7} = 1 $
この連立方程式をアニーリング計算で解くために、、
多項式
$$
f(x)=B_0^2 + B_1^2 + ... + B_7^2
= (((2y_1+2)y_2+2y_1)x_1+(2y_1+2z_{2,4}+2z_{3,4}-4z_{4,5}-8z_{4,6}+5)y_2
- 2z_{2,3}-4z_{3,4}-8z_{3,5}+3)y_1+2z_{1,2}-4z_{2,3}-8z_{2,4}+2z_{3,5}
+2z_{4,5}-4z_{5,6}-8z_{5,7})x_2+((2y_1+2z_{2,3}-4z_{3,4}-8z_{3,5}+3)y_2
+(2z_{1,2}-4z_{2,3}-8z_{2,4}+3)y_1
-4z_{1,2}+2z_{2,4}+2z_{3,4}-4z_{4,5}-8z_{4,6})x_1
+(2z_{1,2}-4z_{2,3}-8z_{2,4}+2z_{3,5}+2z_{4,5}-4z_{5,6}-8z_{5,7})y_2
+(-4z_{1,2}+2z_{2,4}+2z_{3,4}-4z_{4,5}-8z_{4,6})y_1
+(-4z_{2,3}-8z_{2,4}+7)z_{1,2}+(16z_{2,4}-4z_{3,4}-8z_{3,5}+11)z_{2,3}
+(2z_{3,4}-4z_{4,5}-8z_{4,6}+25)z_{2,4}
+(16z_{3,5}-4z_{4,5}-8z_{4,6}+1)z_{3,4}
+(2z_{4,5}-4z_{5,6}-8z_{5,7}+9)z_{3,5}+(16z_{4,6}-4z_{5,6}-8z_{5,7}+5)z_{4,5}
+(2z_{5,6}-4z_{6,7}+19)z_{4,6}+(16z_{5,7}-4z_{6,7}+7)z_{5,6}
+(2z_{6,7}+15)z_{5,7}-z_{6,7}+5
$$
を使用します。素朴法の4変数に比べ、この多項式は14変数であり、変数の個数は増えています。しかし、係数の絶対値が小さくなっており、素朴法よりも扱いやすくなっています。
変数消去
$N=143$ の関係式 $B_1: x_1+y_1=1+2z_{1,2}$ を考えます。各変数は Boolean なので、左辺値は高々 2 なので、$z_{1,2}=0$ でなければならないことがわかります。同様な考察を繰り返すと、上の8式は、$x_1+y_1=1$, $x_2+y_2=1$, $x_1y_2+x_2y_1=1$ という3式に簡約化されます。$N$ が大きくなるとこのような簡約は難しくなります。
素因数分解記録
アニーリング計算による素因数分解の実験結果を以下にまとめます。
| 発表年 | 計算手段 | $N$ | $N$のビット長 | 文献 | 備考 |
|---|---|---|---|---|---|
| 2002年 | [理論検討] | [Bur02] | 筆算法の提案 | ||
| 2008年 | NMR | 21 | 5 | [PLX+08] | 最初の素因数分解実験 |
| 2009年 | [理論検討] | [SS09] | 筆算法(Cell法,Column法)の提案 | ||
| 2012年 | NMR | 143 | 8 | [XZL+12] | 変数消去の導入 |
| 2014年 | [思考実験] | 291311 | 19 | [DB+14] | 変数消去できる合成数の探索 |
| 2016年 | NMR | 551 | 10 | [PMA+16] | 対称性の利用 |
| 2016年 | D-Wabve 2X | 200099 | 18 | [DA16] | グレブナー基底計算の利用 |
| 2017年 | NMR | 291311 | 19 | [LDC+17] | 変数消去の有効利用 |
| 2018年 | D-Wave 2000Q | 8137 | 13 | [JBMc+18] | ブロック化法の提案 |
| 2019年 | Digital Annealer | 541000303 | 30 | [SIS+19] | 部分的生成法の提案 |
| 2019年 | qbsolve | 1005973 | 20 | [PWH+19] | 改良ブロック化法の提案 |
| 2020年 | Digital Annealer 2 | 4049874797 | 32 | [ISS+20] |
まとめ
アニーリング計算による素因数分解アルゴリズムと、素因数分解記録についてまとめました。現時点での世界記録は、32 ビット合成数の素因数分解であり、古典計算機の素因数分解記録 829 ビットとはかけ離れた状況です。ただし、(量子)アニーリングの専用計算機が活発に開発されていることから、当面はこの記録は更新され続けられると予想します。Keep Factoring!
古典計算を用いた素因数分解の現状についてはこちらの記事を参照下さい。
また、量子ゲート計算を用いた素因数分解の現状についてはこちらの記事を参照下さい。
-
伊豆等, アニーリング計算による素因数分解について (その2), 2020年暗号と情報セキュリティシンポジウム (2020), 2020年1月. ↩