力石徹也
格子点探索法による素因数分解高速化手法
Abstract:素因数分解の困難さに安全性の基礎を置く暗号・認証方式が数多く提案されている。RSA暗号、Fiat-Shamir零知識証明等がその例である。これらの暗号・認証方式が安心して使用できるためには、第3者による暗号の解読や偽証明が素因数分解と同等の困難さであることが証明され、素因数分解が計算量的に困難であるような合成数の桁数についての指針が与えられることが必要である。このうち、暗号・認証方式と素因数分解の計算量的な関係については専門書に譲るとして、ここでは後者の素因数分解の困難さについて論じる。
「RSA暗号のブロック長はどの程度であれば安全か」というような具体的な問題の解は、個々の素因数分解のアルゴリズムに依存する。最も単純、かつ明解な方法は合成数Nを素数で順に割る、という試行割算法である。但し、この方法は最悪N1/2の探索となり、10進200桁程度の合成数を用いる現在のRSA暗号は、解読不可能である。
今日では、専門的には素因数分解は準指数的な計算量であると言われている。簡単に言えば、200桁の合成数であれば、概ねN1/8回の探索で済むことになる。このような計算量で素因数分解できるアルゴリズムは、楕円曲線法や2次ふるい法である。これらの手法を用いて、かつ多数の計算機を使用すれば、155桁の合成数が素因数分解できるまでになっている。
これらは概ね、「一定の規則で整数を次々と生成して、各整数と合成数の公約数を求める」という手法をとる。素因数を含む可能性の高い整数Lを生成する方法が、技術的なポイントである。例えば楕円曲線法では、ある種となる整数xと、数多くの素数の積からなる合成数Mとの積Mxを因数とする楕円関数の値を整数Lに用いる。整数xを振らせて、自明でない公約数が存在するかどうかを調べるのである。これらの手法をN1/8オーダよりさらに高速化することは、興味あるテーマであるが、種xの選択法や選択範囲、整数Lを生成するアルゴリズム自体の改良法等の解決すべき問題がある。
本稿では試行割算法に近い、新しい素因数分解の方法を提案する。試行割算法では、因数の探索範囲が1からN1/2までと決まっているので、研究の方向としては総当たり探索でない、効率的な因数探索法を見つけることに専念すればよい。この探索を効率化するには、幾何学的な手法が有効である。すなわち素因数分解は幾何学的はx、yを座標軸とする解平面上で、双曲線xy=Nが整数座標からなる講師点を通過する箇所を求めることに相当する。そこで双曲線xy=Nの近傍に位置するような格子点だけを取り出して、座標値の積を計算して合成数に一致すれば、それが因数である。この方法（これを格子点探索法と呼ぶことにする）により、最大、N1/4の幅で因数を探索できる。従来の試行割算法やフェルマー法等と比較すると高速である。さらに格子点探索法を高速化するために、仮想格子点を設定する方式と合成数の素数に対する剰余値から、格子点の中でも因数の候補となり得るもののみを選択し、これらの間引きされた格子点の中で、双曲線の近傍にあるものを探索する方式を提案する。
第2章では格子点探索法の基本的な方式の説明を行う。第3章では仮想格子点を導入した方式を説明し、第4章で剰余類を導入した方式を説明する。