nを法とする原始根

モジュラー算術において、数 $gが$ $n$ を法とする原始根 であるとは、 $n$ $と互いに素$ $な$ すべての数a が $n$ を法とする $g$ のべき乗と合同であることを意味する。つまり、 $n$ $と互いに素なすべての整数 a$ に対して、 g $k$ $\equiv$ ^$a$ ( $mod$ n $)$ となる整数 $k$ が存在することを意味する。このような値 $kは、 n を法とする$ $g$ を底とするa $の$ 指数または離散対数と呼ばれる。したがって、 $g が$ $nを法とする$ 原始根であるためには、 $g が$ $n$ $を$ 法とする整数の乗法群の生成元となる必要がある。

ガウスは『算術論』（1801年）第57条で原始根を定義し、オイラーがその用語を作ったと認めた。第56条では、ランベルトとオイラーが原始根を知っていたと述べているが、素数 $n$ に対して原始根が存在することを厳密に証明したのはガウスが初めてである。実際、『算術論』には2つの証明が含まれている。第54条の証明は非構成的存在証明であり、第55条の証明は構成的存在証明である。

原始根が存在するのは、nが1、2、4、p ^k、または2 p ^k（ただしpは奇数の素数、k > 0）のときである。それ以外のnの値では、 nを法とする整数の乗法群は巡回的ではない。^[1]^[2]^[3]これはガウスによって初めて証明された。^[4]

基本的な例

3は7を法とする原始根である^[5]。なぜなら ${\begin{array}{rcrcrcrcrcr}3^{1}&=&3^{0}\times 3&\equiv &1\times 3&=&3&\equiv &3{\pmod {7}}\\3^{2}&=&3^{1}\times 3&\equiv &3\times 3&=&9&\equiv &2{\pmod {7}}\\3^{3}&=&3^{2}\times 3&\equiv &2\times 3&=&6&\equiv &6{\pmod {7}}\\3^{4}&=&3^{3}\times 3&\equiv &6\times 3&=&18&\equiv &4{\pmod {7}}\\3^{5}&=&3^{4}\times 3&\equiv &4\times 3&=&12&\equiv &5{\pmod {7}}\\3^{6}&=&3^{5}\times 3&\equiv &5\times 3&=&15&\equiv &1{\pmod {7}}\end{array}}$

ここで、 3 ^$k$を法とした周期は 6 であることがわかります。この周期内の剰余は 3、2、6、4、5、1 であり、7 を法としたすべての非ゼロの剰余を並べ替えたものになるため、3 は確かに 7 を法とした原始根であることを意味します。これは、 n を法とすると有限個の値が生成されますので、シーケンス ( g k modulo n ) は常に k のある値の後で繰り返されるという事実から生じます $。$ g が n を法とした原始根で n が素数の場合、 $繰り返し$ ^$の$周期 $は$ n $-$ $1$ $です$ 。この $よう$ に $し$ て作成された順列 (およびその循環シフト) は、コスタス配列であることが示されています。

意味

$n が$ 正の整数であるとき、1 から $n$ − 1までの $n$ と互いに素な整数（または、 $nと互いに素な$ 合同類）は、 $n$ を法とする乗算を演算とする群を形成し、これは次のように表される。 $\mathbb {Z}$ ^×
_$n$ $であり、 n$ を法とする単位群、または $n$ を法とする原始類群と呼ばれる。「 $n$ を法とする整数の乗法群」の記事で説明したように、この乗法群（ $\mathbb {Z}$ ^×
_$n$）が巡回的である 場合、かつその場合のみ、 $n$ は2、4、 $p k$ 、または2 $p k$ $（p k$ は奇数の素数のべき乗）である。^[6]^[2]^[7]この群が巡回的である場合（かつその場合のみ）、 $\mathbb {Z}$ ^×
_$n$が巡回的な場合、この巡回群の生成元は $nを$ 法とする原始根^[8]（またはより完全な言葉で $n$ を法とする原始単位根と呼ばれ、単位多項式方程式Xの基本解としての役割を強調する）と呼ばれる。^{$メートル$}
− 1 の環_$n$）、あるいは単に $\mathbb {Z}$ $\mathbb {Z}$ ^×
_$n$。

いつ $\mathbb {Z}$ ^×
_$n$は非巡回的であるため、そのような $nを法とする原始元は存在しません。代わりに、$ $n$ の各素成分にはそれぞれ部分原始根が存在します（以下の例の $15 を参照）。$

任意の $n$ （ $\mathbb {Z}$ ^×
_$n$巡回的である）、 $\mathbb {Z}$ ^×
_$n$はオイラーのトーシェント関数 $φ$ ( $n$ ) （OEISのシーケンスA000010 ）によって与えられます。そして、オイラーの定理によれば、 $n$ と互いに素な任意の $a$ に対して、 $a$ ^$φ$⁽^$n$⁾ ≡ 1 (mod $n$ )が成り立ちます。n を法として 1 と合同となる $a$ の最小のべき乗は、 $nを法として$ $a$ の乗法位数と呼ばれます。特に、 $a が$ $n$ $を$ 法として原始根となるためには、 $a$ ^$φ$⁽^$n$^{) は} $n$ を法として 1 と合同となる $a$ の最小のべき乗でなければなりません。

例

例えば、 $n$ = 14の場合、 $\mathbb {Z}$ ^×
_$n$は合同類{1, 3, 5, 9, 11, 13}であり、 $φ$ (14) = 6個存在する。以下は14を法とするそれらの冪の表である。

xx、x ²、x ³、...（14を法とする） 1：1 3：3、9、13、11、5、1 5：5、11、13、9、3、1 9 : 9, 11, 111:11、9、113 : 13, 1

1 の位数は 1、3 と 5 の位数は 6、9 と 11 の位数は 3、13 の位数は 2 です。したがって、3 と 5 は 14 を法とする原始根です。

2つ目の例として、 $n$ = 15とします。 $\mathbb {Z}$ ^×
₁₅は合同類{1, 2, 4, 7, 8, 11, 13, 14}であり、その数は $φ$ (15) = 8である。

xx、x ²、x ³、...（15を法とする） 1：1 2：2、4、8、1 4 : 4, 1 7：7、4、13、1 8：8、4、2、111 : 11, 113:13、4、7、114 : 14, 1

8の位数を持つ数は存在しないので、15を法とする原始根は存在しない。実際、 $λ$ (15) = 4であり、 $λ$ はカーマイケル関数である。（OEISのシーケンスA002322）

原始根表

原始根を持つ数は次のような形をしている。 $n$

n\in \{1,2,4,p^{k},2\cdot p^{k}\;\;|\;\;2<p{\text{ prime}};\;k\in \mathbb {N} \},

= {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, ...}. ^[9]

これらは、 OEISのシーケンス A033948 にも保持されている番号です。 $n$ $\varphi (n)=\lambda (n),$

$次の表は、 n を$ 法とするまでの原始根を示します。 $n=31$

⁠ ⁠ $n$	原始根を法とする⁠ ⁠ $n$	順序（（OEISのシーケンスA000010）） $\varphi (n),$	指数（（OEISのシーケンスA002322）） $\lambda (n),$
1	0	1	1
2	1	1	1
3	2	2	2
4	3	2	2
5	2、3	4	4
6	5	2	2
7	3、5	6	6
8		4	2
9	2、5	6	6
10	3、7	4	4
11	2、6、7、8	10	10
12		4	2
13	2、6、7、11	12	12
14	3、5	6	6
15		8	4
16		8	4
17	3、5、6、7、10、11、12、14	16	16
18	5、11	6	6
19	2、3、10、13、14、15	18	18
20		8	4
21		12	6
22	7、13、17、19	10	10
23	5、7、10、11、14、15、17、19、20、21	22	22
24		8	2
25	2、3、8、12、13、17、22、23	20	20
26	7、11、15、19	12	12
27	2、5、11、14、20、23	18	18
28		12	6
29	2、3、8、10、11、14、15、18、19、21、26、27	28	28
30		8	4
31	3、11、12、13、17、21、22、24	30	30

プロパティ

ガウスは、任意の素数 $p （$ $p$ = 3を除く）に対して、その原始根の積は $pを法として1と合同であることを証明した$ ^[10]。

彼はまた、任意の素数 $p$ に対して、その原始根の和はpを法としたμ(p−1)と合同である $こと$ $を$ 証明 $し$ た^[11] 。ここで $μは$ メビウス関数である。

例えば、

$p$ = 3,	$μ$ （2）＝−1である。	原始根は 2 です。
$p$ = 5,	$μ$ （4）＝0である。	原始根は 2 と 3 です。
$p$ = 7,	$μ$ （6）＝1である。	原始根は 3 と 5 です。
$p$ = 31、	$μ$ （30）＝−1である。	原始根は 3、11、12、13、17、21、22、24 です。

たとえば、後者の原始根の積はであり、それらの和はです。 $2^{6}\cdot 3^{4}\cdot 7\cdot 11^{2}\cdot 13\cdot 17=970377408\equiv 1{\pmod {31}}$ $123\equiv -1\equiv \mu (31-1){\pmod {31}}$

が素数を法とする原始根である場合、となります。 $a$ $p$ $a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}$

アルティンの原始根に関する予想は、完全な平方数でも -1 でもない整数 $a が$ 、無限個の素数を法とした原始根であるというものである。

原始的なルーツを見つける

$n$ を法とする原始根を計算するための単純な一般公式は知られていない。^[a]^[b]しかし、すべての候補を単純に試すよりも速く原始根を求める方法はある。nを法とする数 $mの$ 乗法位数（その指数 $）$ が（ $\varphi (n)$ $\mathbb {Z}$ ^×
_$n$）であれば、それは原始根です。実際、逆もまた真です。つまり、 $m が$ $n$ を法とする原始根である場合、 $m$ の乗法順序はです。これを用いて、候補となる $m$ が原始根であるかどうかをテストできます。 $\varphi (n)=\lambda (n)~.$

まず、を計算し、の異なる素因数、例えば $p$ ₁ , ..., $p$ $k$ を決定する。最後に、を計算する。 $n>1$ $\varphi (n)~.$ $\varphi (n)$

g^{\varphi (n)/p_{i}}{\bmod {n}}\qquad {\mbox{ for }}i=1,\ldots ,k

2乗によるべき乗などの高速なべき乗剰余アルゴリズムを使用する。これらの $k個$ の結果がすべて1と異なる数 $g$ は原始根である。

$n$ を法とする原始根の数は、もし存在するならば^{[12]に等しい。}

\varphi \left(\varphi (n)\right)

一般に、 $r$ 個の元を持つ巡回群には生成元があるからです。 $\varphi (r)$

素数 $n$ の場合、これはに等しく、生成元は{2, ..., $n$ −1}の間で非常に一般的であるため、比較的簡単に見つけることができます。^[13] $\varphi (n-1)$ $n/\varphi (n-1)\in O(\log \log n)$

$gが$ $p を$ 法とする原始根である場合、 $g$ ^$p$⁻¹ ≡ 1 (mod p 2 )でない限り、 $gは$ $p k$ のすべてのべき乗を法とする原始根でもある。 g p −1 ≡ 1 (mod $p$ ² ) の場合は $g$ + $p$ が原始根である。^[14]

$gが$ $p k を$ 法とする原始根である場合、 $gは$ $p$ のすべての小さい累乗を法とする原始根でもあります。

$gが$ $p kを$ 法とする原始根ならば、 $g$ か $g$ + $p k$ （どちらか奇数）は2 $p k$ を法とする原始根である。^[14]

$p$ を法とする原始根を求めることは、 $pを法とする ($ $p$ − 1) 番目の円分多項式の根を求めることと同じです。

原始根の大きさの順序

$p$ を法とする最小の原始根 $g p$ (範囲1、2、...、 $p$ − 1)は一般に小さい。

上限

バージェス（1962）は^[15]^{[16] 、すべての}ε > 0に対して $C$ が存在し、 $g_{p}\leq C\,p^{{\frac {1}{4}}+\varepsilon }.$

グロスワルド（1981）は^[15]^[17]、もしならば、 $p>e^{e^{24}}\approx 10^{11504079571}$ $g_{p}<p^{0.499}.$

ショウプ（1990, 1992）は $[$ ^18]一般化リーマン予想を仮定して、gp = O(log6p)であること $を$ 証明^し $た$ 。

下限

フリドランダー（1949）とサリエ（1950）は、 $無限$ $個$ の素数に対してgp>Clogpとなる $正$ の $定数$ Cが存在することを $証明した$ ^[15]。

$任意の正の整数Mに対して、$ $M$ < $g$ $p$ < $p$ − $M$ を満たす素数が無限に存在することが基本的な方法^[15]で証明できる。

アプリケーション

$n$ を法とする原始根は、擬似乱数生成器^[19]や暗号技術（ディフィー・ヘルマン鍵交換方式を含む）でよく用いられる。音拡散器は、原始根や平方剰余といった数論的概念に基づいている^[20]^[21]。

参照

脚注

^ 「有限体理論における最も重要な未解決問題の一つは、原始根を構築するための高速アルゴリズムを設計することである。」von zur Gathen & Shparlinski 1998, pp. 15–24
^ 「[最小原始根]を計算するための便利な公式は存在しない。」ロビンズ 2006, p. 159

参考文献

^ ワイスタイン、エリック W.「モジュロ乗算グループ」。マスワールド。
^ ab 「原始根 - 数学百科事典」. encyclopediaofmath.org . 2024年11月5日閲覧。
^ (Vinogradov 2003, pp. 105–121, § VI 原始根と指数)
^ (ガウス 1986、第52～56条、第82～891条)
^ Stromquist, Walter. 「原始根とは何か？」数学. Bryn Mawr College. 2017年7月3日時点のオリジナルよりアーカイブ。 2017年7月3日閲覧。
^ ワイスタイン、エリック W.「モジュロ乗算グループ」。マスワールド。
^ Vinogradov 2003、pp. 105–121、§ VI 原始根と指数。
^ ヴィノグラドフ 2003、106ページ。
^ ガウス 1986、第92条。
^ ガウス 1986、第80条。
^ ガウス 1986、第81条。
^ ( OEISの配列A010554 )
^ Knuth, Donald E. (1998).半数値アルゴリズム. コンピュータプログラミングの芸術. 第2巻（第3版）. Addison–Wesley. セクション4.5.4、391ページ。
^ ab コーエン、ヘンリ(1993). 『計算代数的数論講座』ベルリン:シュプリンガー. p. 26. ISBN 978-3-540-55640-4。
^ abcd リベンボイム、パウロ(1996). 『素数記録の新書』ニューヨーク、NY:シュプリンガー. p. 24. ISBN 978-0-387-94457-9。
^ バージェス, DA (1962). 「特性和と原始根について †」 .ロンドン数学会報. s3-12 (1): 179– 192. doi :10.1112/plms/s3-12.1.179.
^ Grosswald, E. (1981). 「素数を法とする原始根のバージェス境界とΓ(p)への応用について」 . American Journal of Mathematics . 103 (6): 1171– 1183. doi :10.2307/2374229. ISSN 0002-9327. JSTOR 2374229.
^ バッハとシャリット 1996、p. 254.
^ Gentle, James E. (2003).乱数生成とモンテカルロ法（第2版）. ニューヨーク: Springer. ISBN 0-387-00178-6. OCLC 51534945。
^ Walker, R. (1990). モジュラー音響拡散素子の設計と応用(PDF) . BBC調査部 (レポート).英国放送協会. 2019年3月25日閲覧。
^ フェルドマン、エリオット (1995年7月). 「鏡面反射を無効化する反射格子：静寂の円錐」. J. Acoust. Soc. Am . 98 (1): 623– 634. Bibcode :1995ASAJ...98..623F. doi :10.1121/1.413656.

出典

バック、エリック、シャリット、ジェフリー（1996年）『効率的なアルゴリズム』『アルゴリズム的数論』第1巻、マサチューセッツ州ケンブリッジ：MIT出版、ISBN 978-0-262-02405-1。

Carella, NA (2015). 「最小素数原始根」.国際数学・コンピュータサイエンスジャーナル. 10 (2): 185–194 . arXiv : 1709.01172 .

『算術論』は、ガウスのキケロ語ラテン語から英語とドイツ語に翻訳されました。ドイツ語版には、彼の数論に関するすべての論文、すなわち、二次の相互性に関するすべての証明、ガウス和の符号の決定、双二次の相互性に関する考察、そして未発表の注釈が収録されています。

ガウス、カール・フリードリヒ(1986) [1801]。算数に関する議論。アーサー A. クラーク訳 (第 2 版、修正版)。ニューヨーク州ニューヨーク州：スプリンガー。ISBN 978-0-387-96254-2。

ガウス、カール・フリードリヒ(1965) [1801]。Unterschungen über höhere Arithmetik [高等算術の研究] (ドイツ語)。 Maser, H. 訳（第 2 版）。ニューヨーク州ニューヨーク州: チェルシー。ISBN 978-0-8284-0191-3。

ロビンズ、ネヴィル（2006年）『初級数論』ジョーンズ＆バートレット・ラーニング社、ISBN 978-0-7637-3768-9。

Vinogradov, IM (2003). 「§ VI 原始根と指数」. 『数論の要素』 . ミネオラ, ニューヨーク州: Dover Publications. pp. 105– 121. ISBN 978-0-486-49530-9。

フォン・ズール・ガテン, ヨアヒム; シュパルリンスキ, イゴール (1998). 「有限体におけるガウス周期の順序」.工学・通信・コンピューティングにおける応用代数. 9 (1): 15– 24. CiteSeerX 10.1.1.46.5504 . doi :10.1007/s002000050093. MR 1624824. S2CID 19232025.

さらに読む

オーレ、オイスタイン（1988年）『数論とその歴史』ドーバー社、pp. 284–302. ISBN 978-0-486-65620-5。。

外部リンク

ワイスタイン、エリック・W.「原始根」。MathWorld。
ホルト「二次剰余と原始根」数学、ミシガン工科大学。
「原始根計算機」BlueTulip。

[12] 「有限体理論における最も重要な未解決問題の一つは、原始根を構築するための高速アルゴリズムを設計することである。」von zur Gathen & Shparlinski 1998, pp. 15–24

[13] 「[最小原始根]を計算するための便利な公式は存在しない。」ロビンズ 2006, p. 159

[1] ワイスタイン、エリック W.「モジュロ乗算グループ」。マスワールド。

[:0-2] 「原始根 - 数学百科事典」. encyclopediaofmath.org . 2024年11月5日閲覧。

[Vinogradov2003.pp=105-121-3] (Vinogradov 2003, pp. 105–121, § VI 原始根と指数)

[4] (ガウス 1986、第52～56条、第82～891条)

[5] Stromquist, Walter. 「原始根とは何か？」数学. Bryn Mawr College. 2017年7月3日時点のオリジナルよりアーカイブ。 2017年7月3日閲覧。

[6] ワイスタイン、エリック W.「モジュロ乗算グループ」。マスワールド。

[Vinogradov2003.pp=105–121-7] Vinogradov 2003、pp. 105–121、§ VI 原始根と指数。

[8] ヴィノグラドフ 2003、106ページ。

[9] ガウス 1986、第92条。

[10] ガウス 1986、第80条。

[11] ガウス 1986、第81条。

[14] ( OEISの配列A010554 )

[Knuth-1998-15] Knuth, Donald E. (1998).半数値アルゴリズム. コンピュータプログラミングの芸術. 第2巻（第3版）. Addison–Wesley. セクション4.5.4、391ページ。

[Cohen1993-16] コーエン、ヘンリ(1993). 『計算代数的数論講座』ベルリン:シュプリンガー. p. 26. ISBN 978-3-540-55640-4。

[Ribenboim,_p.24-17] リベンボイム、パウロ(1996). 『素数記録の新書』ニューヨーク、NY:シュプリンガー. p. 24. ISBN 978-0-387-94457-9。

[18] バージェス, DA (1962). 「特性和と原始根について †」 .ロンドン数学会報. s3-12 (1): 179– 192. doi :10.1112/plms/s3-12.1.179.

[19] Grosswald, E. (1981). 「素数を法とする原始根のバージェス境界とΓ(p)への応用について」 . American Journal of Mathematics . 103 (6): 1171– 1183. doi :10.2307/2374229. ISSN 0002-9327. JSTOR 2374229.

[20] バッハとシャリット 1996、p. 254.

[21] Gentle, James E. (2003).乱数生成とモンテカルロ法（第2版）. ニューヨーク: Springer. ISBN 0-387-00178-6. OCLC 51534945。

[Walker-1990-22] Walker, R. (1990). モジュラー音響拡散素子の設計と応用(PDF) . BBC調査部 (レポート).英国放送協会. 2019年3月25日閲覧。

[Feldman-23] フェルドマン、エリオット (1995年7月). 「鏡面反射を無効化する反射格子：静寂の円錐」. J. Acoust. Soc. Am . 98 (1): 623– 634. Bibcode :1995ASAJ...98..623F. doi :10.1121/1.413656.