１０．１２川原未鈴目次・複数多項式二次篩について・複数多項式二次篩の長所・次回複数多項式二次篩基本 𝑋 2 ≡ 𝑌 2 (mod 𝑛), 𝑋 ≢ 𝑌(mod 𝑛)となる（𝑋, 𝑌）の組を見つける平方剰余 ≪二次篩QS≫ 𝑓 𝑥 = 𝑥2 − 𝑛 𝑝を素数とすると 𝑝 ∣ 𝑓(𝑥) ⟺ 𝑥 2 ≡ 𝑛(mod 𝑝) ⟺ 𝑛 𝑝 =1 𝑛 𝑞 ≔１ (𝑛 ≡ 𝑥 2 (mod 𝑞)となる𝑥 ∈ ℤが存在) 𝑛 2 相互法則でｌｇ 𝑞で計算できる 𝑞 𝑝1 𝑝2 4 = 𝑥1 2 − 𝑛 𝑝1 5 𝑝2 2 = 𝑥2 2 − 𝑛 両辺かける (𝑝1 3 𝑝2 3 )2 ≡ (𝑥1 𝑥2 )2 (mod 𝑛) いろいろな 𝑝 を試していく。 𝑝 ∣ 𝑓(𝑥)となる 𝑝の集合𝐵は因子基底。 𝐵‐smoothとなる𝑓 𝑥 をいくつか組み合わせて平方数となるようなものを選ぶ。 ≪複数多項式二次篩MPQS≫ 二次篩との違い：篩の対象となる多項式の違いアイデア① 𝑛 = 𝑏 2 − 𝑎𝑐となる 𝑎, 𝑏, 𝑐 を用いて𝐹 𝑥 アイデア② 𝑛 = 𝑏 2 − 4𝑎𝑐となる 𝑎, 𝑏, 𝑐 を用いて𝐺 𝑥 ① 𝐹 𝑥 = 𝑎𝑥 2 + 2𝑎𝑏𝑥 + 𝑐, 𝑛 = 𝑏 2 − 𝑎𝑐, 𝑎 = 𝑑 2 とする 𝑎𝐹 𝑥 = (𝑎𝑥 + 𝑏)2 −𝑛 𝑎1 𝑝1 𝑝2 3 = (𝑎1 𝑥1 + 𝑏1 ) 2 −𝑛 𝑎2 𝑝1 3 𝑝2 = (𝑎2 𝑥2 + 𝑏2 )2 −𝑛 両辺をかけると 𝑎1 𝑎2 𝑝1 4 𝑝2 4 ≡ (𝑎1 𝑥1 + 𝑏1 ) (𝑎2 𝑥2 + 𝑏2 ) 2 (mod 𝑛) 𝑎1 = 𝑑1 2 , 𝑎2 = 𝑑2 2 とすると (𝑑1 𝑑2 𝑝1 2 𝑝2 2 )2 ≡ (𝑎1 𝑥1 + 𝑏1 ) (𝑎2 𝑥2 + 𝑏2 ) 2 (mod 𝑛) ex. ② 𝐹 𝑥 = 𝑎𝑥 2 + 𝑏𝑥 + 𝑐, 𝑛 = 𝑏 2 − 4𝑎𝑐, 𝑎 = 𝑑 2 とする 4𝑎𝐹 𝑥 = (2𝑎𝑥 + 𝑏)2 −𝑛 4𝑎1 𝑝1 𝑝2 3 = (2𝑎1 𝑥1 + 𝑏1 ) 2 −𝑛 4𝑎2 𝑝1 3 𝑝2 = (2𝑎2 𝑥2 + 𝑏2 )2 −𝑛 両辺をかけると 16𝑎1 𝑎2 𝑝1 4 𝑝2 4 ≡ (2𝑎1 𝑥1 + 𝑏1 ) (2𝑎2 𝑥2 + 𝑏2 ) 2 (mod 𝑛) 𝑎1 = 𝑑1 2 , 𝑎2 = 𝑑2 2 とすると (4𝑑1 𝑑2 𝑝1 2 𝑝2 2 )2 ≡ (𝑎1 𝑥1 + 𝑏1 ) (𝑎2 𝑥2 + 𝑏2 ) 2 (mod 𝑛) ex. 複数多項式二次篩の長所 ⅰ.二次式𝐹 𝑥 の値の上限は𝑓 𝑥 の上限より小さいので、素因数分解できる可能性が高い。 ⅱ.区間の幅を小さくできる。完全に素因数分解される𝐹 𝑥 が不足の場合、新しい多項式を生成して、同じ区間で篩いなおす。区間を狭くしておくと、与えられた𝐹 𝑥 が分解される可能性が増す。 ⅲ.篩処理が完全に並列処理できる。 N個のプロッセサがあれば、各プロセッサに別の多項式を割り当てることができ、N倍速く処理できる。次回・篩処理を行う区間について・係数の決め方・熊木さんのプログラムで実験