原始根の計算が楽しい

有限体(mod素数)が大好きだ。有限体はなぜこんなに素朴におもしろいんだろう。逆元を求める計算からハマったのだと思う。ただ計算するだけで楽しい。

そんな計算の中でも一番楽しいと思うのが原始根を求めることだ。原始根は例えばmod５なら２のこと（３も）。１は２⁰、２は２¹、３は２⁴、４は２²。０でない全ての元がある数のべき乗で表せるとき、その元を原始根という。mod7なら3と5。

原始根の魅力。それは、原始根がわかれば、この体の掛け算の全てがわかること。平方剰余も立方剰余もわかる。べき乗の形の指数が偶数なら平方剰余。逆元もわかる。べき乗の指数の和が素数ー１で割れれば逆。

高速で求める特別な技術はしらないが、小さな工夫で早く求められる。

まずすぐにわかる８１から始め、間を埋めていくように計算すると、比較的速く計算できる。

有限体はきっと、ちっこいオモチャみたいだから楽しいのだろう。