AKS実装part9 2011/12/21 伴地 慶介 目次 復習 累乗根の取り方 今後 AKS実装part9 2015/9/30 復習 分割統治法 値計算と補間 AKS実装part9 2015/9/30 累乗根の取り方 1 の原始 𝑛 乗根 これまでは・・・ 複素累乗根 例） 𝜔3 = 1, 𝜔 = −1+ 3𝑖 2 実際は・・・ 整数環 ℤ/𝑚 上 AKS実装part9 2015/9/30 𝑚 の取り方 異なる点の個数 𝑛 に対し ℤ/𝑚・・・ 𝑛 𝑚≔2 1 の原始 𝑛 乗根・・・ +1 𝑊𝑛1 = 2 2 複素累乗根と同様に再帰的な計算が可能 AKS実装part9 2015/9/30 証明 𝑊𝑛1 = 2 , 整数環 ℤ/𝑚 上 ① 𝑊𝑛1 ≠ 1 ② 𝑊𝑛𝑛 = 1 𝑛 𝑚 ≔2 2+1 2 ③ 𝑛 2 ≡ −1 mod 𝑚 𝑛−1 𝑖𝑘 𝑊 𝑛 𝑖=0 ⇒ ⇒ 2𝑛 ≡ 1 mod 𝑚 = 0 (0 ≤ 𝑘 ≤ 𝑛 − 1) 1 + 2𝑘 + 22𝑘 + ⋯ + 2 𝑛−1 𝑘 AKS実装part9 2015/9/30 例） 𝑛 = 8 ⇒ 𝑚 = 17 , ℤ/𝑚上 𝑊80 , 𝑊81 , 𝑊82 , 𝑊83 , 𝑊84 , 𝑊85 , 𝑊86 , 𝑊87 = 𝑊80 , 𝑊81 , 𝑊82 , 𝑊83 , 𝑊8−1 , 𝑊8−2 , 𝑊8−3 , 𝑊8−4 ℤ ∶ 1 , 2 , 4 , 8 , 16 , 32 , 64 , 128 ℤ/𝑚: 1 , 2 , 4 , 8 , −1 , −2 , −4 , −8 AKS実装part9 2015/9/30 乗算 (ⅰ) フーリエ変換 (ⅲ) フーリエ逆変換 (ⅱ) AKS実装part9 2015/9/30 例） 𝑓 𝑥 = 1 + 𝑥 + 𝑥 2 , 𝑔 𝑥 = 2 − 𝑥 ℎ 𝑥 =𝑓 𝑥 𝑔 𝑥 𝑛 = 4, 𝑚 = 5 = 2 4 2 +1 𝑊20 = 1, 𝑊21 = −1, 𝑊40 = 1, 𝑊41 = 2, 𝑊42 = −1, 𝑊43 = −2 𝑓(𝑥) の値計算 1 1 1 0 → 1 1 1 0 2 0 1 1 → -2 2 1 -2 𝑊4𝑖 𝑊2𝑖 3 2 1 -2 同様に 𝑔(𝑥) も計算 AKS実装part9 2015/9/30 𝑓 𝑊40 , 𝑓 𝑊41 , 𝑓 𝑊42 , 𝑓 𝑊43 𝑔 𝑊40 , 𝑔 𝑊41 , 𝑔 𝑊42 , 𝑔 𝑊43 ℎ 𝑊40 , ℎ 𝑊41 , ℎ 𝑊42 , ℎ 𝑊43 -2 0 -2 2 → -2 -2 0 2 → = [−2,2,1, −2] = [1,0, −2, −1] = −2,0, −2,2 -2 1 -1 -1 → 2 1 1 -1 ℎ 𝑥 = 2 + 𝑥 + 𝑥2 − 𝑥3 AKS実装part9 2015/9/30 今後 高速フーリエ変換実装 AKS用の高速フーリエ変換 AKS実装part9 2015/9/30 参考文献 宮崎彬 http://tnt.math.se.tmu.ac.jp/labo/grad/2004/akira/ index.html T.コルメン,C.ライザーソン,R.リベスト アルゴリズムイントロダクション AKS実装part9 2015/9/30
© Copyright 2024 ExpyDoc
