shop99は 79円(税込83円)とか隣接した素数の値札あるよん。 最小原始根って・・・調べた。p が素数でn が原始根だとした場合 n^(p-1) % p == 1 というものだということはわかったけど、何につかうんでしょうか？
n^(p-1) % p == 1は俗にフェルマーの小定理というやつで、p-1乗すれば必ずpで割ったあまりは1になります。 しかしnの中には、p-1乗するまえに1になってしまう数もあります。 たとえばp=7とすると、 2^3 % 7 == 1 です。 しかし、素数を法とする世界では、必ずp-1乗しなければ1にならない数があるのです。これが原始根定理です。 そして、そういう数で最小のものをここでは紹介しています。 ちなみに7の場合は3です。 原始根の総数はp-1の約数と関係があります。 （ぶっちゃけた話1～p-1とp-1と互いに素の数と同じだけある） またnが原始根なら n^1, n^2, ..., n^(p-1)は mod pで考えればすべて異なる数となります。 この冪の性質はとても重要で、全部一通り現れるのですから、一様乱数などに使われます。 ちなみに、ブレイクダウンした視点でみれば、公開鍵暗号もこの応用です。
ああ、やっとわかりました。p-1 だから一様になるわけだ。 公開鍵暗号は本当に基本の基礎しか知りませんが、わかりやすい説明ありがとうございます。 なぜ最小かはまだわかんないけど、性質同じなら小さいほうが計算量が少ないとかそういうことでしょうかね
最小であるかどうかはあまり重要じゃないですね。まぁチョット計算が楽とか？実際1つの原始根がわかれば、すべての原始根は簡単に計算できます。 ただ最小の原始根を格素数に対して順番に並べると不規則に見えるのも事実で、そこがまた不思議だったり。