複数多項式二次篩

１．１１川原
未鈴
目次
１、実験結果
２、熊木さんのプログラムの問題点
３、今後
性能評価
・NZMATHにある熊木さんのプログラムで実験
・５０桁から６０桁の合成数について実験
・それぞれの実験の対象となった合成数は
ほぼ同じ桁数の素数２つの積であるような数とし
た
・各桁の約１０個の合成数に対し,平均時間
実験環境
 ハードウェア
AMD Phenom(tm) Ⅱ X6 1090T
Processor (3.2GHz 6cores)
Memory: 8GB
Disk:
HDD 2TB, SDD 64GB
CPU:
 システム
Server: Windows Server 2008 R2 Standard
Emulator: VMware(R) Player Ver.3.1.3
Linux OS: CentOS 5.5
(CPU: 4cores, Memory: 2GB,
HDD: 200GB )
 Python: 2.7.1
 NZMATH:1.1.0
１、実験結果
前回（time）
50桁
51桁
52桁
53桁
54桁
55桁
9331.4 11212.8 15699.9 19949.8 21601.6 24808.2
平均
（2.5）（3.1）（4.3）（5.5）（6）（6.8）
今回（clock）
50桁
平均
51桁
52桁
53桁
54桁
55桁
56桁
57桁
11520.3 12735.5 15002.3 19705.8 23466.1 27482.8 32469.7 36104.6
２、MPQSの問題点
（１）まず 𝑘 を決める。この𝑘は𝑘𝑛 ≡ 1(mod 4)をみた
し、
𝑘𝑛
𝑝𝑖
= 1, 𝑝𝑖 ∈ 𝐵なる𝑝𝑖 がなるべく多く取れるもの
が望ましい。とりわけ
8)となる𝑘を選ぶ。
𝑘𝑛
2
= 1とするには𝑘𝑛 ≡ 1(mod
例 𝑛＝5835505721を入力すると
𝑘=89として素因数分解を行っている。
5835505721 ×89＝ 519360009169を入力すると、
𝑘=１で済むはずなのに、わざわざ𝑘= 8089を使ってい
る。
今後
・５８桁から６０桁の合成数で実験
・今後どうするか考える

Download Report