Введение

В теории чисел конгруэнтность квадратов — это конгруэнтность, часто используемая в алгоритмах факторизации целых чисел.

Использование коэффициентной базы

Метод, впервые примененный в методе факторизации Диксона и усовершенствованный методом непрерывных дробей, решетом квадратов и общим решетом числового поля, заключается в построении сравнения квадратов с использованием фактор-базы. Вместо поиска одной пары напрямую, мы находим множество "отношений", где значения y имеют только малые простые делители (являются гладкими числами), и перемножаем некоторые из них, чтобы получить квадрат в правой части. Множество малых простых чисел, на которые все y разлагаются, называется фактор-базой. Строим булеву матрицу, где каждая строка описывает одно значение y, каждый столбец соответствует одному простому числу в фактор-базе, а элемент матрицы представляет собой четность (четное или нечетное) количества раз, которое данный фактор встречается в y. Наша цель – выбрать строки для сложения, чтобы получить строку, состоящую из нулей. Это соответствует набору значений y, которые нужно перемножить, чтобы получить произведение, все факторы которого встречаются четное число раз, то есть квадрат числа. Перемножение соответствующих значений x даст сравнение квадратов. Это классическая задача системы линейных уравнений, которую можно эффективно решить с помощью метода Гаусса, как только число строк превысит число столбцов. Каждая дополнительная строка предоставляет дополнительное решение, в случае если первое решение приводит к тривиальному сравнению. Значительным преимуществом этой техники является то, что поиск отношений легко распараллеливается: большое количество компьютеров можно задействовать для поиска в различных диапазонах значений x и попыток разложения полученных y. Только найденные отношения необходимо сообщать центральному компьютеру, и делать это не нужно срочно. Компьютерам, выполняющим поиск, даже не обязательно доверять: достоверность сообщенного отношения можно проверить с минимальными усилиями. Существует множество усовершенствований этой техники. Например, помимо отношений, где y полностью разлагается на факторы в фактор-базе, вариант с "большим простым числом" также собирает "частичные отношения", где y разлагается полностью, за исключением одного большего множителя. Второе частичное отношение с тем же большим множителем можно перемножить с первым, чтобы получить "полное отношение".