暗号理論の問題

$p-1=70=2\cdot 5\cdot 7$ である。$a$ の位数は $70$ の約数なので、$a$ が原始根であるための必要十分条件は
$$a^{70/2}=a^{35}\not\equiv 1,a^{70/5}=a^{14}\not\equiv 1,a^{70/7}=a^{10}\not\equiv 1(\mathrm{mod}71)$$
がすべて成り立つことである（位数が $70$ の真の約数 $d$ ならば、$d$ は $35,14,10$ のいずれかの約数になるため）。

$a^{35}$ の判定（オイラーの規準）　オイラーの規準より $a^{35}\equiv \left(\frac{a}{71}\right)(\mathrm{mod}71)$ である。したがって $a$ が法 $71$ の平方剰余なら $a^{35}\equiv 1$ となり原始根ではない。小さい $a$ から平方剰余かどうかを調べる。

• $a=1$：位数 $1$ で原始根ではない。
• $a=2$：$71\equiv 7(\mathrm{mod}8)$ なので第 2 補充法則より $\left(\frac{2}{71}\right)=1$。原始根ではない。
• $a=3$：$3\equiv 71\equiv 3(\mathrm{mod}4)$ なので平方剰余の相互法則より $\left(\frac{3}{71}\right)=-\left(\frac{71}{3}\right)=-\left(\frac{2}{3}\right)=-(-1)=1$。原始根ではない。
• $a=4=2^2$：平方剰余。原始根ではない。
• $a=5$：$5\equiv 1(\mathrm{mod}4)$ なので $\left(\frac{5}{71}\right)=\left(\frac{71}{5}\right)=\left(\frac{1}{5}\right)=1$。原始根ではない。
• $a=6$：$\left(\frac{6}{71}\right)=\left(\frac{2}{71}\right)\left(\frac{3}{71}\right)=1$。原始根ではない。
• $a=7$：$7\equiv 71\equiv 3(\mathrm{mod}4)$ なので $\left(\frac{7}{71}\right)=-\left(\frac{71}{7}\right)=-\left(\frac{1}{7}\right)=-1$。よって $7^{35}\equiv -1\not\equiv 1$。

$7^{14}$, $7^{10}$ の計算　法 $71$ で
$$7^2=49,7^4=49^2=2401=71\cdot 33+58\equiv 58,$$
$$7^8\equiv 58^2=3364=71\cdot 47+27\equiv 27,$$
$$7^{10}=7^8\cdot 7^2\equiv 27\cdot 49=1323=71\cdot 18+45\equiv 45\not\equiv 1,$$
$$7^{14}=7^{10}\cdot 7^4\equiv 45\cdot 58=2610=71\cdot 36+54\equiv 54\not\equiv 1.$$

以上より $7^{35},7^{14},7^{10}$ はいずれも $1$ と合同でないので、$7$ の位数は $70$ であり、$7$ は法 $71$ の原始根である。$1$ から $6$ はいずれも原始根でないので、求める最小の原始根は $7$ である。

$70=2\cdot 5\cdot 7$ なので、$g$ が原始根であることは $g^{35}\not\equiv 1$, $g^{14}\not\equiv 1$, $g^{10}\not\equiv 1(\mathrm{mod}71)$ と同値。

$g^{35}\equiv \left(\frac{g}{71}\right)$（オイラーの規準）なので、$g$ は平方非剰余でなければならない。
- $g=1$: 位数 1。不適。
- $g=2$: $71\equiv 7(\mathrm{mod}8)$ より $\left(\frac{2}{71}\right)=1$。平方剰余で不適。
- $g=3$: $3,71$ はともに $3\mathrm{mod}4$ なので $\left(\frac{3}{71}\right)=-\left(\frac{71}{3}\right)=-\left(\frac{2}{3}\right)=1$。不適。
- $g=4=2^2$: 平方数で不適。
- $g=5$: $\left(\frac{5}{71}\right)=\left(\frac{71}{5}\right)=\left(\frac{1}{5}\right)=1$。不適。
- $g=6=2\cdot 3$: 平方剰余どうしの積で平方剰余。不適。
- $g=7$: $\left(\frac{7}{71}\right)=-\left(\frac{71}{7}\right)=-\left(\frac{1}{7}\right)=-1$。平方非剰余なので $7^{35}\equiv -1\ne 1$。

$g=7$ について残りを確かめる。$7^2=49$, $7^4=2401\equiv 58$, $7^8\equiv 58^2=3364\equiv 27$。$7^{10}=7^8\cdot 7^2\equiv 27\cdot 49=1323\equiv 45\ne 1$。$7^{14}=7^{10}\cdot 7^4\equiv 45\cdot 58=2610\equiv 54\ne 1$。

よって 7 の位数は 70 で、最小の原始根は $7$。