原始元
primitive element
$ \mathbb{F}_q=\{0,\alpha,\alpha^2,...,\alpha^{q-1}=1\}のとき$ \alphaを$ \mathbb{F}_qの原始元という
$ q-1乗して初めて1になるような$ \mathbb{F}_qの元のこと
$ |\alpha|=q-1とかく
原始元を1乗、2乗としていけば$ \mathbb{F}_qの全ての元になる
例えば$ \mathbb{Z}_7の原始元を探す
以下のように元を一つずつ1乗、2乗、、と求めていけばいい
1が出たらそれ以上求める必要はない
table:a^n
1 2 3 4 5 6
0 0 0 0 0 0 0
1 1
2 2 4 1
3 3 2 6 4 5 1 ←
4 4 2 1
5 5 4 6 2 3 1 ←
6 6 1
よって3,5が原始元
ある数$ gが原始元かどうかを確かめる方法
$ p-1が$ p-1=q_{0}^{e_{0}} q_{1}^{e_{1}} \cdots q_{t}^{e_{t}}と素因数分解されたとする。このとき、$ gが$ \pmod pの原始元である必要十分条件は$ 0\le i\le tなる全ての$ iに対し、$ g^\frac{p-1}{q_i}\not\equiv1\pmod pとなる
$ 1\lt g\lt p-1
$ gは↑この範囲で当てずっぽうでガンバる
例
$ p=19に対して、$ \mathbb{Z}^\ast_pの生成元を求める
$ 19-1=18=2\times3^2
例えば$ g=2とすると、$ 2^{\frac{18}{2}},2^{\frac{18}{3}}に対して$ \pmod {19}を求める
$ 2^3\not\equiv1\pmod{19}
$ 2^2\not\equiv1\pmod{19}
なので、2は原始元
一つの原始元が見つかったら他の原始元は以下のようにしても求められる
$ \gcd(i,p-1)=1になる$ i
例えば上の問題では、原始元の一つが3だとわかった上で
$ p-7なので
$ \gcd(i,6)=1となる$ iは5
よって解は3,5
参考