流れる空の中で数学を。

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

【素因数分解】円分多項式法の微改良とテスト計算

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

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

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

前回の記事の円分多項式法のプログラムをさらに改良しました。

sky-time-math.hatenablog.jp

$p\#_n$ を素数階乗としたとき、

$a_1=(p\#_n)^{(p\#_n^k)}-1$

$a_n=(a_{n-1})^{(p\#_n^k)}-1$

を計算し、

$gcd(a_n,N)$

から素因数を計算して、 $N$ を素因数分解するプログラムに少し改良？しました。

素数階乗に使う素数の個数、指数 $k$ 、数列の個数 $n$ の順に入力すれば計算できます。nlistに素因数分解したい数のリストを入れてください。

テストでは、10桁×20桁の素因数分解を100個行います。成功確率は、100000個の素数と $k=9,n=1$ で、約50%です。平均計算時間は4.5秒です。

gistbb369755c4507056bbdd7485fde21693