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

В этой статье не процитировать какие - либо источники . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Ссылками материал может быть оспаривается и удалена . Найти источники:  «Конгруэнтность квадратов»  -  новости  · газеты  · книги  · ученый  · JSTOR ( декабрь 2009 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

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

Вывод [ править ]

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

${\ Displaystyle х ^ {2} -y ^ {2} = п \, \!}$

Затем мы можем множить n = x ² - y ² = ( x + y ) ( x - y ). Этот алгоритм на практике медленный, потому что нам нужно найти много таких чисел, и только некоторые из них удовлетворяют строгому уравнению. Тем не менее, n также можно факторизовать, если мы можем удовлетворить условие более слабого сравнения квадратов :

${\ Displaystyle х ^ {2} \ эквив у ^ {2} {\ pmod {п}}}$

${\ Displaystyle х \ не \ эквив \ пм у {\ pmod {п}}}$

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

${\ Displaystyle х ^ {2} -y ^ {2} \ Equiv 0 {\ pmod {п}}}$

${\ Displaystyle (х + у) (ху) \ эквив 0 {\ pmod {п}}}$

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

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

Дальнейшие обобщения [ править ]

Также можно использовать факторные базы, чтобы быстрее находить сравнения квадратов. Вместо того, чтобы искать с самого начала, мы находим многие, у которых у есть маленькие простые множители, и пытаемся умножить несколько из них вместе, чтобы получить квадрат в правой части.${\ Displaystyle \ TextStyle х ^ {2} \ экв у ^ {2} {\ pmod {п}}}$${\ Displaystyle \ TextStyle х ^ {2} \ экв у {\ pmod {п}}}$

Примеры [ править ]

Факторизовать 35 [ править ]

Возьмем n = 35 и находим, что

${\ Displaystyle \ textstyle 6 ^ {2} = 36 \ эквив 1 \ эквив 1 ^ {2} {\ pmod {35}}}$.

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

${\ Displaystyle \ НОД (6-1,35) \ CDOT \ НОД (6 + 1,35) = 5 \ CDOT 7 = 35}$

Факторизовать 1649 [ править ]

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

${\displaystyle 41^{2}\equiv 32{\pmod {1649}}}$

${\displaystyle 42^{2}\equiv 115{\pmod {1649}}}$

${\displaystyle 43^{2}\equiv 200{\pmod {1649}}}$

из них два имеют только маленькие простые числа в качестве факторов

${\displaystyle 32=2^{5}}$

${\displaystyle 200=2^{3}\cdot 5^{2}}$

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

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

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

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

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

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

См. Также [ править ]

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