Конгруэнтность квадратов

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

Вывод

Учитывая положительное целое число n , метод факторизации Ферма основан на поиске чисел x и y, удовлетворяющих равенству

$x^{2}-y^{2}=n$

Затем мы можем факторизовать n = x ² − и ² знак равно ( Икс + у )( Икс - у ). На практике этот алгоритм работает медленно, поскольку нам нужно искать много таких чисел, и лишь немногие из них удовлетворяют уравнению. Однако n также можно факторизовать, если мы можем удовлетворить более слабым условиям сравнения квадратов :

$x^{2}\equiv y^{2}{\pmod {n}}$

$x\not \equiv \pm y\,{\pmod {n}}$

Отсюда мы легко выводим

$x^{2}-y^{2}\equiv 0{\pmod {n}}$

$(x+y)(x-y)\equiv 0{\pmod {n}}$

Это означает, что n делит произведение ( x + y )( x − y ). Второе условие нетривиальности гарантирует, что n не делит ( x + y ) и ( x − y ) по отдельности. Таким образом, ( x + y ) и ( x − y ) содержат некоторые, но не все, множители n , а наибольшие общие делители ( x + y , n ) и ( x − y , n ) дадут нам эти факторы. Это можно сделать быстро, используя алгоритм Евклида .

Большинство алгоритмов поиска сравнений квадратов на самом деле не гарантируют нетривиальности; они только делают это вероятным. Есть вероятность, что найденное сравнение окажется тривиальным, и в этом случае нам нужно продолжить поиск других x и y .

Сравнения квадратов чрезвычайно полезны в алгоритмах факторизации целых чисел. И наоборот, поскольку поиск квадратных корней по модулю составного числа оказывается вероятностным полиномиальным эквивалентом разложения этого числа на множители, любой алгоритм целочисленной факторизации может эффективно использоваться для выявления сравнения квадратов.

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

Техника, впервые разработанная методом факторизации Диксона и улучшенная с помощью непрерывной факторизации дробей , квадратичного сита и сита общего числового поля , заключается в построении сравнения квадратов с использованием факторной базы .

Вместо того, чтобы искать одну пару $\textstyle x^{2}\equiv y^{2}{\pmod {n}}$ непосредственно мы находим множество «отношений» $\textstyle x^{2}\equiv y{\pmod {n}}$ где у имеют только небольшие простые делители (это гладкие числа ), и умножьте некоторые из них вместе, чтобы получить квадрат в правой части.

Набор маленьких простых чисел, в которые входят все y, называется факторной базой. Постройте логическую матрицу , где каждая строка описывает один y , каждый столбец соответствует одному простому числу в базе факторов, а запись представляет собой четность (четную или нечетную) количества раз, когда этот фактор встречается в y . Наша цель — выбрать подмножество строк, сумма которых равна нулевой строке. Это соответствует набору значений y , произведением которого является квадратное число, т. е. тому, факторизация которого имеет только четные показатели. Произведения значений x и y вместе образуют конгруэнтность квадратов.

Это классическая задача системы линейных уравнений , которую можно эффективно решить с помощью метода исключения Гаусса , как только количество строк превышает количество столбцов. Некоторые дополнительные строки часто включаются, чтобы гарантировать, что в пустом пространстве нашей матрицы существует несколько решений, в случае, если первое решение дает тривиальное сравнение.

Большим преимуществом этой техники является то, что поиск отношений является до неприличия параллельным ; можно настроить большое количество компьютеров на поиск различных диапазонов значений x и попытку факторизации результирующего y . Только о найденных связях нужно сообщить в центральный компьютер, причем особой спешки это делать не стоит. Поисковым компьютерам даже не нужно доверять; сообщаемая связь может быть проверена с минимальными усилиями.

Существует множество разработок этой техники. Например, в дополнение к отношениям, в которых y полностью входит в факторную базу, вариант «большого простого числа» также собирает «частичные отношения», в которых y полностью учитывается, за исключением одного более крупного фактора. Второе частичное отношение с тем же большим коэффициентом можно умножить на первое, чтобы получить «полное отношение».

Примеры

Факторизовать 35

Берем n = 35 и находим, что

$\textstyle 6^{2}=36\equiv 1=1^{2}{\pmod {35}}$.

Таким образом, мы учитываем

$\gcd(6-1,35)\cdot \gcd(6+1,35)=5\cdot 7=35$

Факторизовать 1649

Используя n = 1649, как пример нахождения сравнения квадратов, составленных из произведений неквадратов (см. метод факторизации Диксона ), сначала получаем несколько сравнений

$41^{2}\equiv 32=2^{5}{\pmod {1649}},$

$42^{2}\equiv 115=5\cdot 23{\pmod {1649}},$

$43^{2}\equiv 200=2^{3}\cdot 5^{2}{\pmod {1649}}.$

Из них первое и третье имеют в качестве факторов только маленькие простые числа, а их произведение имеет четную степень каждого маленького простого числа и, следовательно, представляет собой квадрат.

$32\cdot 200=2^{5+3}\cdot 5^{2}=2^{8}\cdot 5^{2}=(2^{4}\cdot 5)^{2}=80^{2}$

что дает равенство квадратов

$32\cdot 200=80^{2}\equiv 41^{2}\cdot 43^{2}\equiv 114^{2}{\pmod {1649}}.$

Таким образом, использование значений 80 и 114 в качестве наших x и y дает коэффициенты

$\gcd(114-80,1649)\cdot \gcd(114+80,1649)=17\cdot 97=1649.$

См. также

• Отношение конгруэнтности

Ссылки

• Брессуд, Дэвид М. (1989). «8. Квадратное решето». Факторизация и тестирование на простоту (PDF) . Тексты для бакалавриата по математике. Спрингер-Верлаг. ISBN  0-387-97040-1 .
• Райзель, Ганс (1994). Простые числа и компьютерные методы факторизации . Прогресс в математике. Том. 126 (2-е изд.). Биркхаузер. ISBN  0-8176-3743-5 .
• Вагстафф, Сэмюэл С. младший (2013). Радость факторинга . Студенческая математическая библиотека. Том. 68. Провиденс, Род-Айленд: Американское математическое общество . стр. 195–202. ISBN  1-4704-1048-6 .