Primitív gyök

Ha n>1 természetes szám, akkor g primitív gyök modulo n, ha a 
g, g2,…,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 gk ≡ 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, pk, 2pk alakú számokra létezik, ahol p páratlan prímszám. 
Ha n=2k, ahol k≥3, akkor nincs primitív gyök modulo n, de teljes redukált maradékrendszert adnak az 5,52,…,5t,-5,-52,…,-5t maradékosztályok, ahol t=2k-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 Zn× jelöli,  és a modulo n egységek csoportjának is nevezik. Ez a csoport akkor és csak akkor ciklikus, ha n  2, 4, pk, vagy 2pk, ahol pk egy páratlan prím hatványa.

A Zn×  csoport rendjét a φ(n)   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:

Látható, hogy 3k 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 . 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, ... 

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 24 = 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: 21 + 8 = 512 ≡ 6 (mod 11).  A 25 indexe az 5 indexének kétszerese: 28 = 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 52 = 25 ≡ −7 (mod 32); de a 17-hez 4 van megadva, és 54 = 625 ≡ 17 (mod 32).

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

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, ... 

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, ... 

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, ... 

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, ... 

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, ... 

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, ... 

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, ... 

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, ...

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 . Ez alapján tesztelhetők a jelöltek.

Először is kiszámítjuk -t, majd meghatározzuk különböző prímtényezőit, legyenek ezek p1, ..., pk. Kiszámoljuk az m elemektre Zn*-ban as következőt:

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 pk hatványra,  kivéve a g p – 1 ≡ 1 (mod p2) hatványokra; ekkor g + p lesz primitív gyök.

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

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  becslést adta 1945-ben. A legjobb ismert becslés  (D. A. Burgess, 1962) míg a Riemann-sejtést feltéve 70 (log p)2-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 
gp > 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 < gp < p − M.

Egy másik kérdés Artin sejtése: ha a egy -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

Jegyzetek

Források
.

.

 [in English].

 [in German].

.

.

.

.

Fordítás

Számelmélet