p-1法による素因数分解 - ちりもつもればミルキーウェイ

はじめに

RSAについて語る上で、素因数分解の困難さにふれないわけにはいかんやろ！ということで、素因数分解アルゴリズムの中でも簡単なp-1法について紹介します！

(ほんとうは数体ふるい法が実用上最速のあつかいをされることが多いので紹介したいんですが、むずすぎて僕が理解できてない...いずれかならず倒したい)

p-1法とは

まず素因数分解したい値 $n$ (素因数に $p$ を含む), $p$ と互いに素な整数 $a$ を準備します。

そして $p-1$ の倍数となる $M$ をなんとか探します。
さすがにノーヒントで範囲無限で探索すると日が暮れるので $p-1$ の値にそんなに大きい素因数はないだろ！という前提の元に探索する素因数の上限を指定して探します。
そのため $p-1$ の素因数がすべて小さいとうまくハマって少ない探索で素因数分解ができます。逆に言うと $p-1$ に大きい素因数が含まれていると無力です。

どうにかしてこの条件を満たす $M$ を探し出すと $gcd(a^{M}-1, n)$ をとって素因数 $p$ が高確率でわかるぞ！というやつです

$M$ がわかると素因数 $p$ がわかる理由

p-1法はフェルマーの小定理の考え方をつかった素因数分解アルゴリズムなのでおさらい！(証明とかはこちら)

フェルマーの小定理:

素数 $p$ とその倍数でない正の整数 $a$ について、
$a^{(p-1)}\equiv 1\pmod p$ がなりたつ

で、これはフェルマーの小定理がわかってれば簡単です。前提条件は以下です

素因数分解したい値 $n$ (素因数に $p$ を含む)
$p$ と互いに素な整数 $a$
$m(p-1)$ となる $M$

で、このとき $a, p$ は互いに素なのでフェルマーの小定理より

$a^M = a^{m(p-1)} = (a^{p-1})^m \equiv 1^m \equiv 1\pmod p$

です。そのため $a^{M}-1\equiv 0\pmod p$ です。
これは $p$ を素因数に含んでいるということなので、同じく $p$ を素因数に含む $n$ と

$gcd(a^{M}-1, n)$

として最大公約数をとればそれは $p$ の倍数であることは間違いないし、大抵の場合は素数 $p$ そのものが取れるぞ！ということです

$M$ の探し方どうやる？

それな

成り立つ原理はチョロなんですが $M$ の探し方が問題です。
直感で適当に決めたり、1から順に決めたりして $gcd(a^{M}-1, n)$ をそれっぽい値が見つかるまで計算し続けてもいいんですが、素朴にやると効率が悪いです。

$M$ については情報がほぼ無いので、適当に選ぶとだいたい $p$ と互いに素になって $gcd(a^{M}-1, n) = 1$ となります。これは外れです。

で、このまま直感で適当に値を設定し続けてもいいんですがそれではあまりにも運命力が求められるので、別のやり方を考えます。

ここで $p-1$ は小さな素数の積である！みたいな前提をおきます。これをちょっとかっこよくいうと $B$ -Smooth といいます

$B$ -Smooth:

$n$ のすべての素因数が $B$ 以下であること
言い換えると $n = q^{e_1}_1\cdot q^{e_2}_2 \cdot q^{e_3}_3 \cdot \cdots q^{e_r}_r$ に素因数分解できるとき、
任意の $i$ ( $1 \leq i \leq r$ ) について $q_i \leq B$ を満たすことをいう

こうすると $B$ で設定した値以下の素数についてのみ確認すればよいので、すこし負荷は下がりそうです。

つぎは $M$ が $p-1$ の倍数であるような条件を考えます。
$p-1$ と $M$ を以下のような $B$ -Smooth をみたすの素数 $q_i$ の積とします

$p-1 = q^{e_1}_1\cdot q^{e_2}_2 \cdot q^{e_3}_3 \cdot \cdots q^{e_r}_r$
$M = q^{m_1}_1\cdot q^{m_2}_2 \cdot q^{m_3}_3 \cdot \cdots q^{m_r}_r$

そうしたときに、それぞれの素因数 $q_i$ について考えると $e_i \leq m_i$ となっていれば $q^{m_r}_r$ は $q^{e_r}_r$ で割り切れると言えます。
これはすべての素因数について言えるので $M$ が $p-1$ の倍数であるような条件は

$e_i \leq m_i$

となります。

とはいえ実際の $p-1$ の具体的な値などはわかりません。いまのところわかっているのは少なくとも $n$ 以下ではある！ということくらいです。

ですが、最も $q_i$ に対して指数が多いパターンである $n$ の素因数が $q_i$ しかない場合を想定しておけば確実に $p-1$ に含まれる該当の素因数 $q_i$ の指数 $e_i$ 以上になるはずです。なので

$m_i = log_{qi} n$

とすれば $B$ -Smooth な前提において確実に $e_i \leq m_i$ となり $M$ は $p-1$ で割り切れます。

$M$ の探し方まとめ

ある素数 $p$ を素因数に含む $n$ を与えられたとすると

$p$ と互いに素な $a$ の決定
探索する素数の上限である $B$ をきめる。これは $B$ -Smoothな素数であるという前提による
$1..B$ までの素数 $q_i$ をあらいだす
それぞれの素数を $m_i = log_{qi} n$ の値でべき乗する
4の結果を $a$ に対してべき乗して $M$ とする
$gcd(a^{M}-1, n)$ を計算！素因数 $p$ が見つかることを祈る

となります。

実装するときの注意としてLogとるときに対数指定できない系の言語では自然対数かlog2で言い換えて書いたりする必要があります。(それらはだいたいどの言語にもある)

$m_i = log_{qi} n$ を求める部分に関してだいたい $\frac {log_e n} {log_e qi}$ ( $e$ は自然対数)とすると(計算の誤差とかも含めるとちょっとはずれるけど)近似するような気がしたのでそれを使えばよいです。端数が出ると思うので床関数をかけるのを忘れずに

あとそのまま $a$ に対してべき乗やり続けると桁数がやばくなるので適宜剰余とります。なんで剰余とっていいかというと $gcd(M-1, n)$ がとりたくて、この数はどちらも $p$ でわりきれる数なので $n$ で都度剰余とっても $M-1$ が $p$ の倍数であることは変わらないからですね。

素数判定はとりあえずフェルマーテストとか通せばいいと思います

ほんとは実装したかったけどGoだと数値計算処理が math/big と math に散ってて大変そうだったのでやめました。
床関数はmathにしかない！法指定のべき乗操作はmath/bigにしかない！みたいな感じ。

己の筋肉で中国剰余定理を書いて法つきのべき乗したり足りない実装をおぎなえばよいので、筋トレしてすべてをなぎ倒すパワーを手に入れてからからリベンジします

はじめに

p-1法とは

がわかると素因数 がわかる理由

の探し方どうやる？

の探し方まとめ

$M$ がわかると素因数 $p$ がわかる理由

$M$ の探し方どうやる？

$M$ の探し方まとめ