Реферат на тему:

Примітивний елемент

Означення. Нехай 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),

< p – 1, тобто порядок g не дорівнює порядку Zp* і в такому разі не може бути примітивним елементом. Твердження. Zp* має точно ?(p - 1) примітивних елементів. 1 mod p. Тоді g буде примітивним елементом тоді і тільки тоді, коли ? 1 (mod p) . 1 mod p. Якщо g не примітивний елемент, то елемент (-g) буде примітивним. (mod p) ? -1 (mod p), тобто (-g) є примітивним елементом. є простими. Для знаходження генератора групи достатньо обрати довільний елемент g ? Zp* та перевірити, чи є він генератором. Якщо ні – то генератором буде елемент (-g) ? p - g. Приклад. Знайти примітивні елементи в групі Z11*. 1 mod 11, генераторами не будуть (таких значення два: g = 1, g = 10). Кількість генераторів групи Z11* дорівнює ?(10) = (2 – 1) * (5 – 1) = 4. (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}. не дорівнювало 1 (pi – дільники порядка групи G). Оскільки циклічна група G порядку n має ?(n) генераторів, то ймовірність того що перше навмвння обране число g ? G буде примітивним елементом, дорівнює ?(n)/n. Алгоритм . Вихід: генератор g групи G. 1. Обрати довільний елемент g із G; 2. for i ??1 to s do ; 2.2. if (b = 1) then goto 1; 3. return(g); Приклад. Знайти генератор групи Z139. Обчислимо порядок групи Z139: |Z139| = ?(139) = 138. Розкладемо число 138 на прості множники: 138 = 2 * 3 * 23. Кількість генераторів Z139 дорівнює ?(138) = ?(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

Похожие записи