もう一人のY君

iPhoneアプリのレビューやアップデートレビューなどを書いています. たまに数学の記事も書きます.

もう一人のY君 MENU

【ショートカット】原始根を求めるショートカット(正攻法)

181110_42

 今回は原始根を求めるショートカットです.

 ひねったやり方は行わず定義に従って素直にやっているため処理速度に難ありです.

 

ショートカット

ショートカット

  • Apple
  • 仕事効率化
  • 無料

※価格は記事執筆時のものです. 現在の価格はApp Storeから確認ください.

 レビュー時のバージョン : v2.1.1

 

スポンサーリンク

 

 

原始根の定義

blog.thetheorier.com

 

 フェルマーの定理より, 素数 { \displaystyle p } と { \displaystyle \text{gcd}(a,p)=1 } なる整数 { \displaystyle a } について,

 

{ \displaystyle a^{p-1}\equiv 1\pmod p }

 

が成り立ちます.

 

 しかし { \displaystyle a } と { \displaystyle p } の組み合わせ次第では, { \displaystyle p-1 } より小さい正指数 { \displaystyle e }

 

{ \displaystyle a^e\equiv 1\pmod p }

 

となる場合があります, この { \displaystyle e } について「{ \displaystyle a } は指数 { \displaystyle e } に対応する」と言います.

 

 もし整数 { \displaystyle a } が正指数 { \displaystyle p-1 } に対応する, つまり { \displaystyle p-1 } より小さな正指数 { \displaystyle e } で { \displaystyle a^e\equiv 1\pmod p } が成り立たないとき, { \displaystyle a } を { \displaystyle p } の原始根と言います.

 

 今回は素数 { \displaystyle p } に応じて決まる原始根を求めてみます.

 ちなみに素数 { \displaystyle p } の原始根は { \displaystyle \varphi(p-1) } 個存在します.

 

 またヒントとして, もし { \displaystyle a } が { \displaystyle p-1 } の原始根ならば

 

{ \displaystyle a^{\frac{p-1}{2}}\equiv 1\pmod p }

 

が成り立ち, かつ { \displaystyle a } が { \displaystyle p } の原始根ならば, { \displaystyle a } は { \displaystyle p-1 } の約数に対応します.

 

 上記よりその候補として確実に挙がるのが { \displaystyle \frac{p-1}{2} } になるわけですが, 実際にはもっと小さな正指数で対応する可能性もあります.

 従ってまず { \displaystyle \frac{p-1}{2} } からチェックし, カウントダウンしてチェックし続ける必要があります.

 2つ目の性質よりチェックの対象は { \displaystyle p-1 } の, もっと言えば { \displaystyle \frac{p-1}{2} } の約数ですが今回は律儀にカウントダウンする冗長なやり方になります.

 

 原始根は基本的に奇素数で扱うため, { \displaystyle \frac{p-1}{2} } はショートカット上では { \displaystyle \left[ \frac{p}{2} \right] } とすれば十分です(但し { \displaystyle p=3 } は自明のため扱いません, 従って { \displaystyle 5 } 以上の奇素数を扱うことになります).

 

 

フロー

181110_43

 まず素数の入力を要求し, そもそも素数であるかを判定させるため先日作った関数用の素数判定ショートカットを呼び出します.

 

 

181110_44

 その後メイン処理で必要になる { \displaystyle \left[ \frac{p}{2} \right]-1 } と { \displaystyle p-3 } を求めます(画像のコメントは誤りです).

 

 

181110_45

 メインの処理に移ります.

 原始根の候補として初期値2の変数 g0 を用意し, 

 

{ \displaystyle g_0^r,\,(g_0=2,3,\dots ,p-3,\,r=\left[ \frac{p}{2} \right],\dots ,2 ) }

 

について法 { \displaystyle p } で整除し, { \displaystyle 1 } になるかどうかをひたすら確かめます.

 

 

181110_46

 画像右下に見える合同式(累乗)の関数は, リターンとして絶対値最小剰余を返します.

 { \displaystyle -1\equiv p-1 } に一致したらその指数を対応する指数の候補として 変数 { \displaystyle r' } にも渡し, { \displaystyle r } を一つ減らして「繰り返す」を戻ります.

 

 

181110_47

 上の条件に一致しなかった場合は { \displaystyle r } を1つカウントダウンする処理だけを行います.

 

 

181110_48

 先程のループで得られた対応する指数候補 { \displaystyle r' } が { \displaystyle \left[ \frac{p}{2} \right] } に等しければ対応する g0 が原始根であることを意味するため, 配列として変数 x に代入します.

 そうでなければその g0 は原始根でないということです, よって g0 を1つ足して最初のループへ戻り, 同じ操作を繰り返します.

 結果変数 x には素数 p の原始根だけが配列として並ぶことになります.

 

 

実行

181110_49

 実際に実行してみると, 正しく原始根だけが並ぶことが確認できます.

 

 

 フロー自体に誤りはありませんが, 本来高々 { \displaystyle p-1 } の正約数についてのみ確認すれば良いものに対して { \displaystyle \frac{p-1}{2} } から { \displaystyle 2 } までを処理しているため, 実用に耐えるものでは残念ながらありません.

 上画像の { \displaystyle p=11 } ですら, 約48秒もかかっています.

 まともなショートカットにするためには先日も指摘した通り, 「繰り返す」の数や処理を減らすことはもとより, 原始根の性質に伴い, 指数は { \displaystyle \frac{p-1}{2} } の正約数にのみ絞ることです.

 代わりに対象の指数が { \displaystyle \frac{p-1}{2} } の約数かどうかを判定する必要があります.