Реферат на тему:
Примітивний елемент
Означення. Нехай x ? Zn*. Порядком числа x називається таке найменше
додатне ціле число k, що xk ? 1 (mod n) та позначається ord(x).
Твердження. Якщо ord(x) = k, xt ? 1 (mod n), то t ділиться на k.
Зокрема, k ділить ?(n).
Приклад. Нехай n = 21. Z21* = {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19,
20}. ?(21) = ?(3) * ?(7) = 2 * 6 = 12. Порядок елементів множини Z21*
наведено у таблиці.
x ? Z21* 1 2 4 5 8 10 11 13 16 17 19 20
порядок x 1 6 3 6 2 6 6 2 3 6 6 2
Означення. Нехай g ? Zn*. Якщо порядок g дорівнює порядку групи Zn* (
ord(g) = |Zn*| = ?(n)), то число g називається генератором або
примітивним елементом Zn*. Якщо Zn* має генератор, то множина Zn*
називається циклічною.
Властивості генераторів
1. Zn* має генератор тоді і тільки тоді, коли n = 2, 4, pk, 2 * pk, де p
– непарне просте число та k ? 1. Зокрема, якщо p просте, то Zp* має
генератор.
2. Якщо g – генератор Zn*, то Zn* = {gi mod n | 0?? i?? ?(n) – 1}.
3. Нехай g – генератор Zn*. Тоді b = gi mod n є також генератором Zn*
тоді і тільки тоді, коли НСД(i, ?(n)) = 1. Якщо множина Zn* є циклічною,
то її кількість генераторів дорівнює ?(?(n)).
? 1 (mod n) для кожного простого дільника p числа ?(n).
Приклад. Множина Z21* не є циклічною, тому що вона не містить елементу,
порядок якого дорівнює ?(21) = 12. Число 21 не задовольняє властивості 1
генераторів. Множина Z25* є циклічною, її генератором є 2.
Приклад. Множина Z13* має генератор g = 2.
n 1 2 3 4 5 6
2n (mod 13) 2 4 8 3 6 12
n 7 8 9 10 11 12
2n (mod 13) 11 9 5 10 7 1
g = 4 не є генератором множини Z13*, але є генератором її підмножини.
n 1 2 3 4 5 6
4n (mod 13) 4 3 12 9 10 1
Якщо група має генератор, то на поточний час не існує поліноміального
алгоритму, який буде знаходити всі генератори групи.
Твердження. Нехай p – просте, g – генератор Zp*. Тоді рівність
ga = gb * gc (mod p)
має місце тоді і тільки тоді, коли
a = b + c (mod p – 1)
Звідси випливає існування гомоморфізму f: Zp* ? Zp-1.
Приклад. Розглянемо групу Z13*, генератором якої є g = 2. Тоді з
рівності
217 = 22 * 23 (mod 13)
випливає рівність
17 = 2 + 3 (mod 12)
– розклад на множники порядка групи Zp* ( |Zp*| = ?(p) = p – 1).
Елемент g буде примітивним елементом групи Zp* тоді і тільки тоді, коли
??1 (mod p), 1 ? i ??k
Доведення. Елемент g буде примітивним елементом тоді і тільки тоді, коли
його порядок дорівнює порядку групи: ord(g) = |Zp*| = p – 1. Якщо для
деякого i, 1 ? i ??k, має місце рівність
= 1(mod p),
Нашли опечатку? Выделите и нажмите CTRL+Enter
