Primitív gyök

Ha n>1 természetes szám, akkor g primitív gyök modulo n, ha a g, g²,...,g^φ(n) hatványok különböző maradékot adnak n-nel osztva, azaz g rendje modulo n pontosan φ(n). Itt φ(n) az Euler-féle φ-függvény. Más szóval, g hatványai a redukált maradékrendszert adják modulo n. Ha például n=5, akkor g=2 megfelel: hatványai rendre 2,4,3,1 modulo 5. Ekkor, ha g^k ≡ a (mod n), akkor k-t g alapú indexnek vagy diszkrét logaritmusnak nevezik. Más szavakkal, g a modulo n maradékosztályok multiplikatív csoportjának generátora.

Primitív gyök pontosan az n=2, 4, p^k, 2p^k alakú számokra létezik, ahol p páratlan prímszám. Ha n=2^k, ahol k≥3, akkor nincs primitív gyök modulo n, de teljes redukált maradékrendszert adnak az 5,5²,...,5^t,-5,-5²,...,-5^t maradékosztályok, ahol t=2^k-2.

Primitív gyököket gyakran használnak a kriptográfiában, többek között a Diffie–Hellman-kulcscseréhez.

Története

Először Legendre bizonyította be 1798-ban kiadott Théorie des nombres című könyvében, hogy minden p prímszámra létezik primitív gyök modulo p. Gauss Disquisitiones Arithmeticae (1801) 57-es cikkében Eulernek tulajdonította a primitív gyök elnevezést. Az 56-os cikkben azt állítja, hogy Lambert és Euler is ismerte őket, de csak ő tudta belátni, hogy minden prímszámhoz van primitív gyök. Az 54-es cikkben csak a létezést bizonyítja, az 55-ösben pedig konstruálja is őket.

Definíció

Ha n pozitív egész, akkor a modulo n redukált maradékosztályok csoportot alkotnak a modulo n szorzásra. Ezt Z_n^× jelöli, és a modulo n egységek csoportjának is nevezik. Ez a csoport akkor és csak akkor ciklikus, ha n 2, 4, p^k, vagy 2p^k, ahol p^k egy páratlan prím hatványa.

A Z_n^× csoport rendjét a φ(n) (A000010 sorozat az OEIS-ben) Euler-függvény adja meg. Az Euler-tétel szerint a^φ(n) ≡ 1 (mod n) minden a-hoz, ami relatív prím n-hez. Az a elem rendjének nevezzük a legkisebb pozitív kitevőt, amire felemelve az a elemet 1-et kapunk. Ha a primitív gyök, akkor ez a φ(n).

Elemi példa

A 3 primitív gyök modulo 7, mivel:

${\begin{array}{rcrcrcrcrcr}3^{1}&=&3&=&3^{0}\times 3&\equiv &1\times 3&=&3&\equiv &3{\pmod {7}}\\3^{2}&=&9&=&3^{1}\times 3&\equiv &3\times 3&=&9&\equiv &2{\pmod {7}}\\3^{3}&=&27&=&3^{2}\times 3&\equiv &2\times 3&=&6&\equiv &6{\pmod {7}}\\3^{4}&=&81&=&3^{3}\times 3&\equiv &6\times 3&=&18&\equiv &4{\pmod {7}}\\3^{5}&=&243&=&3^{4}\times 3&\equiv &4\times 3&=&12&\equiv &5{\pmod {7}}\\3^{6}&=&729&=&3^{5}\times 3&\equiv &5\times 3&=&15&\equiv &1{\pmod {7}}\\\end{array}}$

Látható, hogy 3^k periódusa modulo 7 6. A periodikus 3, 2, 6, 4, 5, 1 maradékok a modulo 7 nem nulla maradékok permutációját adják, amiből látszik, hogy a 3 primitív gyök modulo 7. Az ekképpen előálló permutációk Costas-tömböt alkotnak.

További példák

Ha n = 14 = 2 × 7, akkor a redukált maradékosztályok {1, 3, 5, 9, 11, 13}; számuk φ(14) = 6. Hatványaik táblázata modulo 14:

 x     x, x2, x3, ... (mod 14) 
 1 :   1 
 3 :   3,  9, 13, 11,  5,  1  
 5 :   5, 11, 13,  9,  3,  1
 9 :   9, 11,  1
11 :  11,  9,  1
13 :  13,  1

Így 1 rendje 1, 3 és 5 rendje 6, 9 és 11 rendje 3, 13 rendje 2. Így 3 és 5 primitív gyökök modulo 14.

A következő példa az n = 15 = 3 × 5. A redukált maradékosztályok modulo 15 {1, 2, 4, 7, 8, 11, 13, 14}; számuk φ(15) = 8. A hatványok táblázata:

 x     x, x2, x3, ... (mod 15) 
 1 :   1 
 2 :   2,  4,  8, 1  
 4 :   4,  1
 7 :   7,  4, 13, 1
 8 :   8,  4,  2, 1
11 :  11,  1
13 :  13,  4,  7, 1
14 :  14,  1

Innen látszik, hogy egyik elem rendje sem 8, tehát nincs primitív gyök modulo 15.

A primitív gyökök táblázata

A következő számokhoz tartozik primitív gyök:

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, ... (A033948 sorozat az OEIS-ben)

Gauss megadott egy táblázatot is a primitív gyökökhöz a Disquisitionesban. A modern szerzőkkel szemben nem mindig a legkisebb primitív gyököt használta. Ehelyett, ha 10 primitív gyök, akkor azt adta meg; különben azt választotta, aminek a legkisebb indexe 10; ha ezekből több is volt, akkor a legkisebbet adta meg közülük.

A táblázat sorait a 100-nál kisebb prímhatványokkal címkézte, kivéve a 2, 4 és 8 számokat. A második oszlopban a primitív gyököt tüntette fel. Az oszlopokat a 100-nál kisebb prímekkel címkézte. A p sor q oszlopban szereplő elem q adott primitív gyökre vonatkozó indexe modulo p. Például a 11 sorában a primitív gyök 2, és az 5-höz tartozó elem 4. Ez azt jelenti, hogy 2⁴ = 16 ≡ 5 (mod 11). Az összetett számok indexe ennek alapján a logaritmushoz hasonlóan prímtényezős szorzattá bontással és a tényezők indexének összeadásával kapható. Például a 11 sorában a 6 indexe a 2 és a 3 indexének összege: 2^{1 + 8} = 512 ≡ 6 (mod 11). A 25 indexe az 5 indexének kétszerese: 2⁸ = 256 ≡ 25 (mod 11). Mivel 25 ≡ 3 (mod 11), azért 3 indexe 8.

A táblázat jól működik a páratlan prímek hatványaira, de modulo 16, 32 és 64 nincs primitív gyök. Az 5 hatványai a páratlan maradékosztályok egyik felét, a -5 a másik felét járja be. Az 5 hatványai modulo 8 1-gyel vagy 5-tel kongruensek. A 3-nál és 7-nél feltüntetett érték a -5 kitevője. Például modulo 32 a 7 indexe 2, és 5² = 25 ≡ −7 (mod 32); de a 17-hez 4 van megadva, és 5⁴ = 625 ≡ 17 (mod 32).

Primitív gyökök és indexek
(a többi oszlop az oszlop tetején levő számnak a megadott primitív gyökhöz tartozó indexeit tartalmazza)

n	gyök	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
n	gyök	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

A következő táblázat tartalmazza a primitív gyököket modulo n, ha n ≤ 72:

n	primitív gyökök modulo n	rend ((A000010 sorozat az OEIS-ben))	n	primitív gyökök modulo n	rend ((A000010 sorozat az OEIS-ben))
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

Sejtés, hogy a négyzetszámokat kivéve minden szám végtelen sokszor primitív gyök.

A legkisebb primitív gyökök sorozata, ha a 0 azt jelöli, hogy nincs primitív gyök:

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, ... (A046145 sorozat az OEIS-ben)

Prímszámokra

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, ... (A001918 sorozat az OEIS-ben)

A legnagyobb primitív gyökök sorozata, ha a 0 azt jelöli, hogy nincs primitív gyök

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, ... (A046146 sorozat az OEIS-ben)

Prímszámokra

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, ... (A071894 sorozat az OEIS-ben)

A primitív gyökök száma mod n

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, ... (A046144 sorozat az OEIS-ben)

Prímszámokra

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, ... (A008330 sorozat az OEIS-ben)

A legkisebb > n prím, aminek primitív gyöke n

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, ... (A023049 sorozat az OEIS-ben)

A legkisebb prím, aminek n primitív gyöke

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, ... (A056619 sorozat az OEIS-ben)

Tulajdonságok

Gauss belátta, hogy a hármat kivéve minden prímszámnál a primitív gyökök szorzata kongruens eggyel modulo a prím. Ha a prímet p jelöli, akkor a szorzat kongruens 1 modulo p. Továbbá a primitív gyökök összege kongruens μ(p − 1) modulo p, ahol μ a Möbius-függvény.

Például,

p = 3, μ(2) = −1. A primitív gyök 2.

p = 5, μ(4) = 0. A primitív gyökök 2 és 3.

p = 7, μ(6) = 1. A primitív gyökök 3 és 5.

p = 31, μ(30) = −1. A primitív gyökök 3, 11, 12, 13, 17 ≡ −14, 21 ≡ −10, 22 ≡ −9, és 24 ≡ −7.

Szorzatuk 970377408 ≡ 1 (mod 31) és összegük 123 ≡ −1 (mod 31).

3 × 11 = 33 ≡ 2

12 × 13 = 156 ≡ 1

(−14) × (−10) = 140 ≡ 16

(−9) × (−7) = 63 ≡ 1, and 2 × 1 × 16 × 1 = 32 ≡ 1 (mod 31).

Megtalálásuk

Nincs ismert képlet a primitív gyökök kiszámítására, azonban van jobb módszer az egyszerű találgatásnál. Ha m primitív gyök modulo n, akkor multiplikatív rendje $\varphi \left(n\right)$. Ez alapján tesztelhetők a jelöltek.

Először is kiszámítjuk $\varphi \left(n\right)$-t, majd meghatározzuk különböző prímtényezőit, legyenek ezek p₁, ..., p_k. Kiszámoljuk az m elemektre Z_n^*-ban as következőt:

$m^{\varphi (n)/p_{i}}\mod n\qquad {\mbox{ minden }}i=1,\ldots ,k\qquad {\mbox{ elemre }}$

a moduláris hatványozás és a sorozatos négyzetre emelések módszerével. Ha egy m elemre mind 1-től különböző értéket kapunk, akkor az primitív gyök.

Ha g primitív gyök modulo p, akkor g primitív gyök modulo minden p^k hatványra, kivéve a g ^{p – 1} ≡ 1 (mod p²) hatványokra; ekkor g + p lesz primitív gyök.

Ha g primitíve gyök modulo p^k, akkor g vagy g + p^k közül a páratlan primitív gyök modulo 2p^k.

Megtalálni a primitív gyököket modulo p ekvivalens megtalálni (p-1)^th a körosztási polinom gyökeinek megtalálásával modulo p.

Nevezetes problémák

Nevezetes probléma, hogy mekkora egy p prímszámra vonatkozó legkisebb primitív gyök. Erdős Pál például a ${\sqrt {p}}(\log p)^{17}$ becslést adta 1945-ben. A legjobb ismert becslés $O(p^{1/4+\varepsilon })$ (D. A. Burgess, 1962) míg a Riemann-sejtést feltéve 70 (log p)²-es felső korlát adódik (Victor Shoup (1990, 1992)).

Az alsó korlátra Fridlander (1949) és Salié (1950) eredménye, hogy végtelen sok prímre teljesül az alábbi g_p > C log p, ahol C konstans.

Elemi úton belátható, hogy minden pozitív M egészre végtelen sok prím van, hogy M < g_p < p − M.

Egy másik kérdés Artin sejtése: ha a egy −1-től különböző egész szám, ami nem négyzetszám, akkor végtelen sok prímszámra a primitív gyök. Ezzel kapcsolatban Gupta és Ram Murty eredményei után Heath-Brown bebizonyította, hogy legfeljebb két prímszámra és legfeljebb három pozitív négyzetmentes számra nem teljesülhet az állítás. Az érdekes az a dologban, hogy még mindig nem tudunk egyetlen prímet sem, amire igaz az állítás.

Erdős egy érdekes sejtése, hogy ha a p prím elég nagy, akkor van olyan q<p primitív gyöke, hogy q prím.

További információk

• Alice és Bob - 26. rész: Alice és Bob átlépi a célvonalat

Források

• Bach, Eric; Shallit, Jeffrey (1996). Algorithmic Number Theory (Vol I: Efficient Algorithms). Cambridge: The MIT Press. ISBN 0-262-02405-5..

• Cohen, Henri (1993), A Course in Computational Algebraic Number Theory, Berlin: Springer, ISBN 3-540-55640-0.

• Gauss, Carl Friedrich; Clarke, Arthur A. (translator) (1986), Disquisitiones Arithmeticae (2nd, corrected ed.), New York: Springer, ISBN 0-387-96254-9 {{citation}}: |first2= has generic name (súgó) [in English].

• Gauss, Carl Friedrich; Maser, H. (translator) (1965), Untersuchungen über höhere Arithmetik [Studies on higher arithmetic] (2nd ed.), New York: Chelsea, ISBN 0-8284-0191-8 {{citation}}: |first2= has generic name (súgó) [in German].

• Ribenboim, Paulo (1996). The New Book of Prime Number Records. New York: Springer. ISBN 0-387-94457-5..

• Robbins, Neville (2006), Beginning Number Theory, Jones & Bartlett Learning, ISBN 978-0-7637-3768-9.

• Vinogradov, I. M. (2003). "§ VI PRIMITIVE ROOTS AND INDICES". Elements of Number Theory. Mineola, NY: Dover Publications. 105–121. o. ISBN 978-0-486-49530-9..

• von zur Gathen, Joachim; Shparlinski, Igor (1998), "Orders of Gauss periods in finite fields", Applicable Algebra in Engineering, Communication and Computing, 9 (1), doi:10.1007/s002000050093, MR 1624824.

Fordítás

Ez a szócikk részben vagy egészben a Primitive root modulo n című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.