Какие способы разложения чисел на простые множители применяются в криптографии?

В криптографии применяются следующие способы разложения чисел на простые множители:

• Квадратичное решето (quadratic sieve, QS). dha.spb.ru Относительно простой алгоритм факторизации, предложенный Carl Pomerance в 1981 году. dha.spb.ru Может разлагать на множители числа до 110 десятичных разрядов или около того. dha.spb.ru
• Метод решета числового поля (general number eld sieve, GNFS). dha.spb.ru Применяется для чисел ещё больших. dha.spb.ru
• Метод Ферма (факторизация, использующая разность квадратов). dha.spb.ru Поиск начинают с x = n + 1, наименьшего возможного числа, при котором разность x2 − n положительна. dha.spb.ru Увеличивают x на 1 и вычисляют x2 − n, пока x2 − n не окажется точным квадратом. dha.spb.ru Если это произошло, пытаются разложить n как x − x2 − n / x + x2 − n. dha.spb.ru Если это разложение тривиально, продолжают увеличивать x. dha.spb.ru

Сложность задачи факторизации используется в некоторых криптографических алгоритмах, например, в системе шифрования RSA. intuit.ru

Пользователь

Время добавления