タイトルは正確には「有限体の原始元」

体の乗法群の生成元のこと

\mathbb{F}_q=\{0,\alpha,\alpha^2,...,\alpha^{q-1}=1\}のとき\alphaを\mathbb{F}_qの原始元という

q-1乗して初めて1になるような\mathbb{F}_qの元のこと

つまり\alphaの位数はq-1

|\alpha|=q-1とかく

原始元を1乗、2乗としていけば\mathbb{F}_qの全ての元になる

例えば\mathbb{Z}_7の原始元を探す

以下のように元を一つずつ1乗、2乗、、と求めていけばいい

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は18の素因数

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

参考

『現代暗号の基礎数理』 8章