Теоретико-числовые методы в криптографии. Сборник заданий

31 Решение варианта 40 работы №3 1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют. а) m=219; б) m=149; в) m=134; г) m=59; д) m=26. Решение: а) 219=3·73 – составное, не 2, 4, pα, 2 pα . Ответ: Порождающих нет. б) 149 – простое число. Количество порождающих составляет φ(φ(149))=φ(148)=φ(22·37)=1·2·36=72 элемента. Найдем какой-нибудь порождающий для Z*149. φ(149)=148=22·37. 2: 24 mod 149=16 mod 149=16≠1; 274 mod 149=148≠1. Ответ: 2 – порождающий элемент Z*149, количество порождающих – 72. в) 134=2·67. Количество порождающих есть φ(φ(134))=φ(66)=φ(2·3·11)= =1·2·10=20 . Найдем какой-нибудь порождающий для Z*134. φ(134)=66=2·3·11. 3: 36 mod 134=723 mod 149=53≠1; 322 mod 134=1. 3 – не порождающий элемент Z*134. 5: 56 mod 134=81≠1; 522 mod 134=1. 5 – не порождающий элемент Z*134. 7: 76 mod 134=131≠1; 722 mod 134=29≠1; 733 mod 134=133≠1; 7 – порождающий элемент Z*134 Ответ: 7 – порождающий элемент Z*134, количество порождающих – 20. г) 59 – простое число. Количество порождающих есть φ(φ(59))=φ(58)= =φ(2·29)=1·28=28. Найдем какой-нибудь порождающий для Z*59. φ(59)=58=2·29. 2: 22 mod 59=4≠1; 229 mod 59=58≠1; 2 – порождающий элемент Z*59. Ответ: 2 – порождающий элемент Z*59, количество порождающих – 28. д) 26=2·13. Количество порождающих есть φ(φ(26))=φ(12)=φ(22·3)= =1·2·2=4 . Найдем какой-нибудь порождающий для Z*26. φ(26)=12=22·3.