Примітивний елемент
Zn* має генератор тоді і тільки тоді, коли n = 2, 4, pk, 2 * pk, де p — непарне просте число та k xF0B3 1. Зокрема, якщо p просте, то Zp* має генератор. Розклад на множники порядка групи Zp* (|Zp*| = xF06A (p) = p — 1). Елемент g буде примітивним елементом групи Zp* тоді і тільки тоді, коли. Означення. Нехай x xF0CE Zn*. Порядком числа x називається таке найменше додатне ціле число k, що xk xF0BA… Читати ще >
Примітивний елемент (реферат, курсова, диплом, контрольна)
Реферат на тему:
Примітивний елемент.
Означення. Нехай x xF0CE Zn*. Порядком числа x називається таке найменше додатне ціле число k, що xk xF0BA 1 (mod n) та позначається ord (x).
Твердження. Якщо ord (x) = k, xt xF0BA 1 (mod n), то t ділиться на k. Зокрема, k ділить xF06A (n).
Приклад. Нехай n = 21. Z21* = {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}. xF06A (21) = xF06A (3) * xF06A (7) = 2 * 6 = 12. Порядок елементів множини Z21* наведено у таблиці.
x xF0CE 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 xF0CE Zn*. Якщо порядок g дорівнює порядку групи Zn* (ord (g) = |Zn*| = xF06A (n)), то число g називається генератором або примітивним елементом Zn*. Якщо Zn* має генератор, то множина Zn* називається циклічною.
Властивості генераторів.
1. Zn* має генератор тоді і тільки тоді, коли n = 2, 4, pk, 2 * pk, де p — непарне просте число та k xF0B3 1. Зокрема, якщо p просте, то Zp* має генератор.
2. Якщо g — генератор Zn*, то Zn* = {gi mod n | 0xF020xF0A3 ixF020xF0A3 xF06A (n) — 1}.
3. Нехай g — генератор Zn*. Тоді b = gi mod n є також генератором Zn* тоді і тільки тоді, коли НСД (i, xF06A (n)) = 1. Якщо множина Zn* є циклічною, то її кількість генераторів дорівнює xF06A (xF06A (n)).
xF0B9 1 (mod n) для кожного простого дільника p числа xF06A (n).
Приклад. Множина Z21* не є циклічною, тому що вона не містить елементу, порядок якого дорівнює xF06A (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* xF0AE Zp-1.
Приклад. Розглянемо групу Z13*, генератором якої є g = 2. Тоді з рівності.
217 = 22 * 23 (mod 13).
випливає рівність.
17 = 2 + 3 (mod 12).
— розклад на множники порядка групи Zp* (|Zp*| = xF06A (p) = p — 1). Елемент g буде примітивним елементом групи Zp* тоді і тільки тоді, коли.
xF0B9xF0201 (mod p), 1 xF0A3 i xF0A3xF020k.
Доведення. Елемент g буде примітивним елементом тоді і тільки тоді, коли його порядок дорівнює порядку групи: ord (g) = |Zp*| = p — 1. Якщо для деякого i, 1 xF0A3 i xF0A3xF020k, має місце рівність.
= 1(mod p),.
< p — 1, тобто порядок g не дорівнює порядку Zp* і в такому разі не може бути примітивним елементом.
Твердження. Zp* має точно xF06A (p — 1) примітивних елементів.
1 mod p. Тоді g буде примітивним елементом тоді і тільки тоді, коли.
xF0B9 1 (mod p).
.
" .
b.
t.
x.
|.
x20AC.
".
x02C6.
x017D.
".
x0161.
.
b.
d.
f.
h.
j.
l.
p.
r.
x00B2.
6x0161.
¦
x00B2.
x00B4.
E.
I.
x00D0.
O.
O.
Ue.
a.
ae.
e.
i.
x00F0.
o.
o.
u.
ue.
x00B8.
x00BA.
e.
x00B2.
x00B4.
Ae.
AE.
o.
u.
ue.
F.
H.
J.
L.
‚.
".
†.
x02C6.
c.
x00B4.
x00BA.
e.
7e.
x00F0.
o.
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 xF0B9xF0201 (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 xF0ACxF0201 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.
76 138 1.
70 138 42 63.