Примітивний елемент, Детальна інформація
Примітивний елемент
Тип документу: Реферат
Сторінок: 3
Предмет: Математика
Автор: Олексій
Розмір: 18.3
Скачувань: 1171
a = b + c (mod p – 1)
Звідси випливає існування гомоморфізму f: Zp* \xF0AE Zp-1.
Приклад. Розглянемо групу Z13*, генератором якої є g = 2. Тоді з рівності
217 = 22 * 23 (mod 13)
випливає рівність
17 = 2 + 3 (mod 12)
– розклад на множники порядка групи Zp* ( |Zp*| = \xF06A(p) = p - 1). Елемент g буде примітивним елементом групи Zp* тоді і тільки тоді, коли
\xF0B9\xF0201 (mod p), 1 \xF0A3 i \xF0A3\xF020k
Доведення. Елемент g буде примітивним елементом тоді і тільки тоді, коли його порядок дорівнює порядку групи: ord(g) = |Zp*| = p – 1. Якщо для деякого i, 1 \xF0A3 i \xF0A3\xF020k, має місце рівність
= 1(mod p),
< p – 1, тобто порядок g не дорівнює порядку Zp* і в такому разі не може бути примітивним елементом.
Твердження. Zp* має точно \xF06A(p - 1) примітивних елементів.
1 mod p. Тоді g буде примітивним елементом тоді і тільки тоді, коли
\xF0B9 1 (mod p)
.
1 mod p. Якщо g не примітивний елемент, то елемент (-g) буде примітивним.
(mod p) \xF0BA -1 (mod p), тобто (-g) є примітивним елементом.
є простими.
Для знаходження генератора групи достатньо обрати довільний елемент g \xF0CE Zp* та перевірити, чи є він генератором. Якщо ні – то генератором буде елемент (-g) \xF0BA p - g.
Приклад. Знайти примітивні елементи в групі Z11*.
1 mod 11, генераторами не будуть (таких значення два: g = 1, g = 10). Кількість генераторів групи Z11* дорівнює \xF06A(10) = (2 – 1) * (5 – 1) = 4.
(mod p) = g5 (mod 11):
g 2 3 4 5
g5 10 1 1 1
Елемент g = 2 буде примітивним оскільки 25 \xF0B9\xF0201 (mod 11), а g = 3, 4, 5 – ні. Отже всією множиною примітивних елементів у Z11* будуть g = {2, 11 – 3, 11 – 4, 11 – 5} = {2, 8, 7, 6}.
Відповідь: примітивними елементами в Z11* будуть g = {2, 6, 7, 8}.
не дорівнювало 1 (pi – дільники порядка групи G). Оскільки циклічна група G порядку n має \xF06A(n) генераторів, то ймовірність того що перше навмвння обране число g \xF0CE G буде примітивним елементом, дорівнює \xF06A(n)/n.
Алгоритм
.
Звідси випливає існування гомоморфізму f: Zp* \xF0AE Zp-1.
Приклад. Розглянемо групу Z13*, генератором якої є g = 2. Тоді з рівності
217 = 22 * 23 (mod 13)
випливає рівність
17 = 2 + 3 (mod 12)
– розклад на множники порядка групи Zp* ( |Zp*| = \xF06A(p) = p - 1). Елемент g буде примітивним елементом групи Zp* тоді і тільки тоді, коли
\xF0B9\xF0201 (mod p), 1 \xF0A3 i \xF0A3\xF020k
Доведення. Елемент g буде примітивним елементом тоді і тільки тоді, коли його порядок дорівнює порядку групи: ord(g) = |Zp*| = p – 1. Якщо для деякого i, 1 \xF0A3 i \xF0A3\xF020k, має місце рівність
= 1(mod p),
< p – 1, тобто порядок g не дорівнює порядку Zp* і в такому разі не може бути примітивним елементом.
Твердження. Zp* має точно \xF06A(p - 1) примітивних елементів.
1 mod p. Тоді g буде примітивним елементом тоді і тільки тоді, коли
\xF0B9 1 (mod p)
.
1 mod p. Якщо g не примітивний елемент, то елемент (-g) буде примітивним.
(mod p) \xF0BA -1 (mod p), тобто (-g) є примітивним елементом.
є простими.
Для знаходження генератора групи достатньо обрати довільний елемент g \xF0CE Zp* та перевірити, чи є він генератором. Якщо ні – то генератором буде елемент (-g) \xF0BA p - g.
Приклад. Знайти примітивні елементи в групі Z11*.
1 mod 11, генераторами не будуть (таких значення два: g = 1, g = 10). Кількість генераторів групи Z11* дорівнює \xF06A(10) = (2 – 1) * (5 – 1) = 4.
(mod p) = g5 (mod 11):
g 2 3 4 5
g5 10 1 1 1
Елемент g = 2 буде примітивним оскільки 25 \xF0B9\xF0201 (mod 11), а g = 3, 4, 5 – ні. Отже всією множиною примітивних елементів у Z11* будуть g = {2, 11 – 3, 11 – 4, 11 – 5} = {2, 8, 7, 6}.
Відповідь: примітивними елементами в Z11* будуть g = {2, 6, 7, 8}.
не дорівнювало 1 (pi – дільники порядка групи G). Оскільки циклічна група G порядку n має \xF06A(n) генераторів, то ймовірність того що перше навмвння обране число g \xF0CE G буде примітивним елементом, дорівнює \xF06A(n)/n.
Алгоритм
.