数論システムNZMATHに於ける素因数分解法MPQSの性能評価

Presentation on theme: "数論システムNZMATHに於ける素因数分解法MPQSの性能評価"— Presentation transcript:

1 数論システムNZMATHに於ける素因数分解法MPQSの性能評価
2012/1/25 首都大学東京　都市教養学部　理工学系　数理科学コース 　川原未鈴

2 目次 １、素因数分解法MPQSとは？ ２、既存のプログラムの性能評価 ３、改良点 ４、改良前・後のMPQSの性能比較 ５、今後の課題

3 １. 素因数分解法MPQSとは？ MPQS（複数多項式二次篩） 素因数分解法の一つである二次篩法(QS)に改良を加え
さらに効率のよい方法として考えられたもの。 1984年 QS　　　 71桁 1986年 MPQS　　87桁 1994年 MPQS　　129桁　　 　　　　（600人以上のボランティアと1600台のCPUを用いた）

4 複数多項式二次篩MPQS 基本原理 𝑋 2 ≡ 𝑌 2 (mod 𝑛), 𝑋≢±𝑌(mod 𝑛)となる（𝑋,𝑌）の組を見つける。 見つけたら
gcd(𝑋−𝑌 , 𝑛 ) を計算することで 𝑛 の約数が求まる。

5 二次篩QS （例: 𝑛 ＝3937） （１）𝑓 𝑥 = 𝑥 2 −𝑛 （２）因子基底 𝑛の平方剰余から２つとる 𝐵 ={2,3} 平方剰余 𝑛 𝑝 ≔ １(𝑛≡ 𝑥 2 (mod 𝑝)となる𝑥∈ℤが存在) 𝑓 𝑥 = 𝑥 2 −𝑛　　　　𝑝を素数とすると　　　　　　　　　　　　　𝑝∣𝑓 𝑥 　　　⟺ 𝑥 2 ≡𝑛(mod 𝑝) 　　　　　　　　　　　　　 　　 ⟺ 𝑛 𝑝 =1 なぜ 平方剰余？

6 （３）篩い 𝑛 =3937 𝑓 𝑥 = 𝑥 2 −𝑛, 𝑥= 𝑛 ±𝑚, 𝑚=1,2,⋯を考える 63 2 −𝑛= −𝑛= −𝑛= −𝑛= −𝑛= −𝑛= −𝑛= −𝑛= −𝑛=1104 ⋮ 𝑥 2 ≡𝑛(mod 𝑝) の解を考える 3 3 2 3 3 2 2 2 ３個おき 1 1 2 3 2 個おき 1 1 1 2 1

7 （３）因子基底だけで表される𝑓 𝑥 をとってくる
　　　 63 2 −𝑛=32= 2 5 　　　 65 2 −𝑛=288= 2 5 ∙ 3 2 （４）組み合わせてかける( 𝑋 2 ≡ 𝑌 2 (mod 𝑛))←ガウスの消去法 　　　 (63∙65) 2 ≡ ( 2 5 ∙3) 2 mod 𝑛 （５） gcd(𝑋−𝑌 , 𝑛 ) を計算 gcd 63∙65− 2 5 ∙3,𝑛 =31 ∴3937=31∙127

8 二次篩との違い：篩の対象となる多項式を複数とれる
𝑛= 𝑏 2 −4𝑎𝑐 となる 𝑎,𝑏,𝑐 を用いて 𝐹 𝑥 =𝑎 𝑥 2 +𝑏𝑥+𝑐…① とする ・二次式𝐹 𝑥 の係数を変えても 同じ因子基底で篩にかけることが出来る ①の式に両辺4𝑎をかける 4𝑎𝐹 𝑥 =4 𝑎 2 𝑥 2 +4𝑎𝑏𝑥+4𝑎𝑐 = (2𝑎𝑥+𝑏) 2 − 𝑏 2 +4𝑎𝑐 = (2𝑎𝑥+𝑏) 2 −𝑛 ・篩い処理が完全に並列処理できる 𝑝∣𝑎𝐹 𝑥 ⟺ (2𝑎𝑥+𝑏) 2 ≡𝑛(mod 𝑝) ⟺ 𝑛 𝑝 =1 (因子基底は二次篩と同じ)

9 MPQSの流れ （１）まず 𝑘 を決める。この𝑘は𝑘𝑛≡1(mod 4)をみたし、 𝑘𝑛 𝑝 𝑖 =1, 𝑝 𝑖 ∈𝐵なる 𝑝 𝑖 がなるべく多く取れるものが望ましい。 とりわけ 𝑘𝑛 2 =1とするには𝑘𝑛≡1(mod 8)となる𝑘を選ぶ。 （２）多項式を決定。 (係数を決定) （３）篩いを行い各 𝑝 𝑖 ∈𝐵に対して𝐹 𝑥 ≡0 (mod 𝑝 𝑖 )なる𝑥を求めて、 𝐵‐smoothな𝐹 𝑥 を探す。 （４）𝐵‐smoothなものが必要な個数集まるまで（２）,（３）を 何回か繰り返し、その中から 𝐹 𝑥 が平方数になるようなものを探す。 （ガウスの消去法） （５） 𝑠 2 ≡ 𝑡 2 (mod 𝑛)が求められるので、 gcd(𝑠−𝑡,𝑛)が自明でない因数ならば終了。

10 （１）𝑛 が奇合成数、 𝑏 2 −4𝑎𝑐=𝑛 ⇒ 𝑏 2 ≡1(mod 4) ∴𝑛≡1(mod 4)としなければならない。 そこで、𝑛≡3(mod 4)となる 𝑛 に対しては 𝑘𝑛≡1(mod 4)となる小さな 𝑘 を求める。 この𝑘は 𝑘𝑛 𝑝 𝑖 =1, 𝑝 𝑖 ∈𝑃なる 𝑝 𝑖 がなるべく多く取れるものが望まし い。 とりわけ 𝑘𝑛 2 =1とするには𝑘𝑛≡1(mod 8)となる𝑘を選ぶ。

11 ２.既存のMPQSの性能評価 性能評価① ・NZMATHにあるmpqs（平成１７年卒の熊木幸司さんが書かれたも の）で実験・比較
・一つのCPUを使って約６時間で 　　どのくらいの桁数まで素因数分解できるか調べる ・実験の対象となった合成数は 　　ほぼ同じ桁数の素数２つの積であるような数とした ・50～55桁の約１０個の合成数に対し,桁ごとの平均時間を算出

12 実験環境 ハードウェア CPU: AMD Phenom(tm) Ⅱ X6 1090T Processor (3.2GHz 6cores) Memory: 8GB Disk: HDD 2TB, SSD 64GB システム Server: Windows Server 2008 R2 Standard Emulator: VMware(R) Player Ver Linux OS: CentOS (CPU: 4cores, Memory: 2GB, HDD: 200GB ) Python: 2.7.1 NZMATH: 1.1.0 以下実験結果はすべてsec

13 実験結果 約７時間弱で55桁の合成数を素因数分解できることがわかった 桁数 50桁 51桁 52桁 53桁 54桁 55桁 平均
9331.4 約７時間弱で55桁の合成数を素因数分解できることがわかった

14 性能評価② ・NZMATHにあるmpqsで実験 ・過程を （ⅰ）係数を決める （ⅱ）篩う （ⅲ）ガウスの消去法 （ⅳ）total に分けてそれぞれの時間を算出 ・ 10、15、20、25、30、35、40桁の合成数について実験 ・それぞれの実験の対象となった合成数は ほぼ同じ桁数の素数２つの積であるような数とした ・各桁の10個の合成数に対し,それぞれの平均時間を算出

15 実験結果 ・３つの過程の中で最も時間がかかっているのは篩いの部分 ・３つの過程以外のところでも多くの時間がかかっている 係数決め 篩い
10桁 15桁 20桁 25桁 30桁 35桁 40桁 係数決め 0.001 0.006 0.048 0.243 0.740 5.748 19.734 篩い 0.008 0.148 1.009 3.743 17.809 80.105 ガウスの消去法 0.002 0.004 0.052 0.289 1.683 10.049 85.323 Total time 0.019 0.073 0.358 1.983 8.340 43.080 その他の時間 0.015 0.110 0.443 2.175 9.474 57.823 ・３つの過程の中で最も時間がかかっているのは篩いの部分 ・３つの過程以外のところでも多くの時間がかかっている

16 ３、改良点 ≪改良後≫ ≪改良前≫ ≪問題箇所≫
（1）𝑘𝑛≡1(mod 4)をみたし、 𝑘𝑛 𝑝 𝑖 =1, 𝑝 𝑖 ∈𝐵なる 𝑝 𝑖 がなるべく多く取れる𝑘を決める。 とりわけ 𝑘𝑛 2 =1とするには𝑘𝑛≡1(mod 8)となる𝑘を選ぶ。 ≪改良前≫ 𝑛≡1 (mod 8)の場合にはすべて𝑘≡1(mod 8)をとってくる。 つまり𝑛≡1 (mod 8)の場合には 𝑛 𝑝 𝑖 =1, が𝑝 𝑖 =3,5,7,11,13 すべてに成り立っていても𝑘≡1(mod 8)をとってくる。 ≪改良後≫ 𝑛≡1 (mod 8) かつ (ⅰ) 𝑛 𝑝 𝑖 =1が 𝑝 𝑖 =3,5,7,11,13 すべてに成り立っていたら𝑘=1 (ⅱ) 𝑛 𝑝 𝑖 =1が 𝑝 𝑖 =3,5,7,11,13 で一つでも成り立っていなかったら𝑘≡1(mod 8)をとってくる。

17 ４、改良前・後の性能比較 ・改良前と改良後のプログラムで実験・比較 ・ 10、15、20、25、30、35、40桁の合成数について実験 ・それぞれの実験の対象となった合成数は 素数×素数× 𝑘 となるものを使用。 ・各桁の約10個の同じ合成数に対し,改良前・後のそれぞれの 平均時間を算出

18 実験結果 桁数 before after 10 0.021 0.016 15 0.101 0.031 20 0.424 0.223 25 1.942 0.841 30 11.602 5.513 35 48.827 21.658 40 𝑛 が mod 8 で １ ,かつ　法3,5,7,11,13の平方剰余の場合、 既存のものより圧倒的に速くなった

19 𝐵‐smoothにある程度近いものの残りの因子を因子基底の中に含ませてしまう方法
５、今後の課題 ・Block Lanczos法の実装 ・・・ガウスの消去法よりも効率の良い方法なので ・篩の行程でLarge Primeを取り入れた篩の実装 𝐵‐smoothにある程度近いものの残りの因子を因子基底の中に含ませてしまう方法

20 参考文献 ・中村憲．数論アルゴリズム ・Richard Crandall and Carl Pomerance． Prime numbers．Springer-Varlag,New York,2001. ・David M.Bressoud． Factorization and Primality Testing．Springer-Varlag,New York,1989． ・熊木幸司． 複数多項式二次篩の数論システムNZMATHへの実装とその考察,2005．

21 ご清聴ありがとうございました。