流れる空の中で数学を。

とある数学好きの「手作りすうがく」と「気ままな雑記」。

【Python】ボツになった素因数分解アルゴリズム【数論】

オリジナルプチ研究プログラミング数学素因数分解

数学関連の絶版本・品切れ本をコチラから購入できます！

この記事では、自然数 $n$ が素数 $p,q$ を用いて、

$n=pq$

と表される場合を考える。この $n$ から $p,q$ を高速に求めたい。そこで、[text:sqrt{n}]と比べて大きすぎず小さ過ぎない適当な自然数 $m \ge 2$ をとり、

$x= [\sqrt{n} ] - ([\sqrt{n} ] \mod m)$

とすると、

$x \equiv 0 \mod m$

$x\sim O(\sqrt{n})$

となる。ここで、整数平方根のプログラムを用いた。

sky-time-math.hatenablog.jp

これを用いて、 $n$ を

$n=(x-cm+a)(x+dm+b)$

と表すことにする。ここで、 $0 \lt a,b\lt m$ は $\gcd(a,m)=\gcd(b,m)=1$ を満たす自然数である。

式変形して、

$M:=n^2-x^2=\{(d-c)m+a+b\}x-cdm^2+(ad-bc)m+ab$

となる。ここで、 $a,b \lt m$ が $c,d$ に比べて十分小さいとすると*1、この式は次のように近似できるはずである。

$M\sim \{(d-c)m+a+b\}x-cdm^2$

これを $d$ について解くと、

$d\sim \frac{M-(a+b)x+cm}{m(x-cm)}$

となる。 $md \lt x$ なので、更に変形して、

$c \lt \frac{x^2+(a+b)x-M}{m+m x}\sim \frac{x}{m}$

となる。cをこの範囲でループさせて、 $x-cm+a$ が $n$ を割り切るか調べれば良い。

aの数の候補は、トーシェント関数 $\phi(m)$ となるので、このアルゴリズムの計算量は、

$\frac{\phi(m)}{m}x\sim\frac{\phi(m)}{m}\sqrt{n}$

となる。mを２から始まる素数の連続した積 $p_1 p_2 \cdots p_r$ にとることで、この計算量を短縮できる。このときの計算量は

$(1-1/2)(1-1/3)\cdots(1-1/p_r)\sqrt{n}$

となる。

しかし、これだけ短縮してもrsa100は残念ながら分解できなかった。こんなアイデアではダメなんだろう。もっと革新的なアイデアが必要なはずだ。

*1:これは、２つの素因数 $p,q$ が近すぎないことを意味する。このとき、 $c,d \gt 0$ である。