Допомога у написанні освітніх робіт...
Допоможемо швидко та з гарантією якості!

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

РефератДопомога в написанніДізнатися вартістьмоєї роботи

Наступний алгоритм знаходить примітивний елемент в циклічній групі G та базується на теоремі 1: для того щоб едемент g був генератором G, необхідно і достатньо щоб значення виразу g — G — / p i не дорівнювало 1 (pi — дільники порядка групи G). Оскільки циклічна група G порядку n має генераторів, то ймовірність того що перше навмвння обране число g буде примітивним елементом, дорівнює /n… Читати ще >

Примітивний елемент (реферат) (реферат, курсова, диплом, контрольна)

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

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

Означення. Нехай x *. Порядком числа x називається таке найменше додатне ціле число k, що xk (mod n) та позначається ord (x).

Твердження. Якщо ord (x) = k, xt (mod n), то t ділиться на k. Зокрема, k ділить .

Приклад. Нехай n = 21. Z21* = {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}.) = * = 2 * 6 = 12. Порядок елементів множини Z21* наведено у таблиці.

x 1*.

порядок x.

Означення. Нехай g *. Якщо порядок g дорівнює порядку групи Zn* (ord (g) = |Zn*| =), то число g називається генератором або примітивним елементом Zn*. Якщо Zn* має генератор, то множина Zn* називається циклічною.

Властивості генераторів.

1. Zn* має генератор тоді і тільки тоді, коли n = 2, 4, pk, 2 * pk, де p — непарне просте число та k Зокрема, якщо p просте, то Zp* має генератор.

2. Якщо g — генератор Zn*, то Zn* = {gi mod n | 0 i — 1}.

3. Нехай g — генератор Zn*. Тоді b = gi mod n є також генератором Zn* тоді і тільки тоді, коли НСД (i,) = 1. Якщо множина Zn* є циклічною, то її кількість генераторів дорівнює).

4. Число g * є генератором Zn* тоді і тільки тоді, коли a ( n ) / p (mod n) для кожного простого дільника p числа .

Приклад. Множина Z21* не є циклічною, тому що вона не містить елементу, порядок якого дорівнює) = 12. Число 21 не задовольняє властивості 1 генераторів. Множина Z25* є циклічною, її генератором є 2.

Приклад. Множина Z13* має генератор g = 2.

n

2n (mod 13).

n

2n (mod 13).

g = 4 не є генератором множини Z13*, але є генератором її підмножини.

n

4n (mod 13).

Якщо група має генератор, то на поточний час не існує поліноміального алгоритму, який буде знаходити всі генератори групи.

Твердження. Нехай p — просте, g — генератор Zp*. Тоді рівність.

ga = gb * gc (mod p).

має місце тоді і тільки тоді, коли.

a = b + c (mod p — 1).

Звідси випливає існування гомоморфізму f: Zp* -1.

Приклад. Розглянемо групу Z13*, генератором якої є g = 2. Тоді з рівності.

217 = 22 * 23 (mod 13).

випливає рівність.

17 = 2 + 3 (mod 12).

Теорема 1. Нехай p — просте число, p — 1 = p 1 e 1 p 2 e 2 . . . p k e k  — розклад на множники порядка групи Zp* (|Zp*| = = p — 1). Елемент g буде примітивним елементом групи Zp* тоді і тільки тоді, коли.

g p - 1 p i 1 (mod p), 1 k.

Доведення. Елемент g буде примітивним елементом тоді і тільки тоді, коли його порядок дорівнює порядку групи: ord (g) = |Zp*| = p — 1. Якщо для деякого i, 1 k, має місце рівність.

g p - 1 p i = 1(mod p),.

то ord (g) math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >p-1pi < p — 1, тобто порядок g не дорівнює порядку Zp* і в такому разі не може бути примітивним елементом.

Твердження. Zp* має точно — 1) примітивних елементів.

Теорема 2. Нехай p та p1 — прості числа, при чому p = 2p1 + 1, g *, g math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >± 1 mod p. Тоді g буде примітивним елементом тоді і тільки тоді, коли.

g p - 1 2 (mod p).

Доведення. g p - 1 2 тоді і тільки тоді, коли g = ± 1 mod p. А дільниками порядка групи Zp* як раз і є значення 2 та p1 = p - 1 2 .

Теорема 3. Нехай p та p1 — прості числа, при чому p = 2p1 + 1, g *, g math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >± 1 mod p. Якщо g не примітивний елемент, то елемент (-g) буде примітивним.

Доведення. Якщо g math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >± 1 mod p, але g не примітивний елемент, то g p - 1 2 = 1 (mod p). Тоді ( - g ) p - 1 2 math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >(-1)p-12 * g p - 1 2 (mod p) math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >(-1)p-12 (mod p) (mod p), тобто (-g) є примітивним елементом.

Наслідок. Існує поліноміальний алгоритм обчислення примітивного елемента для Zp*, якщо p та p - 1 2 є простими.

Для знаходження генератора групи достатньо обрати довільний елемент g * та перевірити, чи є він генератором. Якщо ні - то генератором буде елемент (-g) — g.

Приклад. Знайти примітивні елементи в групі Z11*.

В даному випадку p = 11 та (p — 1) / 2 = 5 — прості. Значення g, для яких g = ± 1 mod 11, генераторами не будуть (таких значення два: g = 1, g = 10). Кількість генераторів групи Z11* дорівнює) = (2 — 1) * (5 — 1) = 4.

Достатньо перевірити, чи є примітивними елементами g = 2, 3, 4, 5. Якщо це так, то елемент 11 — g примітивним не буде. І навпаки, якщо g не є примітивним елементом, то таким буде 11 — g. Складемо таблицю g p - 1 2 (mod p) = g5 (mod 11):

g.

g5.

Елемент 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, необхідно і достатньо щоб значення виразу g | G | / p i не дорівнювало 1 (pi — дільники порядка групи G). Оскільки циклічна група G порядку n має генераторів, то ймовірність того що перше навмвння обране число g буде примітивним елементом, дорівнює /n.

Алгоритм.

Вхід: циклічна група G порядку n, n = p 1 k 1 p 2 k 2 . . . p s k s .

Вихід: генератор g групи G.

1. Обрати довільний елемент g із G;

2. for i 1 to s do.

2.1. Обчислити b g n / p i ;

2.2. if (b = 1) then goto 1;

3. return (g);

Приклад. Знайти генератор групи Z139.

Обчислимо порядок групи Z139: |Z139| = 9) = 138. Розкладемо число 138 на прості множники: 138 = 2 * 3 * 23. Кількість генераторів Z139 дорівнює 8) = * (3) * (23) = 1 * 2 * 22 = 44. Ймовірність того що взяте довільним чином число із Z139 є генератором, дорівнює 44 / 138 31. Число 138 має три дільника. Тому для того, щоб превірити чи є генератором навмання обране g 39, достатньо обчислити значення g138 / 2 mod n, g138 / 3 mod n, g138 / 23 mod n та впевнитися що вони не дорівнюють 1.

g.

g69 mod n.

g46 mod n.

g6 mod n.

Показати весь текст
Заповнити форму поточною роботою