もう一人のY君

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

もう一人のY君　MENU 　MENU

【数学】なるべく少ない計算量で指数表をつくる【原始根・指数】

数学

f:id:thetheorier:20200319115143p:plain

　指数表を作るためには, { \displaystyle a^b }という形の数をひたすら法で整除しなければなりません.

　なのでその作業をできるだけ減らしたい, それが今回の目的です.

 

 

スポンサーリンク

 

 

 

指数表作りに必要な定理たち

　原始根および指数表について, 過去にも面白い性質を見つけましたが何だかんだその証明にもたどり着けました.

　未証明が一つありますが既知のもを含め必要なものを紹介しましょう.

 

　なお, 本記事ではpを5以上の素数とします.

　「素数pについて～」とある場合でも2と3は無視します, 定理によってはp=3でも成り立ちます.

 

 

定理1

　素数{ \displaystyle p}とその任意の原始根{ \displaystyle r }について,

{ \displaystyle r^a\ \left( a\in\mathbb{N} \right) }が{ \displaystyle p }の原始根

⇔　{ \displaystyle \text{gcd}(a,p-1)=1 }

　これは原始根を学ぶ際に触れる既知のものです.

 

 

定理2

　素数{ \displaystyle p}とその任意の原始根{ \displaystyle r }, 自然数{ n\ ( =1,2,\cdots ,p-1 ) }について,

{ \displaystyle \left| \text{Ind}_r\left( n \right)-\text{Ind}_r\left( p-n \right) \right|\ \equiv\ \frac{ p-1 }{ 2 } \pmod {p-1} }

　{ \displaystyle n\equiv -p+n\pmod p }ですから,

{ \displaystyle \text{Ind}_rn \equiv \text{Ind}_r(-p+n)\pmod{p-1} \\ \equiv \text{Ind}_r( (-1)(p-n) ) \\ \equiv \text{Ind}_r(-1)+\text{Ind}_r(p-n) \\ \equiv \frac{p-1}{2}+\text{Ind}_r(p-n) }

 　によって成り立ちます.

 

　ようは, 指数表の真ん中を軸にした両端の値の差の絶対値を取ったものが必ず{ \displaystyle \frac{p-1}{2} }となります.

 

 

f:id:thetheorier:20200318145236p:plain

　参考までにp=7の場合を見てみます.

　p=7の場合はp-1=6項あるわけですが, その真中である3と4を軸にその両端の差を取り更に絶対値を取るとそれぞれ

|0-3|=3 |2-5|=3, |1-4|=3
|0-3|=3, |4-1|=3, |5-2|=3

とすべて3になっています.

 

 

推論3

　素数{ \displaystyle p}とその任意の原始根{ \displaystyle r,\ r' }について, { \displaystyle \text{Ind}_rn }と{ \displaystyle \text{Ind}_{r'}n }の偶奇は一致する

　上で紹介したp=7の指数表を縦に見ると, それぞれの偶奇は全部同じですね.

　少なくともp=37までの指数表については確認しています.

 

　今回の目的で必須ではありません.

 

 

定理4

　素数{ \displaystyle p}とその任意の原始根{ \displaystyle r }について,

{ \displaystyle rr' \equiv 1 \pmod p }

を満たす, { \displaystyle r }と異なる{ \displaystyle p }の原始根{ \displaystyle r' }が存在する

　これは原始根の定義から比較的簡単に導かれます.

　素数{ \displaystyle p }の任意の原始根{ \displaystyle r }はフェルマーの定理より

 

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

 

を満たします.

 

　{ \displaystyle r\neq p }ですから法はそのままに両辺を{ \displaystyle r }で割れるので

 

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

 

, よって{ \displaystyle rx\equiv 1 }の解が{ \displaystyle r' }に相当します.

　{ \displaystyle \text{gcd}(r,p)=1 }は原始根の定義より明らかですから, この合同方程式に解が存在することも明らかです.

 

　ではこの{ \displaystyle r^{p-2}\equiv\frac{1}{p} }は原始根なのか…という疑問が生じます.

　しかしこれは定理1より, { \displaystyle \text{gcd}(p-2,p-1)=1 }が明らかであることから簡単に分かります.

 

　今回の定理の例をp=17で見ると, 原始根は3,5,6,7,10,11,12,14の8つですがうまく組み合わせることで

 

{ \displaystyle 3\cdot 6\equiv 5\cdot 7\equiv 10\cdot 12 \equiv 11\cdot 14\equiv 1 }

 

であることが分かります.

 

　ただ肝心の1が原始根でないため, 代数学的には準群(quasi-group)に相当するんでしょうかね.

　乗法可換なのは明らかですから, このような{ \displaystyle r }と{ \displaystyle r' }のペアは1対1です.

　素数{ \displaystyle p }に対する原始根の個数は{ \displaystyle \phi(p-1) }であり, かつ3以上の自然数nについて{ \displaystyle \phi(n) }は2を約数に持ちますから, 指数表の項数は偶数, 従って任意の原始根はいづれかのペア{ \displaystyle (r,r') }の一方となり, 即ち原始根による集合はこのペアによって類別されます.

　このペア{ \displaystyle (r,r') }を本記事では「r-set」と呼ぶことにします.

 

 

系5

　素数{ \displaystyle p}に対して,

　{ \displaystyle p }の原始根の組{ \displaystyle (r_1,r_2) }がr-set

{ \displaystyle \Leftrightarrow\quad r_1^{p-2}\equiv r_2 \pmod p }

{ \displaystyle \Leftrightarrow\quad r_2^{p-2}\equiv r_2 \pmod p }

{ \displaystyle \Leftrightarrow\quad r_2 }は{ \displaystyle r_1x\equiv 1\pmod p }の解

{ \displaystyle \Leftrightarrow\quad r_1 }は{ \displaystyle r_x\equiv 1\pmod p }の解

　定理4を整理しただけです.

　仮に原始根の値が小さくても{ \displaystyle r_1^{p-2} }を整除するのは面倒ですから2つ目は計算を前提とすると必要のないものです.

 

 

定理6

　素数{ \displaystyle p}の任意のr-set { \displaystyle (r_1,r_2) }, 自然数{ \displaystyle n(=1,2,\cdots ,p-1) }について,

{ \displaystyle \text{Ind}_{r_1}n+\text{Ind}_{r_2}n\ \equiv\ 0\ \pmod {p-1} }

　指数についての定理

{ \displaystyle \text{Ind}_{r'}n\ =\ \text{Ind}_{r'}r\text{Ind}_rn }

より,

{ \displaystyle \text{Ind}_{r_2}n\ \\ \equiv\ \text{Ind}_{r_2}r_1\text{Ind}_{r_1}n \\ \equiv \text{Ind}_{r_2}r_2^{-1}\text{Ind}_{r_1}n \quad (*) \\ \equiv\ (-1)\text{Ind}_{r_2}r_2\text{Ind}_{r_1}n \\ \equiv\ -\text{Ind}_{r_1}n }

, よって{ \displaystyle \text{Ind}_{r_1}n+\text{Ind}_{r_2}n\equiv 0 }.

　指数{ \displaystyle \text{Ind} }は法{ \displaystyle p-1 }において合同関係にあるため, { \displaystyle \text{Ind}_{r_1}n+\text{Ind}_{r_2}n\equiv 0\pmod {p-1} }となります.

　また(*)はr-setの定義より{ \displaystyle r_1r_2\equiv 1\pmod p }より{ \displaystyle r_1\equiv r_2^{-1}\pmod p }が成り立つことを利用しています.

 

 

　定理2は固定の原始根に基づく「横の関係」でしたが, こちらは固定の自然数に対する「縦の関係」です.

 

f:id:thetheorier:20200318155833p:plain

　画像のように, r-set同士の値を足し合わせると, { \displaystyle p-1 }と合同になります.

 

 

　準備は以上です, ここから具体的に指数表を組んでみます.

 

 

 

指数表作り

　大まかな流れとしては, まずひとつでも良いので原始根を見つけ, 残りの原始根は定理1を使います.

 

　続いて定理4の後に書いたように

 

{ \displaystyle rx\ \equiv\ 1\ \pmod p }

 

を解くことでr-setを組みます.

 

　後は容易な累乗を優先して項目を追加し, そのたびに定理2と6を駆使して埋めていきます.

 

 

p=17での例

試しにそれなりの難易度であるp=17でやってみましょう.

 

 

準備

　素数17の原始根は3,5,6,7,10,11,12,14の8つです.

　一つ見つければあとは定理1を使って芋づる式に見つかります.

　{ \displaystyle r }が原始根であるためには{ \displaystyle r^{\frac{p-1}{2}}\equiv -1 \pmod p }である必要があるのと, 計算のしやすさから{ \displaystyle 2^8 }や{ \displaystyle 3^8 }などがどうなるか試します.

 

　続いてr-setを組みます.

　定理4で紹介したとおり, 法17について

 

{ \displaystyle 3\cdot 6\equiv 5\cdot 7\equiv 11\cdot 14\equiv 1 }

 

ですから, p=17のr-setは(3,6),(5,7),(11,14)の3組です.

 

 

f:id:thetheorier:20200318165446p:plain

　では分かるモノから入れてみます.

　左の背景色はr-set, n=8,9の背景色は表の中央を表しています.

 

　n=1の場合は自明, n=16についても先程の { \displaystyle r^{\frac{p-1}{2}}\equiv 1\pmod p }から, 原始根に関係なく{ \displaystyle \frac{17-1}{2}=8 }であることがわかります.

　また{ \displaystyle \text{Ind}_rr=1 }も自明ですからこれも簡単に埋められます, これによって定理2より{ \displaystyle \text{Ind}_r(17-r)=\frac{17-1}{2}+1=9 }を埋めることもできます.

 

 

f:id:thetheorier:20200319110052p:plain

　値1と9が埋まったので, 定理6より対応するr-setの値も埋めることができます(以降、背景が赤い場所が追加した部分).

　今回はp=17なので, 足して17になるように, r-setの片方の値が定まります.

　累乗の計算なしで埋められるのは, 今回はここまでです.

 

 

f:id:thetheorier:20200319110601p:plain

　仕方ないので2乗の値を計算して埋めていきます.

{ \displaystyle 3^2\equiv 9,\ 5^2\equiv 8,\ 6^2\equiv 2,\ 7^2\equiv15 \\ 10^2\equiv 15,\ 11^2\equiv 2,\ 12^2\equiv 8,\ 14^2\equiv 9 }

なので, 上画像のように値2が埋まります.

　{ \displaystyle 10,11,12,14 }はそれぞれ法17について{ \displaystyle -7,-6,-5,-3 }と合同ですからこれも利用します.

 

 

f:id:thetheorier:20200319111222p:plain

　追加した値2に対して, 定理2より値{ \displaystyle 2+\frac{17-1}{2}=10 }を埋めることができます.

 

 

f:id:thetheorier:20200319111505p:plain

 　追加した2と10に対して, 定理6より{ \displaystyle (17-1)-2=14 }と{ \displaystyle (17-1)-10=6 }が埋まります.

 

　まだ足りないので仕方ないです, 3乗も計算しましょう.

 

 

f:id:thetheorier:20200319112247p:plain

{ \displaystyle 3^3\equiv 10,\ 5^3\equiv 6,\ 6^3\equiv 12,\ 7^3\equiv 3 \\ 10^3\equiv 14,\ 11^3\equiv 5,\ 12^3\equiv 11,\ 14^3\equiv 7 }

より, 上画像のように値3が埋まります.

 

 

f:id:thetheorier:20200319112802p:plain

　追加した値3に対して, 定理2と6より, 値5,11,13を埋めることができます.

　これであとは4と12だけになりました.

 

 

f:id:thetheorier:20200319113419p:plain

　これまでの流れを見て分かった方も居られるでしょうが, あと4ヶ所埋まればすべて埋められます.

　計算のしやすさを考えて3,5,12,14の4乗を計算します.

{ \displaystyle 3^4\equiv 13,\ 5^4\equiv 13,\ 12^4\equiv 13,\ 14^4\equiv 13 }

なので上画像のように埋まります.

 

 

f:id:thetheorier:20200319113814p:plain

　残りはやはり定理2と6を使います.

　これでp=17の指数表が完成しました.

 

 

〆

　定理2と6のお陰で一つ確定するとその縦と横の1つずつが確定するため, 作業効率が格段に減ることとなります.

　すべての累乗を計算する手間を考えれば, 今回の例だと素数17に対して8つの原始根の15乗までを計算するのは面倒ですね, それが4乗の一部までで済むことになるのですから.

 

　本当は指定の原始根に対する指数表を簡単に作りたいというのが目的だったので回り道をしているように思えますが現状はこれが早いですね.

 

 

thetheorier