Kongruencja kwadratów

W teorii liczb kongruencja kwadratów jest kongruencją powszechnie używaną w algorytmach faktoryzacji liczb całkowitych .

Pochodzenie

Mając dodatnią liczbę całkowitą n , metoda faktoryzacji Fermata polega na znalezieniu liczb x i y spełniających równość

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

Możemy wtedy rozłożyć n = x ² − y ² = ( x + y )( x − y ). Ten algorytm jest w praktyce powolny, ponieważ musimy przeszukać wiele takich liczb, a tylko kilka spełnia równanie. Jednak n można również rozłożyć na czynniki, jeśli możemy spełnić słabszy warunek zgodności kwadratów :

${\ Displaystyle x ^ {2} \ równoważnik y ^ {2} {\ pmod {n}}}$

${\ Displaystyle x \ nie \ równoważnik \ pm y\,{\pmod {n}}}$

Stąd łatwo wywnioskować

${\ Displaystyle x ^ {2} -y ^ {2} \ równoważnik 0 {\ pmod {n}}}$

${\ Displaystyle (x + y) (xy) \ równoważnik 0 {\ pmod {n}}}$

Oznacza to, że n dzieli iloczyn ( x + y )( x − y ). Zatem ( x + y ) i ( x − y ) każdy zawiera czynniki n , ale te czynniki mogą być trywialne. W tym przypadku musimy znaleźć inne x i y . Obliczenie największych wspólnych dzielników ( x + y , n ) i ( x − y , n ) da nam te czynniki; można to zrobić szybko za pomocą algorytmu Euklidesa .

Kongruencje kwadratów są niezwykle przydatne w algorytmach faktoryzacji liczb całkowitych i są szeroko stosowane, na przykład, w sicie kwadratowym , sicie ogólnego pola liczbowego , ciągłym ułamku faktoryzacji i faktoryzacji Dixona . I odwrotnie, ponieważ znalezienie pierwiastków kwadratowych modulo liczby złożonej okazuje się być probabilistycznym równoważnikiem czasu wielomianu z rozłożeniem tej liczby na czynniki, każdy algorytm faktoryzacji liczb całkowitych może być skutecznie użyty do zidentyfikowania kongruencji kwadratów.

Dalsze uogólnienia

Możliwe jest również użycie podstaw czynników, aby szybciej znaleźć kongruencje kwadratów. Zamiast szukać od początku, znajdujemy wiele ${\ Displaystyle \ textstyle x ^ {2} \ equiv y ^ {2} {\ pmod {n}}} wiele$${\ Displaystyle \ textstyle x ^ {2} \ equiv y {\ pmod {n}}}$ gdzie y mają małe czynniki pierwsze i spróbuj pomnożyć kilka z nich razem, aby uzyskać kwadrat po prawej stronie strona.

Przykłady

Rozłóż na czynniki 35

Bierzemy n = 35 i znajdujemy to

${\ Displaystyle \ textstyle 6 ^ {2} = 36 \ równoważnik 1 = 1 ^ {2} {\ pmod {35}}}$ .

W ten sposób uwzględniamy jako

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

Rozłóż na czynniki 1649

Wykorzystując n = 1649 jako przykład znajdowania kongruencji kwadratów zbudowanych z iloczynów niekwadratów (patrz metoda faktoryzacji Dixona ), najpierw otrzymujemy kilka kongruencji

${\ Displaystyle 41 ^ {2} \ równoważnik 32 {\ pmod {1649}}}$

${\ Displaystyle 42 ^ {2} \ równoważnik 115 {\ pmod { 1649}}}$

${\ Displaystyle 43 ^ {2} \ równoważnik 200 {\ pmod {1649}}}$

spośród nich dwa mają tylko małe liczby pierwsze jako czynniki

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

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

a ich kombinacja ma parzystą potęgę każdej małej liczby pierwszej, a zatem jest kwadratem

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

otrzymując kongruencję kwadratów

${\ Displaystyle 32 \ cdot 200 = 80 ^ {2} \ równoważnik 41 ^ {2} \ cdot 43 ^ {2} \ równoważnik 114 ^ {2}{\pmod {1649}}}$

Więc użycie wartości 80 i 114 jako naszych x i y daje współczynniki

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

Zobacz też

• Relacja kongruencji