Primitivní kořenový modul $n$ - Primitive root modulo n - Wikipedia

v modulární aritmetika, pobočka teorie čísel, číslo $G$ je primitivní root modulo $n$ pokud každé číslo $A$ coprime na $n$ je shodný k moci $G$ modulo $n$ . To znamená $G$ je primitivní root modulo $n$ , pokud pro každé celé číslo $A$ coprime to $n$ , existuje nějaké celé číslo $k$ pro který $G$ ^$k$ ≡ $A$ (mod $n$ ). Taková hodnota $k$ se nazývá index nebo diskrétní logaritmus z $A$ na základnu $G$ modulo $n$ . Všimněte si, že $G$ je primitivní root modulo $n$ kdyby a jen kdyby $G$ je generátor multiplikativní skupina celých čísel modulo $n$ .

Gauss definované primitivní kořeny v Článek 57 z Disquisitiones Arithmeticae (1801), kde si připsal částku Euler s ražením termínu. v Článek 56 uvedl to Lambert a Euler o nich věděl, ale byl první, kdo důsledně prokázal, že primitivní kořeny existují pro primární $n$ . Ve skutečnosti Disquisitiones obsahuje dva důkazy: Jeden v Článek 54 je nekonstruktivní důkaz existence, zatímco důkaz v Článek 55 je konstruktivní.

Základní příklad

Číslo 3 je primitivní kořenový modul 7^[1] protože

{ displaystyle { begin {array} {rcrcrcrcrcr} 3 ^ {1} & = & 3 & = & 3 ^ {0} times 3 & equiv & 1 times 3 & = & 3 & equiv & 3 { pmod {7}} 3 ^ {2} & = & 9 & = & 3 ^ {1} krát 3 & ekviv & 3 krát 3 & = & 9 & ekviv & 2 { pmod {7}} 3 ^ {3} & = & 27 & = & 3 ^ {2} krát 3 & ekviv & 2 krát 3 & = & 6 & ekviv & 6 { pmod {7}} 3 ^ {4} & = & 81 & = & 3 ^ {3} krát 3 & ekviv & 6 krát 3 & = & 18 & ekv & 4 { pmod {7}} 3 ^ {5} & = & 243 & = & 3 ^ {4} krát 3 & ekviv & 4 krát 3 & = & 12 & ekviv & 5 { pmod {7}} 3 ^ { 6} & = & 729 & = & 3 ^ {5} krát 3 & ekviv & 5 krát 3 & = & 15 & ekviv & 1 { pmod {7}} 3 ^ {7} & = & 2187 & = & 3 ^ {6} krát 3 & ekviv & 1 krát 3 & = & 3 & ekviv & 3 { pmod {7}} konec {pole}}}

Zde vidíme, že doba ze dne 3.^$k$ modulo 7 je 6. Zbytky v období, které jsou 3, 2, 6, 4, 5, 1, tvoří přeskupení všech nenulových zbytků modulo 7, z čehož vyplývá, že 3 je skutečně primitivní kořenový modul 7. Toto pochází z skutečnost, že sekvence ( $G$ ^$k$ modulo $n$ ) se vždy opakuje po určité hodnotě $k$ , protože modulo $n$ vytváří konečný počet hodnot. Li $G$ je primitivní kořenový modul $n$ a $n$ je prime, pak je perioda opakování $n$ − 1 . Kupodivu se ukázalo, že takto vytvořené permutace (a jejich kruhové posuny) jsou Costasova pole.

Definice

Li $n$ je kladné celé číslo, celá čísla mezi 0 a $n$ − 1 to jsou coprime na $n$ (nebo ekvivalentně třídy shody coprime to $n$ ) tvoří a skupina, s násobením modulo $n$ jako operace; označuje se $ℤ$ ^×
_$n$ a nazývá se skupina jednotek modulo $n$ nebo skupina primitivních tříd modulo $n$ . Jak je vysvětleno v článku multiplikativní skupina celých čísel modulo $n$ , tato multiplikativní skupina ( $ℤ$ ^×
_$n$) je cyklický kdyby a jen kdyby $n$ se rovná 2, 4, $str k$ nebo 2 $str k$ kde $str k$ je síla lichého prvočíslo.^[2]^[3]^[4] Kdy (a pouze kdy) tato skupina $ℤ$ ^×
_$n$ je cyklický, a generátor této cyklické skupiny se nazývá a primitivní root modulo $n$ ^[5] (nebo v plnějším jazyce primitivní kořen jednoty modulo $n$ , s důrazem na jeho roli jako základního řešení EU kořeny jednoty polynomiální rovnice X^$m$
- 1 v kruhu $ℤ$ _$n$), nebo jednoduše a primitivní prvek $ℤ$ ^×
_$n$. Když $ℤ$ ^×
_$n$ je necyklický, takové primitivní prvky mod $n$ neexistuje.

Pro všechny $n$ (jestli ano nebo ne $ℤ$ ^×
_$n$ je cyklický), pořadí (tj. počet prvků v) $ℤ$ ^×
_$n$ darováno Eulerova totientová funkce $φ$ ( $n$ ) (sekvence.) A000010 v OEIS ). A pak, Eulerova věta říká to $A$ ^{$φ$ ( $n$ )} ≡ 1 (mod $n$ ) pro každého $A$ coprime to $n$ ; nejnižší výkon $A$ to je shodné s 1 modulo $n$ se nazývá multiplikativní pořadí z $A$ modulo $n$ . Zejména pro $A$ být primitivní kořenový modul $n$ , $φ$ ( $n$ ) musí být nejmenší síla $A$ to je shodné s 1 modulo $n$ .

Příklady

Například pokud $n$ = 14 pak prvky $ℤ$ ^×
_$n$ jsou třídy shody {1, 3, 5, 9, 11, 13}; existují $φ$ (14) = 6 z nich. Zde je tabulka jejich výkonů modulo 14:

 x x, x², X³, ... (mod 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

Pořadí 1 je 1, řádky 3 a 5 jsou 6, řádky 9 a 11 jsou 3 a řád 13 je 2. Tedy 3 a 5 jsou primitivní kořeny modulo 14.

Pro druhý příklad pojďme $n$ = 15 . Prvky $ℤ$ ^×
₁₅ jsou třídy shody {1, 2, 4, 7, 8, 11, 13, 14}; existují $φ$ (15) = 8 z nich.

 x x, x², X³, ... (mod 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

Protože neexistuje žádné číslo, jehož pořadí je 8, neexistují žádné primitivní kořeny modulo 15. Ve skutečnosti, $λ$ (15) = 4, kde $λ$ je Funkce Carmichael. (sekvence A002322 v OEIS )

Tabulka primitivních kořenů

Čísla, která mají primitivní kořen, jsou

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, 22, 23, 25, 26, 27, 29, 31, 34, 37, 38, 41, 43, 46, 47, 49, 50, 53, 54, 58, 59, 61, 62, 67, 71, 73, 74, 79, 81, 82, 83, 86, 89, 94, 97, 98, 101, 103, 106, 107, 109, 113, 118, 121, 122, 125, 127, 131, 134, 137, 139, 142, 146, 149, ... (sekvence A033948 v OEIS )

Toto je Gaussova tabulka primitivních kořenů z Disquisitiones. Na rozdíl od většiny moderních autorů ne vždy zvolil nejmenší primitivní kořen. Místo toho si vybral 10, pokud se jedná o primitivní kořen; pokud tomu tak není, vybral si kterýkoli kořen, který dává 10 nejmenší index, a pokud je jich více, vybral nejmenší z nich. To nejen usnadňuje ruční výpočet, ale používá se v § VI, kde se zkoumají periodická desetinná rozšíření racionálních čísel.

Řádky tabulky jsou označeny hlavní síly (s výjimkou 2, 4 a 8) méně než 100; druhý sloupec je primitivní root modulo tohoto čísla. Sloupce jsou označeny prvočísly menšími než 100. Položka v řádku $str$ sloupec $q$ je index $q$ modulo $str$ pro daný kořen.

Například v řádku 11 je 2 uveden jako primitivní kořen a ve sloupci 5 je položka 4. To znamená, že 2⁴ = 16 ≡ 5 (mod 11).

Pro index složeného čísla přidejte indexy jeho hlavních faktorů.

Například v řádku 11 je index 6 součtem indexů pro 2 a 3: $2 1 + 8 = 512 \equiv 6 (mod 11)$ . Index 25 je dvojnásobek indexu 5: $28 = 256 \equiv 25 (mod 11)$ . (Samozřejmě, protože $25 \equiv 3 (mod 11)$ , položka pro 3 je 8).

Tabulka je pro liché hlavní síly přímočará. Ale pravomoci 2 (16, 32 a 64) nemají primitivní kořeny; místo toho mocniny 5 tvoří o polovinu lichých čísel méně než mocninu 2 a jejich negativy modulují mocninu 2 o druhou polovinu. Všechny síly 5 jsou shodné s 5 nebo 1 (modulo 8); sloupce v čele s čísly shodnými s 3 nebo 7 (mod 8) obsahují index záporné hodnoty. (Sekvence A185189 a A185268 v OEIS )

Například modulo 32 index pro 7 je 2 a 5² = 25 ≡ −7 (mod 32), ale položka pro 17 je 4, a $54 = 625 \equiv 17 (mod 32)$ .

Primitivní kořeny a indexy
(ostatní sloupce jsou indexy celých čísel pod hlavičkami příslušných sloupců)
$n$	vykořenit	2	3	5	7	11	13	17	19	23	29	31	37	41	43	47	53	59	61	67	71	73	79	83	89	97
$n$	vykořenit	2	3	5	7	11	13	17	19	23	29	31	37	41	43	47	53	59	61	67	71	73	79	83	89	97
3	2	1
5	2	1	3
7	3	2	1	5
9	2	1	*	5	4
11	2	1	8	4	7
13	6	5	8	9	7	11
16	5	*	3	1	2	1	3
17	10	10	11	7	9	13	12
19	10	17	5	2	12	6	13	8
23	10	8	20	15	21	3	12	17	5
25	2	1	7	*	5	16	19	13	18	11
27	2	1	*	5	16	13	8	15	12	11
29	10	11	27	18	20	23	2	7	15	24
31	17	12	13	20	4	29	23	1	22	21	27
32	5	*	3	1	2	5	7	4	7	6	3	0
37	5	11	34	1	28	6	13	5	25	21	15	27
41	6	26	15	22	39	3	31	33	9	36	7	28	32
43	28	39	17	5	7	6	40	16	29	20	25	32	35	18
47	10	30	18	17	38	27	3	42	29	39	43	5	24	25	37
49	10	2	13	41	*	16	9	31	35	32	24	7	38	27	36	23
53	26	25	9	31	38	46	28	42	41	39	6	45	22	33	30	8
59	10	25	32	34	44	45	28	14	22	27	4	7	41	2	13	53	28
61	10	47	42	14	23	45	20	49	22	39	25	13	33	18	41	40	51	17
64	5	*	3	1	10	5	15	12	7	14	11	8	9	14	13	12	5	1	3
67	12	29	9	39	7	61	23	8	26	20	22	43	44	19	63	64	3	54	5
71	62	58	18	14	33	43	27	7	38	5	4	13	30	55	44	17	59	29	37	11
73	5	8	6	1	33	55	59	21	62	46	35	11	64	4	51	31	53	5	58	50	44
79	29	50	71	34	19	70	74	9	10	52	1	76	23	21	47	55	7	17	75	54	33	4
81	11	25	*	35	22	1	38	15	12	5	7	14	24	29	10	13	45	53	4	20	33	48	52
83	50	3	52	81	24	72	67	4	59	16	36	32	60	38	49	69	13	20	34	53	17	43	47
89	30	72	87	18	7	4	65	82	53	31	29	57	77	67	59	34	10	45	19	32	26	68	46	27
97	10	86	2	11	53	82	83	19	27	79	47	26	41	71	44	60	14	65	32	51	25	20	42	91	18

V následující tabulce jsou uvedeny primitivní kořeny modulo $n$ pro $n$ ≤ 72:

${ displaystyle n}$	primitivní kořeny modulo ${ displaystyle n}$	objednat (OEIS: A000010)	${ displaystyle n}$	primitivní kořeny modulo ${ displaystyle n}$	objednat (OEIS: A000010)
1	0	1	37	2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35	36
2	1	1	38	3, 13, 15, 21, 29, 33	18
3	2	2	39		24
4	3	2	40		16
5	2, 3	4	41	6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35	40
6	5	2	42		12
7	3, 5	6	43	3, 5, 12, 18, 19, 20, 26, 28, 29, 30, 33, 34	42
8		4	44		20
9	2, 5	6	45		24
10	3, 7	4	46	5, 7, 11, 15, 17, 19, 21, 33, 37, 43	22
11	2, 6, 7, 8	10	47	5, 10, 11, 13, 15, 19, 20, 22, 23, 26, 29, 30, 31, 33, 35, 38, 39, 40, 41, 43, 44, 45	46
12		4	48		16
13	2, 6, 7, 11	12	49	3, 5, 10, 12, 17, 24, 26, 33, 38, 40, 45, 47	42
14	3, 5	6	50	3, 13, 17, 23, 27, 33, 37, 47	20
15		8	51		32
16		8	52		24
17	3, 5, 6, 7, 10, 11, 12, 14	16	53	2, 3, 5, 8, 12, 14, 18, 19, 20, 21, 22, 26, 27, 31, 32, 33, 34, 35, 39, 41, 45, 48, 50, 51	52
18	5, 11	6	54	5, 11, 23, 29, 41, 47	18
19	2, 3, 10, 13, 14, 15	18	55		40
20		8	56		24
21		12	57		36
22	7, 13, 17, 19	10	58	3, 11, 15, 19, 21, 27, 31, 37, 39, 43, 47, 55	28
23	5, 7, 10, 11, 14, 15, 17, 19, 20, 21	22	59	2, 6, 8, 10, 11, 13, 14, 18, 23, 24, 30, 31, 32, 33, 34, 37, 38, 39, 40, 42, 43, 44, 47, 50, 52, 54, 55, 56	58
24		8	60		16
25	2, 3, 8, 12, 13, 17, 22, 23	20	61	2, 6, 7, 10, 17, 18, 26, 30, 31, 35, 43, 44, 51, 54, 55, 59	60
26	7, 11, 15, 19	12	62	3, 11, 13, 17, 21, 43, 53, 55	30
27	2, 5, 11, 14, 20, 23	18	63		36
28		12	64		32
29	2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27	28	65		48
30		8	66		20
31	3, 11, 12, 13, 17, 21, 22, 24	30	67	2, 7, 11, 12, 13, 18, 20, 28, 31, 32, 34, 41, 44, 46, 48, 50, 51, 57, 61, 63	66
32		16	68		32
33		20	69		44
34	3, 5, 7, 11, 23, 27, 29, 31	16	70		24
35		24	71	7, 11, 13, 21, 22, 28, 31, 33, 35, 42, 44, 47, 52, 53, 55, 56, 59, 61, 62, 63, 65, 67, 68, 69	70
36		12	72		24

Artinova domněnka o primitivních kořenech uvádí, že dané celé číslo $A$ to není ani a perfektní čtverec nor -1 není primitivní root modulo nekonečně mnoho připraví.

Posloupnost nejmenších primitivních kořenů modulo $n$ (což není totéž jako posloupnost primitivních kořenů v Gaussově tabulce) jsou

0, 1, 2, 3, 2, 5, 3, 0, 2, 3, 2, 0, 2, 3, 0, 0, 3, 5, 2, 0, 0, 7, 5, 0, 2, 7, 2, 0, 2, 0, 3, 0, 0, 3, 0, 0, 2, 3, 0, 0, 6, 0, 3, 0, 0, 5, 5, 0, 3, 3, 0, 0, 2, 5, 0, 0, 0, 3, 2, 0, 2, 3, 0, 0, 0, 0, 2, 0, 0, 0, 7, 0, 5, 5, 0, ... (sekvence A046145 v OEIS )

Pro nejlepší $n$ , oni jsou

1, 2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 6, 3, 5, 2, 2, 2, 2, 7, 5, 3, 2, 3, 5, 2, 5, 2, 6, 3, 3, 2, 3, 2, 2, 6, 5, 2, 5, 2, 2, 2, 19, 5, 2, 3, 2, 3, 2, 6, 3, 7, 7, 6, 3, 5, 2, 6, 5, 3, 3, 2, 5, 17, 10, 2, 3, 10, 2, 2, 3, 7, 6, 2, 2, ... (sekvence A001918 v OEIS )

Největší primitivní kořeny modulo $n$ jsou

0, 1, 2, 3, 3, 5, 5, 0, 5, 7, 8, 0, 11, 5, 0, 0, 14, 11, 15, 0, 0, 19, 21, 0, 23, 19, 23, 0, 27, 0, 24, 0, 0, 31, 0, 0, 35, 33, 0, 0, 35, 0, 34, 0, 0, 43, 45, 0, 47, 47, 0, 0, 51, 47, 0, 0, 0, 55, 56, 0, 59, 55, 0, 0, 0, 0, 63, 0, 0, 0, 69, 0, 68, 69, 0, ... (sekvence A046146 v OEIS )

Pro nejlepší $n$ , oni jsou

1, 2, 3, 5, 8, 11, 14, 15, 21, 27, 24, 35, 35, 34, 45, 51, 56, 59, 63, 69, 68, 77, 80, 86, 92, 99, 101, 104, 103, 110, 118, 128, 134, 135, 147, 146, 152, 159, 165, 171, 176, 179, 189, 188, 195, 197, 207, 214, 224, 223, ... (sekvence A071894 v OEIS )

Počet primitivních kořenů modulo $n$ jsou

1, 1, 1, 1, 2, 1, 2, 0, 2, 2, 4, 0, 4, 2, 0, 0, 8, 2, 6, 0, 0, 4, 10, 0, 8, 4, 6, 0, 12, 0, 8, 0, 0, 8, 0, 0, 12, 6, 0, 0, 16, 0, 12, 0, 0, 10, 22, 0, 12, 8, 0, 0, 24, 6, 0, 0, 0, 12, 28, 0, 16, 8, 0, 0, 0, 0, 20, 0, 0, 0, 24, 0, 24, 12, 0, ... (sekvence A046144 v OEIS )

Pro nejlepší $n$ , oni jsou

1, 1, 2, 2, 4, 4, 8, 6, 10, 12, 8, 12, 16, 12, 22, 24, 28, 16, 20, 24, 24, 24, 40, 40, 32, 40, 32, 52, 36, 48, 36, 48, 64, 44, 72, 40, 48, 54, 82, 84, 88, 48, 72, 64, 84, 60, 48, 72, 112, 72, 112, 96, 64, 100, 128, 130, 132, 72, 88, 96, ... (sekvence A008330 v OEIS )

Nejmenší prime> $n$ s primitivním kořenem $n$ jsou

2, 3, 5, 0, 7, 11, 11, 11, 0, 17, 13, 17, 19, 17, 19, 0, 23, 29, 23, 23, 23, 31, 47, 31, 0, 29, 29, 41, 41, 41, 47, 37, 43, 41, 37, 0, 59, 47, 47, 47, 47, 59, 47, 47, 47, 67, 59, 53, 0, 53, ... (sekvence A023049 v OEIS )

Nejmenší prime (nutně nepřesahuje $n$ ) s primitivním kořenem $n$ jsou

2, 3, 2, 0, 2, 11, 2, 3, 2, 7, 2, 5, 2, 3, 2, 0, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 11, 2, 3, 2, 19, 2, 0, 2, 3, 2, 7, 2, 5, 2, 3, 2, 11, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 19, 2, 3, 2, 0, 2, 7, 2, 3, 2, 19, 2, 5, 2, 3, 2, ... (sekvence A056619 v OEIS )

Aritmetická fakta

Gauss dokázal^[6] že pro jakékoli prvočíslo $str$ (s jedinou výjimkou $str$ = 3 ), produkt jeho primitivních kořenů je shodný s 1 modulo $str$ .

Také dokázal^[7] že pro jakékoli prvočíslo $str$ , součet jeho primitivních kořenů je shodný s $μ$ ( $str$ - 1) modulo $str$ , kde $μ$ je Möbiova funkce.

Například,
$str$ = 3, $μ$ (2) = -1. Primitivní kořen je 2.
$str$ = 5, $μ$ (4) = 0. Primitivní kořeny jsou 2 a 3.
$str$ = 7, $μ$ (6) = 1. Primitivní kořeny jsou 3 a 5.
$str$ = 31, $μ$ (30) = -1. Primitivní kořeny jsou 3, 11, 12, 13, 17, 21, 22 a 24.
Jejich produkt 970377408 ≡ 1 (mod 31) a jejich součet 123 ≡ −1 (mod 31).
3 × 11 = 33 ≡ 2
12 × 13 = 156 ≡ 1
(−14) × (−10) = 140 ≡ 16
(−9) × (−7) = 63 ≡ 1 a 2 × 1 × 16 × 1 = 32 ≡ 1 (mod 31).

A co přidání prvků této multiplikativní skupiny? Jak se to stane, součty (nebo rozdíly) dvou primitivních kořenů sčítají všechny prvky podskupiny indexu 2 $ℤ$ / $n$ $ℤ$ dokonce $n$ a celé skupině $ℤ$ / $n$ $ℤ$ když $n$ je liché:

  $ℤ$ / $n$   $ℤ$ ^× +  $ℤ$ / $n$   $ℤ$ ^× =  $ℤ$ / $n$   $ℤ$  nebo 2 $ℤ$ / $n$   $ℤ$  .^[8]

Nalezení primitivních kořenů

Žádný jednoduchý obecný vzorec pro výpočet primitivních kořenů modulo $n$ je známo.^[A]^[b] Existují však metody k nalezení primitivního kořene, které jsou rychlejší než pouhé vyzkoušení všech kandidátů. Pokud multiplikativní pořadí čísla $m$ modulo $n$ je rovný ${ displaystyle varphi (n)}$ (pořadí $ℤ$ ^×
_$n$), pak je to primitivní kořen. Ve skutečnosti platí obráceně: Pokud $m$ je primitivní kořenový modul $n$ , pak multiplikativní pořadí $m$ je ${ displaystyle varphi (n)}$ . Můžeme to použít k testování kandidáta $m$ zjistit, zda je to primitivní.

Nejprve spočítejte ${ displaystyle varphi (n)}$ . Pak určete různé hlavní faktory z ${ displaystyle varphi (n)}$ , řekněme $str$ ₁, ..., $str k$ . Nakonec spočítejte

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

pomocí rychlého algoritmu pro modulární umocňování jako umocňování druhou mocninou. Číslo $m$ pro které jsou tyto $k$ výsledky se liší od 1 je primitivní kořen.

Počet primitivních kořenů modulo $n$ , pokud existují, je rovno^[9]

{ Displaystyle varphi left ( varphi (n) right)}

protože, obecně, cyklická skupina s $r$ prvků má ${ displaystyle varphi (r)}$ generátory. Pro nejlepší $n$ , to se rovná ${ displaystyle varphi (n-1)}$ , a od té doby ${ displaystyle n / varphi (n-1) v O ( log log n)}$ generátory jsou velmi běžné mezi {2, ..., $n$ −1} a je tedy relativně snadné ho najít.^[10]

Li $G$ je primitivní kořenový modul $str$ , pak $G$ je také primitivní root modulo všech sil $str k$ ledaže $G$ ^{$str$ −1} ≡ 1 (mod $str$ ²); v tom případě, $G$ + $str$ je.^[11]

Li $G$ je primitivní kořenový modul $str k$ , pak buď $G$ nebo $G$ + $str k$ (kterýkoli z nich je lichý) je primitivní kořenový modul 2 $str k$ .^[11]

Nalezení primitivních kořenů modulo $str$ je také ekvivalentní hledání kořenů ( $str$ - 1) sv cyklotomický polynom modulo $str$ .

Řád primitivních kořenů

Nejméně primitivní kořen $G str$ modulo $str$ (v rozsahu 1, 2, ..., $str$ − 1 ) je obecně malý.

Horní hranice

Burgess (1962) dokázal^[12] to pro každého ε > 0 existuje $C$ takhle ${ displaystyle g_ {p} leq C , p ^ {{ frac {1} {4}} + epsilon} ~.}$

Grosswald (1981)^[12] to když ${ displaystyle p> e ^ {e ^ {24}}}$ , pak ${ displaystyle g_ {p}$

Carella (2015) prokázána^[13] že existuje ${ displaystyle C> 0}$ takhle ${ displaystyle g_ {p} leq C , p ^ {5 / log log p}}$ pro všechna dostatečně velká prvočísla ${ displaystyle p> 2 ~.}$

Shoup (1990, 1992) prokázal,^[14] za předpokladu, že zobecněná Riemannova hypotéza, že $G str$ = O (log⁶ $str$ ).

Dolní hranice

Dokázali to Fridlander (1949) a Salié (1950)^[12] že existuje pozitivní konstanta $C$ tak, že na nekonečně mnoho prvočísel $G str$ > $C$ log $str$ .

To se dá dokázat^[12] elementárním způsobem, že pro jakékoli kladné celé číslo $M$ existuje nekonečně mnoho prvočísel $M$ < $G str$ < $str$ − $M$ .

Aplikace

Primitivní kořenový modul $n$ se často používá v kryptografie, včetně Výměna klíčů Diffie – Hellman systém. Zvukové difuzory byly založeny na teoreticko-teoretických koncepcích, jako jsou primitivní kořeny a kvadratické zbytky.^[15]^[16]

Viz také

Poznámky pod čarou

^ „Jedním z nejdůležitějších nevyřešených problémů v teorii konečných polí je návrh rychlého algoritmu pro konstrukci primitivních kořenů. von zur Gathen a Shparlinski 1998, s. 15–24
^ "Neexistuje žádný vhodný vzorec pro výpočet [nejméně primitivní kořen]." Robbins 2006, str. 159

Reference

^ Stromquist, Walter. „Co jsou to primitivní kořeny?“. Matematika. Bryn Mawr College. Archivovány od originál dne 3. 7. 2017. Citováno 2017-07-03.
^ Weisstein, Eric W. "Modulo Multiplication Group". MathWorld.
^ Primitivní kořen, Encyclopedia of Mathematics.
^ Vinogradov 2003, s. 105–121, § VI Primitivní kořeny a indexy.
^ Vinogradov 2003, str. 106.
^ Gauss & Clarke 1986 umění. 80.
^ Gauss & Clarke 1986, umění 81.
^ Amiot, Emmanuel (2016). Hudba v prostoru Fourier. Řada CMS. Curych, CH: Springer. str. 38. ISBN 978-3-319-45581-5.
^ (sekvence A010554 v OEIS )
^ Knuth, Donald E. (1998). Seminumerické algoritmy. Umění počítačového programování. 2 (3. vyd.). Addison – Wesley. oddíl 4.5.4, strana 391.
^ ^A ^b Cohen, Henri (1993). Kurz výpočetní algebraické teorie čísel. Berlín: Springer. str. 26. ISBN 978-3-540-55640-4.
^ ^A ^b ^C ^d Ribenboim, Paulo (1996). Nová kniha rekordů prvočísel. New York, NY: Springer. str. 24. ISBN 978-0-387-94457-9.
^ Carella, N.A. (2015). "Nejméně primitivní kořeny". International Journal of Mathematics and Computer Science. 10 (2): 185–194. arXiv:1709.01172.
^ Bach & Shallit 1996, str. 254.
^ Walker, R. (1990). Návrh a aplikace modulárních akustických rozptylujících prvků (PDF). Výzkumné oddělení BBC (zpráva). British Broadcasting Corporation. Citováno 25. března 2019.
^ Feldman, Eliot (červenec 1995). „Odrazová mřížka, která ruší zrcadlový odraz: kužel ticha“. J. Acoust. Soc. Dopoledne. 98 (1): 623–634. Bibcode:1995ASAJ ... 98..623F. doi:10.1121/1.413656.

Zdroje

Bach, Eric; Shallit, Jeffrey (1996). Efektivní algoritmy. Algoritmická teorie čísel. Já. Cambridge, MA: MIT Press. ISBN 978-0-262-02405-1.

Carella, N.A. (2015). "Nejméně primitivní kořeny". International Journal of Mathematics and Computer Science. 10 (2): 185–194. arXiv:1709.01172.

The Disquisitiones Arithmeticae byl přeložen z Gaussovy ciceronské latiny do angličtiny a němčiny. Německé vydání obsahuje všechny jeho práce o teorii čísel: všechny důkazy kvadratické reciprocity, stanovení znaménka Gaussovy sumy, vyšetřování biquadratické reciprocity a nepublikované poznámky.

Gauss, Carl Friedrich (1986) [1801]. Disquisitiones Arithmeticae. Přeložil Clarke, Arthur A. (2. opravené vydání). New York, NY: Springer. ISBN 978-0-387-96254-2.

Gauss, Carl Friedrich (1965) [1801]. Untersuchungen über höhere Arithmetik [Studie vyšší aritmetiky] (v němčině). Přeložil Maser, H. (2. vyd.). New York, NY: Chelsea. ISBN 978-0-8284-0191-3.

Robbins, Neville (2006). Počáteční teorie čísel. Jones & Bartlett Learning. ISBN 978-0-7637-3768-9.

Vinogradov, I.M. (2003). „§ VI Primitivní kořeny a indexy“. Prvky teorie čísel. Mineola, NY: Dover Publications. str. 105–121. ISBN 978-0-486-49530-9.

von zur Gathen, Joachim; Shparlinski, Igor (1998). "Řád Gaussových období v konečných polích". Použitelná algebra ve strojírenství, komunikaci a práci na počítači. 9 (1): 15–24. CiteSeerX 10.1.1.46.5504. doi:10,1007 / s002000050093. PAN 1624824. S2CID 19232025.

Další čtení

Ruda, Oystein (1988). Teorie čísel a její historie. Doveru. str.284–302. ISBN 978-0-486-65620-5..

externí odkazy

Weisstein, Eric W. „Primitivní kořen“. MathWorld.
Holt. „Kvadratické zbytky a primitivní kořeny“. Matematika. Michigan Tech.
"Primitivní kořenová kalkulačka". BlueTulip.

[9] „Jedním z nejdůležitějších nevyřešených problémů v teorii konečných polí je návrh rychlého algoritmu pro konstrukci primitivních kořenů. von zur Gathen a Shparlinski 1998, s. 15–24

[10] "Neexistuje žádný vhodný vzorec pro výpočet [nejméně primitivní kořen]." Robbins 2006, str. 159

[1] Stromquist, Walter. „Co jsou to primitivní kořeny?“. Matematika. Bryn Mawr College. Archivovány od originál dne 3. 7. 2017. Citováno 2017-07-03.

[2] Weisstein, Eric W. "Modulo Multiplication Group". MathWorld.

[3] Primitivní kořen, Encyclopedia of Mathematics.

[Vinogradov2003.pp=105–121-4] Vinogradov 2003, s. 105–121, § VI Primitivní kořeny a indexy.

[5] Vinogradov 2003, str. 106.

[6] Gauss & Clarke 1986 umění. 80.

[7] Gauss & Clarke 1986, umění 81.

[Amiot-2016-8] Amiot, Emmanuel (2016). Hudba v prostoru Fourier. Řada CMS. Curych, CH: Springer. str. 38. ISBN 978-3-319-45581-5.

[11] (sekvence A010554 v OEIS )

[Knuth-1998-12] Knuth, Donald E. (1998). Seminumerické algoritmy. Umění počítačového programování. 2 (3. vyd.). Addison – Wesley. oddíl 4.5.4, strana 391.

[Cohen1993-13] A ^b Cohen, Henri (1993). Kurz výpočetní algebraické teorie čísel. Berlín: Springer. str. 26. ISBN 978-3-540-55640-4.

[Ribenboim,_p.24-14] A ^b ^C ^d Ribenboim, Paulo (1996). Nová kniha rekordů prvočísel. New York, NY: Springer. str. 24. ISBN 978-0-387-94457-9.

[Carella-2015-15] Carella, N.A. (2015). "Nejméně primitivní kořeny". International Journal of Mathematics and Computer Science. 10 (2): 185–194. arXiv:1709.01172.

[16] Bach & Shallit 1996, str. 254.

[Walker-1990-17] Walker, R. (1990). Návrh a aplikace modulárních akustických rozptylujících prvků (PDF). Výzkumné oddělení BBC (zpráva). British Broadcasting Corporation. Citováno 25. března 2019.

[Feldman-18] Feldman, Eliot (červenec 1995). „Odrazová mřížka, která ruší zrcadlový odraz: kužel ticha“. J. Acoust. Soc. Dopoledne. 98 (1): 623–634. Bibcode:1995ASAJ ... 98..623F. doi:10.1121/1.413656.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[A]

[b]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

Primitivní kořenový modul n - Primitive root modulo n - Wikipedia

Základní příklad

Definice

Příklady

Tabulka primitivních kořenů

Aritmetická fakta

Nalezení primitivních kořenů

Řád primitivních kořenů

Horní hranice

Dolní hranice

Aplikace

Viz také

Poznámky pod čarou

Reference

Zdroje

Další čtení

externí odkazy

Primitivní kořenový modul $n$ - Primitive root modulo n - Wikipedia