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

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

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

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