.

Примітивний елемент (реферат)

Язык: украинский
Формат: реферат
Тип документа: Word Doc
0 1206
Скачать документ

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

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

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

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Оставить комментарий

avatar
  Подписаться  
Уведомление о
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2020