71. Проблема дискретного логарифмирования

Проблема дискретного логарифмирования (упрощенная версия)

Дано: Числа a, b и p.

p – большое простое число.

a и b– натуральные числа меньшие (p-1), связанные соотношением

b ≡ a x (mod p);

Найти: x– натуральное число меньшее (p-1)

Любое целое X , удовлетворяющее уравнению b = a^x , называется дискретным

логарифмом элемента b по основанию a . Таким образом, требуется найти дискретный

логарифм b по основанию a (правда, взятый по модулю p).

В настоящее время не известно алгоритмов дискретного логарифмирования

полиномиальной сложности.

72.Проблема факторизации.

Проблема факторизации

Стойкость наиболее распространенной системы открытого шифрования RSA и стойкость

схемы электронной подписи на основе RSA определяется сложностью задачи

факторизации больших целых чисел. Поэтому эта задача - одна из наиболее важных

математических задач современной криптографии. По популярности она даже

превосходит задачу дискретного логарифмирования.

Задача факторизации целых чисел - это задача нахождения по данному натуральному

Числу n различных простых чисел p₁,…,p_n

и натуральных чисел a₁,…,a_n ≥ 1 таких, что n = p₁^a1…p_n^an . Отметим, что если известен

некоторый

простой делитель p₁ числа n , то соответствующее αi может быть легко найдено (например,

перебором) за полиномиальное от время. Поэтому основная трудность задачи

факторизации заключается в нахождении простых делителей n .