В чем заключается метод квадратичного решета при факторизации чисел?

Метод квадратичного решета — метод факторизации больших чисел, разработанный Померанцем в 1981 году. 4 Это универсальный алгоритм, время выполнения которого зависит от размера факторизуемого числа, а не от его особой структуры и свойств. 14

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

Алгоритм работает в два этапа: 1

1. Сбор данных. 1 Собирается информация, которая может привести к равенству квадратов. 1
2. Обработка данных. 1 Собранные данные помещаются в матрицу и обрабатываются для получения равенства квадратов. 1

Метод квадратичного решета считается одним из самых быстрых для целых чисел до 100 десятичных цифр. 14