Примітивний елемент
Примітивний елемент
Тип документу: Реферат
Сторінок: 6
Предмет: Математика
Автор: Олексій
Розмір: 18.9
Скачувань: 1213
o
oe
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.
Алгоритм
.
Вихід: генератор g групи G.
1. Обрати довільний елемент g із G;
2. for i \xF0AC\xF0201 to s do
;
2.2. if (b = 1) then goto 1;
3. return(g);
Приклад. Знайти генератор групи Z139.
Обчислимо порядок групи Z139: |Z139| = \xF06A(139) = 138. Розкладемо число 138 на прості множники: 138 = 2 * 3 * 23. Кількість генераторів Z139 дорівнює \xF06A(138) = \xF06A(2) * (3) * (23) = 1 * 2 * 22 = 44. Ймовірність того що взяте довільним чином число із Z139 є генератором, дорівнює 44 / 138 \xF0BB 0.31. Число 138 має три дільника. Тому для того, щоб превірити чи є генератором навмання обране g \xF0CE Z139, достатньо обчислити значення g138 / 2 mod n, g138 / 3 mod n, g138 / 23 mod n та впевнитися що вони не дорівнюють 1.
g g69 mod n g46 mod n g6 mod n
64 1
8 138 1
99 1
oe
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.
Алгоритм
.
Вихід: генератор g групи G.
1. Обрати довільний елемент g із G;
2. for i \xF0AC\xF0201 to s do
;
2.2. if (b = 1) then goto 1;
3. return(g);
Приклад. Знайти генератор групи Z139.
Обчислимо порядок групи Z139: |Z139| = \xF06A(139) = 138. Розкладемо число 138 на прості множники: 138 = 2 * 3 * 23. Кількість генераторів Z139 дорівнює \xF06A(138) = \xF06A(2) * (3) * (23) = 1 * 2 * 22 = 44. Ймовірність того що взяте довільним чином число із Z139 є генератором, дорівнює 44 / 138 \xF0BB 0.31. Число 138 має три дільника. Тому для того, щоб превірити чи є генератором навмання обране g \xF0CE Z139, достатньо обчислити значення g138 / 2 mod n, g138 / 3 mod n, g138 / 23 mod n та впевнитися що вони не дорівнюють 1.
g g69 mod n g46 mod n g6 mod n
64 1
8 138 1
99 1