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

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

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

2. for i \xF0AC\xF0201 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