Примітивний елемент, Детальна інформація
Примітивний елемент
Тип документу: Реферат
Сторінок: 6
Предмет: Математика
Автор: Олексій
Розмір: 18.9
Скачувань: 1212
Реферат на тему:
Примітивний елемент
Означення. Нехай x \xF0CE Zn*. Порядком числа x називається таке найменше додатне ціле число k, що xk \xF0BA 1 (mod n) та позначається ord(x).
Твердження. Якщо ord(x) = k, xt \xF0BA 1 (mod n), то t ділиться на k. Зокрема, k ділить \xF06A(n).
Приклад. Нехай n = 21. Z21* = {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}. \xF06A(21) = \xF06A(3) * \xF06A(7) = 2 * 6 = 12. Порядок елементів множини Z21* наведено у таблиці.
x \xF0CE 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 \xF0CE Zn*. Якщо порядок g дорівнює порядку групи Zn* ( ord(g) = |Zn*| = \xF06A(n)), то число g називається генератором або примітивним елементом Zn*. Якщо Zn* має генератор, то множина Zn* називається циклічною.
Властивості генераторів
1. Zn* має генератор тоді і тільки тоді, коли n = 2, 4, pk, 2 * pk, де p – непарне просте число та k \xF0B3 1. Зокрема, якщо p просте, то Zp* має генератор.
2. Якщо g – генератор Zn*, то Zn* = {gi mod n | 0\xF020\xF0A3 i\xF020\xF0A3 \xF06A(n) - 1}.
3. Нехай g – генератор Zn*. Тоді b = gi mod n є також генератором Zn* тоді і тільки тоді, коли НСД(i, \xF06A(n)) = 1. Якщо множина Zn* є циклічною, то її кількість генераторів дорівнює \xF06A(\xF06A(n)).
\xF0B9 1 (mod n) для кожного простого дільника p числа \xF06A(n).
Приклад. Множина Z21* не є циклічною, тому що вона не містить елементу, порядок якого дорівнює \xF06A(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)
має місце тоді і тільки тоді, коли
Примітивний елемент
Означення. Нехай x \xF0CE Zn*. Порядком числа x називається таке найменше додатне ціле число k, що xk \xF0BA 1 (mod n) та позначається ord(x).
Твердження. Якщо ord(x) = k, xt \xF0BA 1 (mod n), то t ділиться на k. Зокрема, k ділить \xF06A(n).
Приклад. Нехай n = 21. Z21* = {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}. \xF06A(21) = \xF06A(3) * \xF06A(7) = 2 * 6 = 12. Порядок елементів множини Z21* наведено у таблиці.
x \xF0CE 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 \xF0CE Zn*. Якщо порядок g дорівнює порядку групи Zn* ( ord(g) = |Zn*| = \xF06A(n)), то число g називається генератором або примітивним елементом Zn*. Якщо Zn* має генератор, то множина Zn* називається циклічною.
Властивості генераторів
1. Zn* має генератор тоді і тільки тоді, коли n = 2, 4, pk, 2 * pk, де p – непарне просте число та k \xF0B3 1. Зокрема, якщо p просте, то Zp* має генератор.
2. Якщо g – генератор Zn*, то Zn* = {gi mod n | 0\xF020\xF0A3 i\xF020\xF0A3 \xF06A(n) - 1}.
3. Нехай g – генератор Zn*. Тоді b = gi mod n є також генератором Zn* тоді і тільки тоді, коли НСД(i, \xF06A(n)) = 1. Якщо множина Zn* є циклічною, то її кількість генераторів дорівнює \xF06A(\xF06A(n)).
\xF0B9 1 (mod n) для кожного простого дільника p числа \xF06A(n).
Приклад. Множина Z21* не є циклічною, тому що вона не містить елементу, порядок якого дорівнює \xF06A(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)
має місце тоді і тільки тоді, коли