UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75843
останнє поновлення: 2016-12-04
за 7 днів додано 10

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваПримітивний елемент (реферат)
Авторdimich
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось1139
Скачало263
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

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

 

Означення. Нехай 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* та перевірити, чи є він генератором. Якщо ні – то генератором буде

-----> Page:

0 [1]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ