Cubic Residue and Cubic Root Modulo p

Presentation on theme: "Cubic Residue and Cubic Root Modulo p"— Presentation transcript:

1 Cubic Residue and Cubic Root Modulo p
東京都立大学 理学部 数学科 藤代 武人

2 卒業研究のテーマ 前期のゼミでは 「平方剰余・mod pでの平方根」 について学びました. そこで・・・ 「立方剰余はどう計算する？」
以上の事を中心に後期では研究をしました.

3 本日の内容 Cubic Residue (立方剰余) Cubic Root (立方根)

4 Cubic Residue…? 定義 [ (rational) 立方剰余 ]

5 疑問… 平方剰余と同様のことはできるだろうか? 剰余記号 相互法則 (補充法則) ヤコビ記号 アルゴリズム

6 立方剰余記号 定義 [立方剰余記号]

7 立方剰余記号について 平方剰余記号の場合と同様のことが言える. multiplicity modularity generalize
(ヤコビ記号)

8 立方剰余の相互法則 これらの法則は, 剰余記号を計算する上で重要な役割を 果たすことになる. (補充法則)

9 Algorithmのポイント 剰余記号は,先程の相互法則・補充法則 を繰り返し用いて計算する. (互除法のアルゴリズムと似ている.)
今回紹介するものの他にも立方剰余を求める アルゴリズムはある. 有理数を扱う場合には注意が必要なので, 次で触れることにする.

10 α:有理整数, β:有理素数の場合 β = 2 (mod 3) の有理素数の場合 ⇒ Z [ω] 上においても,
β は素元となっているのでそのまま計算できる. β = 1 (mod 3) の素数の場合 ⇒

11 Algorithm (Cubic Residue)[1/2]
α:有理整数, β:有理素数(mod 3 で1)の場合,β=ππとなるπを求めβとする. (これはcornacchiaのアルゴリズム[HP参照]を利用して計算する.)

12 Algorithm (Cubic Residue)[2/2]

13 mod p での平方根を求めるアルゴリズムを
Cubic Root…? mod p で3乗根が存在するかどうかは, 確かめることができた. 実際に,根は何になるのか? どのように求める? mod p　での平方根を求めるアルゴリズムを 3乗根へ拡張する!!

14 Algorithmのポイント [1/2] 入力に関して 解はひとつに定まる 解は３つある

15 具体的にはこの「g」と「k」を求めていくアルゴリズムである.
Algorithmのポイント [2/2] 具体的にはこの「g」と「k」を求めていくアルゴリズムである.

16 Algorithm (Cubic Root) [1/2]

17 Algorithm (Cubic Root) [2/2]

18 計算量について Cubic Residue Cubic Root 平方根を求めるアルゴリズム(Tonelli-Shanks method)と
同様に, O (log4p) となる.

19 まとめ 相互法則等の証明は今回は省略しました． 詳細に関しては参考文献(*)(**)等を参照してください．
また,pythonで作成したプログラム等は にあります. 今後の課題 3乗根を求めるアルゴリズムについては さらに速く (O (log3p)で) 計算できるものがあります． このalgorithmをもとに, Cardanoの方法を用いて, Fp上での3次方程式を解くことも可能となります.

20 References(1/2) Ⅰ) Ⅱ) Ⅲ)

21 References(2/2) Ⅳ) Ⅴ)