| dbo:abstract
|
- 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 . (hu)
- 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 . (hu)
|
