GMP_ECMによる素因数分解

概要

(岩波書店『科学』編集部 2024) にあった”RSAと素因数分解”に GMP-ECM が紹介されていたので、実際に動かしてみた。

GMP-ECMの準備

ZIMMERMANN Paul / ecm · GitLab を利用した。 

git clone https://gitlab.inria.fr/zimmerma/ecm.git

INSTALL.dev にある記載のように実行して、コンパイルした。 

cd ecm
autoreconf -i
./configure
make -j4
make check

コンパイル後に実行ファイル ecm がフォルダに生成されている。

素数の生成

2つの素数を生成して、素因数分解のための合成数を用意する。 

import sympy

N = 100
p1 = sympy.randprime(2**(N+1), 2**(N+2))
p2 = sympy.randprime(2**(N+1), 2**(N+2))

print(f'{p1=}')
print(f'{p2=}')
print(f'{p1*p2=}')

p1=2869069113607969685726929882709
p2=3871722605512470843352197003061 
p1*p2=11108239743933603608670116823884965417896735085597594043972249

2つの素数p1, p2から合成数: 11108239743933603608670116823884965417896735085597594043972249 を得た。

実行

GMP-ECM の使い方 の USAGE を参考にコマンドのオプションの引数を決定した。未知の素因数の桁数が30桁なので表から以下の値を採用した。

  • -c(反復): 500
  • B1: 250000

結果の最後部をみると、合成数が元の2つの素数に分解されていることが分る。 

echo 11108239743933603608670116823884965417896735085597594043972249 | ./ecm -c 500 250000


GMP-ECM 7.0.6-dev [configured with GMP 6.3.0, --enable-asm-redc, --enable-assert] [ECM]
Input number is 11108239743933603608670116823884965417896735085597594043972249 (62 digits)
Using B1=250000, B2=128992510, polynomial Dickson(3), sigma=1:4010257250
Step 1 took 77ms
Step 2 took 70ms
Run 2 out of 500:
Using B1=250000, B2=128992510, polynomial Dickson(3), sigma=1:2451171661
Step 1 took 70ms
Step 2 took 69ms
Run 3 out of 500:
Using B1=250000, B2=128992510, polynomial Dickson(3), sigma=1:2557109986
Step 1 took 70ms
Step 2 took 69ms

...

Run 18 out of 500:
Using B1=250000, B2=128992510, polynomial Dickson(3), sigma=1:504643144
Step 1 took 70ms
Step 2 took 70ms
Run 19 out of 500:
Using B1=250000, B2=128992510, polynomial Dickson(3), sigma=1:2975852467
Step 1 took 70ms
Step 2 took 71ms
********** Factor found in step 2: 2869069113607969685726929882709
Found prime factor of 31 digits: 2869069113607969685726929882709
Prime cofactor 3871722605512470843352197003061 has 31 digits

参考文献

岩波書店『科学』編集部, ed. 2024. 科学2024年3月号［雑誌］. Kindle版. 岩波書店. https://lead.to/amazon/jp/?op=bt&la=ja&key=B0CW1DZS1W.