Cubic Residue and Cubic Root Modulo p 東京都立大学 理学部 数学科 藤代 武人
卒業研究のテーマ 前期のゼミでは 「平方剰余・mod pでの平方根」 について学びました. そこで・・・ 「立方剰余はどう計算する？」 以上の事を中心に後期では研究をしました.
本日の内容 Cubic Residue (立方剰余) Cubic Root (立方根)
Cubic Residue…? 定義 [ (rational) 立方剰余 ]
疑問… 平方剰余と同様のことはできるだろうか? 剰余記号 相互法則 (補充法則) ヤコビ記号 アルゴリズム
立方剰余記号 定義 [立方剰余記号]
立方剰余記号について 平方剰余記号の場合と同様のことが言える. multiplicity modularity generalize (ヤコビ記号)
立方剰余の相互法則 これらの法則は, 剰余記号を計算する上で重要な役割を 果たすことになる. (補充法則)
Algorithmのポイント 剰余記号は,先程の相互法則・補充法則 を繰り返し用いて計算する. (互除法のアルゴリズムと似ている.) 今回紹介するものの他にも立方剰余を求める アルゴリズムはある. 有理数を扱う場合には注意が必要なので, 次で触れることにする.
α:有理整数, β:有理素数の場合 β = 2 (mod 3) の有理素数の場合 ⇒ Z [ω] 上においても, β は素元となっているのでそのまま計算できる. β = 1 (mod 3) の素数の場合 ⇒
Algorithm (Cubic Residue)[1/2] α:有理整数, β:有理素数(mod 3 で1)の場合,β=ππとなるπを求めβとする. (これはcornacchiaのアルゴリズム[HP参照]を利用して計算する.)
Algorithm (Cubic Residue)[2/2]
mod p での平方根を求めるアルゴリズムを Cubic Root…? mod p で3乗根が存在するかどうかは, 確かめることができた. 実際に,根は何になるのか? どのように求める? mod p での平方根を求めるアルゴリズムを 3乗根へ拡張する!!
Algorithmのポイント [1/2] 入力に関して 解はひとつに定まる 解は３つある
具体的にはこの「g」と「k」を求めていくアルゴリズムである. Algorithmのポイント [2/2] 具体的にはこの「g」と「k」を求めていくアルゴリズムである.
Algorithm (Cubic Root) [1/2]
Algorithm (Cubic Root) [2/2]
計算量について Cubic Residue Cubic Root 平方根を求めるアルゴリズム(Tonelli-Shanks method)と 同様に, O (log4p) となる.
まとめ 相互法則等の証明は今回は省略しました． 詳細に関しては参考文献(*)(**)等を参照してください． また,pythonで作成したプログラム等は http://tnt.math.metro-u.ac.jp/labo/grad/2006/taketo/ にあります. 今後の課題 3乗根を求めるアルゴリズムについては さらに速く (O (log3p)で) 計算できるものがあります． このalgorithmをもとに, Cardanoの方法を用いて, Fp上での3次方程式を解くことも可能となります.
References(1/2) Ⅰ) Ⅱ) Ⅲ)
References(2/2) Ⅳ) Ⅴ)