９．２１川原未鈴目次１、卒研テーマ２、今後の予定３、二次篩１、卒研テーマ平成１７年卒の熊木幸司さんの『複数多項式二次篩の数論システムNZMATHへの実装』を修正する。いくつかの修正するべき点はメールで指摘されている２、今後の予定１、熊木さんの修論を読み、理解する（１）篩を用いた素因数分解（二次篩・複数多項式二次篩）本日ココ（２）Block Lanczos 法（３）複数多項式二次篩の実装（４）実装後の考察２、どこを修正した方がいいのか自分で考えてみる３、メールで指摘されているところがどこか調べる４、修正してみる５、実装後の考察３、二次篩 Step １．因子基底を選択 B∈ ℕに対し因子基底 J ← 2 ∪ 𝑞 ∈ ℙ>2,≤𝐵 𝑛 𝑞 る 𝑛 + 𝑖 𝑖 ∈ ℕ≤𝐴 定理2.1.3PNTより 𝑠 = #𝐽 ~𝐵/2ｌｎ𝐵, #K=A とす平方剰余QR またA∈ ℕに対し K ← =1 とする平方剰余QR 𝑛 𝑞 P.48 ≔ １ (𝑛が法𝑞のQR。即ち𝑛 ≡ 𝑥 2 (mod 𝑞)となる𝑥 ∈ ℤが存在) 定理2.1.3（素数定理）PNT P.36 𝑛 #(ℙ≤𝑛 )~ ln 𝑛 戻る Step ２．線型関係収集(𝑓𝑘 がJ滑かな𝑘 ∈ 𝐾を決める) 𝑞 ∈ 𝐽で𝑞 > 2なら、各𝑒 ∈ ℕについて合同式𝑋 2 ≡ 𝑛 (mod 𝑞 𝑒 )の解を K内で小さい方から𝑋 = ℎ, 𝑋 = 𝑖,と二つとり、それから𝑞 𝑒 個置きにKを篩えば全合同式解が得られ、任意の𝑘 ∈ 𝐾で 𝑞 𝑒 ∣ 𝑓𝑘 ⟺ 𝑘 ∈ (ℎ + 𝑞 𝑒 ℤ) ∪ (𝑖 + 𝑞 𝑒 ℤ) となる。また、 2𝑒 ∣ 𝑓𝑘 𝑘 ∈ 𝐾, 𝑒 ∈ ℕ も得る。故に定理1.2.2PF（P.6）で定義した 𝑓𝑘 の𝑞指数𝑒（𝑘, 𝑞）∈ ℤ≥0 (𝑘 ∈ 𝐾, 𝑞 ∈ 𝐽)が判る。ここで或𝑞 ∈ 𝐽で𝑒（𝑘, 𝑞）> 0な𝑘 ∈ 𝐾の𝑓𝑘 を初めて求め、それがJ滑かなら 𝑒 𝑞 𝑞∈𝐽 𝑘,𝑞 = 𝑓𝑘 ≡ 𝑘 2 (mod 𝑛) となる. このような𝑘を個数𝑟 > 𝑠まで探し関係ベクトル集合V を得る. 例 1694を素因数分解 𝑛 = 1649 , 𝐽 = 2,5 , 𝑛 = 40, 𝐾 = 41,42,43,44,45, … 𝒌 41 42 43 44 45 46 47 𝑓𝑘 = 𝑘 2 − 𝑛 32 115 200 287 376 ・・・ 560 𝑞 = 5 (𝑒5 (𝑘)) 0 1 1 0 0 ・・・ 1 𝑞 = 25 (𝑒25 (𝑘)) 0 1 2 0 0 𝑞 = 2 (𝑒2 (𝑘)) 5 0 3 0 3 1 8 𝑞 (𝑘) 25 × 50𝑞 𝑒= 32 ≡ 32 412 (mod 5 𝑛) 200 𝑞∈𝐽 23 × 52 = 200 ≡ 432 (mod 𝑛) ・・・５個おき・・・・・・両辺かけると 28 × 52 ≡ (41・43)2 (mod 𝑛) ≡ 1142 (mod 𝑛) gcd(28 × 52 − 114, 𝑛)= 17