数論アルゴリズム

二次篩
８．３川原未鈴
目次
 二次篩について
 二次篩手順
 計算量
二次篩QSについて
前回のICMの算法図式でStep０，３，４は
各種のICMに共通しているが、Step１と２の
因子基底選択と線型関係収集はいくつかの工夫ができ
る。
二次
篩
二次式𝑋 2 − 𝑛の値𝑓𝑘 ≔
𝑘 2 − 𝑛 mod 𝑛 ∈ ℤ/𝑛(𝑘 ∈
ℤ)を使う
二次篩手順
Step １．因子基底を選択
B∈ ℕに対し
因子基底 J
← 2 ∪ 𝑞 ∈ ℙ>2,≤𝐵
𝑛
𝑞
またA∈ ℕに対し
K ←
𝑛 + 𝑖 𝑖 ∈ ℕ≤𝐴
=1
とする
平方剰余QR
とする
定理2.1.3PNTより
𝑠 = #𝐽 ~𝐵/2ｌｇ𝐵, #K=A
Step２
例
量
計算
平方剰余QR
𝑛
𝑞
P.48
≔ １ (𝑛が法𝑞のQR。即ち𝑛 ≡ 𝑥 2 (mod 𝑞)となる𝑥 ∈ ℤが存在)
定理2.1.3（素数定理）PNT P.36
𝑛
#(ℙ≤𝑛 )~
ln 𝑛
Step1
Step ２．線型関係収集(𝑓𝑘 がJ滑かな𝑘 ∈ 𝐾を決める)
𝑞 ∈ 𝐽で𝑞 > 2なら、各𝑒 ∈ ℕについて
合同式𝑋 2 ≡ 𝑛 (mod 𝑞 𝑒 )の解を
K内で小さい方から𝑋 = ℎ, 𝑋 = 𝑖,と二つとり、
それから𝑞 𝑒 個置きにKを篩えば全合同式解が得られ、
任意の𝑘 ∈ 𝐾で
𝑞 𝑒 ∣ 𝑓𝑘 ⟺ 𝑘 ∈ (ℎ + 𝑞 𝑒 ℤ) ∪ (𝑖 + 𝑞 𝑒 ℤ)
となる。
また、 2𝑒 ∣ 𝑓𝑘 𝑘 ∈ 𝐾, 𝑒 ∈ ℕ も得る。
計算量
故に定理1.2.2PF（P.6）で定義した
𝑓𝑘 の𝑞指数𝑒（𝑘, 𝑞）∈ ℤ≥0 (𝑘 ∈ 𝐾, 𝑞 ∈ 𝐽)が判る。
ここで或𝑞 ∈ 𝐽で𝑒（𝑘, 𝑞）> 0な𝑘 ∈ 𝐾の𝑓𝑘 を初めて求め、
それがJ滑かなら
𝑒
𝑞
𝑞∈𝐽
𝑘,𝑞
= 𝑓𝑘 ≡ 𝑘 2 (mod 𝑛)
となる.
このような𝑘を個数𝑟 > 𝑠まで探し関係ベクトル集合V
を得る.
例
計算量
例
８８９２０９７３を素因数分解
88920973 ＝9429.7 …
94302 − 88920973＝3927＝3 × 7 × 11 × 17
94312 − 88920973＝22788 = 22 × 33 × 211
94322 − 88920973＝41651
94332 − 88920973＝60516 ＝22 × ３2 × 412
つまり，
88920973
2
＝94332 − （2 × 3 × 41）
＝（9433＋2 × 3 × 41）（9433 − 2 × 3 × 41）
＝9679 × 9187
Step１
Step２
計算量
Step１：注意2.3.3 (P.53)よりÕ（B lg 𝑛）
Step２：◦各𝑘 ∈ 𝐾で合同式解法が§2.3.3の
算法SQRTP,SQRTPPw（P.54）よりEZHの下で
3
計算量Õ(lg 𝑛)
◦𝑓𝑘 の計算量Õ（lg 𝑛）
3
故にStep２は全部で計算量Õ（A lg 𝑛）で、篩の回数は
𝐴𝐵
𝑂
lg 𝐵
この方法で計算量を決定する要素は滑かさの限界𝐴、𝐵が、
どの程度なら適切かという問題である。
例えば、 𝐴、𝐵が𝐿𝑛
ば良く、
1
,1
2
と同じ位で、𝐵< 𝐴<𝐵2 となるように取れ

Download Report