Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Примітивний елемент
Означення. Нехай x Î Zn*. Порядком числа x називається таке найменше додатне ціле число k, що xk º 1 (mod n) та позначається ord(x).
Твердження. Якщо ord(x) = k, xt º 1 (mod n), то t ділиться на k. Зокрема, k ділить j(n).
Приклад. Нехай n = 21. Z21* = {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}. j(21) = j(3) * j(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*| = j(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 £ j(n) - 1}.
3. Нехай g – генератор Zn*. Тоді b = gi mod n є також генератором Zn* тоді і тільки тоді, коли НСД(i, j(n)) = 1. Якщо множина Zn* є циклічною, то її кількість генераторів дорівнює j(j(n)).
4. Число g Î Zn* є генератором Zn* тоді і тільки тоді, коли ¹ 1 (mod n) для кожного простого дільника p числа j(n).
Приклад. Множина Z21* не є циклічною, тому що вона не містить елементу, порядок якого дорівнює j(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)
Теорема 1. Нехай p – просте число, p – 1 = – розклад на множники порядка групи Zp* ( |Zp*| = j(p) = p - 1). Елемент g буде примітивним елементом групи Zp* тоді і тільки тоді, коли
¹ 1 (mod p), 1 £ i £ k
Доведення. Елемент g буде примітивним елементом тоді і тільки тоді, коли його порядок дорівнює порядку групи: ord(g) = |Zp*| = p – 1. Якщо для деякого i, 1 £ i £ k, має місце рівність
= 1(mod p),
то ord(g) £ < p – 1, тобто порядок g не дорівнює порядку Zp* і в такому разі не може бути примітивним елементом.
Твердження. Zp* має точно j(p - 1) примітивних елементів.
Теорема 2. Нехай p та p1 – прості числа, при чому p = 2p1 + 1, g Î Zp*, g ¹ 1 mod p. Тоді g буде примітивним елементом тоді і тільки тоді, коли
¹ 1 (mod p)
Доведення. º g2 º 1 тоді і тільки тоді, коли g = 1 mod p. А дільниками порядка групи Zp* як раз і є значення 2 та p1 = .
Теорема 3. Нехай p та p1 – прості числа, при чому p = 2p1 + 1, g Î Zp*, g ¹ 1 mod p. Якщо g не примітивний елемент, то елемент (-g) буде примітивним.
Наслідок. Існує поліноміальний алгоритм обчислення примітивного елемента для Zp*, якщо p та є простими.
Для знаходження генератора групи достатньо обрати довільний елемент g Î Zp* та перевірити, чи є він генератором. Якщо ні – то генератором буде елемент (-g) º p - g.
Приклад. Знайти примітивні елементи в групі Z11*.
В даному випадку p = 11 та (p – 1) / 2 = 5 – прості. Значення g, для яких g = 1 mod 11, генераторами не будуть (таких значення два: g = 1, g = 10). Кількість генераторів групи Z11* дорівнює j(10) = (2 – 1) * (5 – 1) = 4.
Достатньо перевірити, чи є примітивними елементами g = 2, 3, 4, 5. Якщо це так, то елемент 11 – g примітивним не буде. І навпаки, якщо g не є примітивним елементом, то таким буде 11 – g. Складемо таблицю (mod p) = g5 (mod 11):
|
g |
2 |
3 |
4 |
5 |
|
g5 |
10 |
1 |
1 |
1 |
Елемент g = 2 буде примітивним оскільки 25 ¹ 1 (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}.
Наступний алгоритм знаходить примітивний елемент в циклічній групі G та базується на теоремі 1: для того щоб едемент g був генератором G, необхідно і достатньо щоб значення виразу не дорівнювало 1 (pi – дільники порядка групи G). Оскільки циклічна група G порядку n має j(n) генераторів, то ймовірність того що перше навмвння обране число g Î G буде примітивним елементом, дорівнює j(n)/n.
Алгоритм
Вхід: циклічна група G порядку n, n = .
Вихід: генератор g групи G.
1. Обрати довільний елемент g із G;
2. for i ¬ 1 to s do
2.1. Обчислити b ¬ ;
2.2. if (b = 1) then goto 1;
3. return(g);
Приклад. Знайти генератор групи Z139.
Обчислимо порядок групи Z139: |Z139| = j(139) = 138. Розкладемо число 138 на прості множники: 138 = 2 * 3 * 23. Кількість генераторів Z139 дорівнює j(138) = j(2) * (3) * (23) = 1 * 2 * 22 = 44. Ймовірність того що взяте довільним чином число із Z139 є генератором, дорівнює 44 / 138 » 0.31. Число 138 має три дільника. Тому для того, щоб превірити чи є генератором навмання обране g Î 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 |
||
|
76 |
138 |
1 |
|
|
70 |
138 |
42 |
63 |