Алгоритмические проблемы криптографии

 ВАРИАНТ 14.

1. Определить, является ли число квадратичным вычетом: 

 29 mod 89

 66 mod 97

 21 mod 71

 33 mod 77

 78 mod 221

 34 mod 323

2. Извлечь корень: 

 x^2 = 51 mod 59

 x^2 = 17 mod 53

ВАРИАНТ 14.

1. Определить, является ли число простым или составным, оценить вычислительную сложность и вероятность ошибки теста: 

1.1. При помощи метода пробных делений проверить на простоту число n = 23. 

1.2. При помощи теста Лукаса проверить на простоту число n = 37. 

1.3. При помощи теста Ферма проверить на простоту число n = 29. 

1.4. При помощи теста Соловея-Штрассена проверить на простоту число n = 21. 

1.5. При помощи теста Миллера-Рабина проверить на простоту число n = 31. 

1.6. При помощи теста Конягина-Померанса проверить на простоту число n = 33. 

 2. Разложить число на множители и оценить вычислительную сложность алгоритма: 

 2.1. При помощи метода Ферма факторизовать число n = 391. 

 2.2. При помощи (p-1)-метода Полларда факторизовать число n = 119. 

 2.3. При помощи Ро-метода Полларда факторизовать число n = 119. 

 2.4. При помощи метода Шермана-Лемана факторизовать число n = 437. 

 2.5. При помощи метода Полларда-Штрассена факторизовать число n = 247. 

ВАРИАНТ 14.

1. Извлечь корень: 

 x^2 = 8 mod 41

 x^2 = 3 mod 143

 x^2 = 3 mod 77

2. Вычислить дискретный логарифм двумя способами, сравнить сложности решений 

 11^x = 5 mod 13

 5^x = 12 mod 13

 30^x = 28 mod 41