Jak wyciągnąć $-- | 2$ modulo $n?$

Niech $|n$ będzie liczbą nieparzystą...

Pytamy, czy istnieje taka liczba całkowita $x,$ że

2 x ≡ 2 (mod n)?

(1)

Jeśli ta kongruencja ma rozwiązanie całkowite $x,$ to na pewno istnieje rozwiązanie $x ∈ {0,1,...,n − 1}. 1$ Wtedy liczba $x = n − x 2 1$ też jest rozwiązaniem. Jak jednak rozstrzygnąć, czy kongruencja (1) w ogóle ma rozwiązania?

W przypadku, gdy $n = p$ jest liczbą pierwszą, dysponujemy praktycznym algorytmem, który rozstrzyga, czy kongruencja (1) ma rozwiązanie - oparty jest on na tzw. kryterium Eulera. Jest ono ściśle związane z małym twierdzeniem Fermata. To słynne twierdzenie mówi, że jeśli $x$ nie dzieli się przez liczbę pierwszą $p,$ to wówczas

p−1 x ≡ 1 (mod p).

Jeśli kongruencja (1) ma rozwiązanie $x,$ to możemy napisać

p- 1 2 p- 1 p−1 2 2 ≡(x ) 2 ≡ x ≡ 1 (mod p),

a zatem ostatecznie

2 p2 1≡ 1 (mod p).

(2)

Kryterium Eulera stanowi, że powyższe rozumowanie można odwrócić: jeśli zachodzi kongruencja (2), to kongruencja (1) ma rozwiązanie. Warto w tym miejscu dodać, że potęgowanie $| k a$ modulo $| n$ łatwo wykonać efektywnie nawet wtedy, gdy liczby $n$ oraz $|k$ są ogromne! Oto zarys metody. Najpierw zapisujemy wykładnik $k$ w układzie dwójkowym:

m1 m2 ml k = 2 +2 + ...+2 , gdziem1 < m2 < ⋯ < ml = ⌊log2 k⌋.

Ponieważ

m m m ak = a21 ⋅a22 ⋅...⋅a2l ,

więc wystarczy wykonać $ml$ kolejnych podnoszeń do kwadratu, a na koniec $|l− 1$ mnożeń - wszystkie operacje wykonujemy modulo $n,$ a więc na liczbach mniejszych od $n.$

Załóżmy teraz, że liczba $2$ przeszła test Eulera. Nasuwa się teraz pytanie: jak znaleźć $x$ spełniające kongruencję (1)?

Jeśli $p ≡ 3 (mod 4),$ to wystarczy przyjąć

p 1 x≡ 2 4- (mod p).

Pokazuje to poniższy rachunek

p 1 p 1 x2 ≡ 2-2 ≡ 2-2 ⋅21≡ 2 (mod p)

(na mocy (2)).

Jeżeli natomiast $|p≡ 1 (mod 4),$ to nieco komplikując powyższą metodę (szczegóły pominiemy), można obliczyć $x$ spełniające (1), o ile mamy do dyspozycji taką liczbę $s,$ że kongruencja

x2 ≡ s (mod p)

(3)

nie ma rozwiązań. Taką liczbę $s$ nazywamy nieresztą kwadratową modulo $|p$ . Łatwo udowodnić, że w ciągu liczb $|1,2,...,p− 1$ jest dokładnie $|(p− 1)/2$ niereszt. Dla pozostałych liczb $s$ z powyższego ciągu kongruencja (3) ma rozwiązanie - nazywamy je resztami kwadratowymi modulo $p$ . I tak np. dla $|p = 7$ liczby $|1,2,4$ są resztami kwadratowymi, a liczby $|3,5,6$ nieresztami kwadratowymi. Natomiast dla $p = 11$ niereszty kwadratowe to $2,6,7,8,10,$ a reszty kwadratowe to $|1,3,4,5,9.$ Nieresztę kwadratową $|s,$ której używamy we wzmiankowanym powyżej algorytmie pierwiastkowania modulo $p,$ łatwo znaleźć praktycznie nawet dla bardzo dużych liczb pierwszych $p.$ Wystarczy mianowicie wylosować liczbę $s ∈{1,2,...,p− 1}$ i sprawdzić, czy jest nieresztą kwadratową, stosując, na przykład, kryterium Eulera. W przypadku niepowodzenia losujemy i testujemy inną liczbę $|s.$ Prawdopodobieństwo wylosowania niereszty w każdej próbie wynosi $1/2,$ a zatem przeciętnie bardzo szybko znajdziemy nieresztę. Jest to przykład algorytmu zrandomizowanego. Rzucając $|20$ razy symetryczną monetą, możemy, oczywiście, wyrzucić same reszty (niektórzy mówią reszki), ale prawdopodobieństwo tego jest małe.

A może lepiej testować po kolei liczby $s = 1,2,3...,$ aż do skutku, czyli do napotkania niereszty? Niech więc $|N(p)$ oznacza najmniejszą nieresztę kwadratową modulo $p.$ Najlepszy wynik bezwarunkowy pochodzi od D.A. Burgessa

4-1 e+ε N(p) < p

dla każdego $|ε> 0$ i $p > p (ε). 0$ Natomiast przy założeniu uogólnionej hipotezy Riemanna N.C. Ankeny pokazał oszacowanie znacznie lepsze

N(p) < C(log

Tak więc prymitywny algorytm testowania kolejnych liczb $s$ jest (warunkowo) bardzo efektywny.

Podsumujmy nasze dotychczasowe rozważania: jeśli moduł $n$ jest liczbą pierwszą, to w zasadzie potrafimy poradzić sobie zarówno z rozstrzygnięciem, czy $2$ jest resztą kwadratową modulo $n,$ jak i ze znalezieniem wszystkich rozwiązań kongruencji (1) w zbiorze $|{1,2,...,n − 1}$ (są dwa takie rozwiązania).

A jak jest dla liczb złożonych $n?$ Rozpatrzymy najprostszy przypadek, gdy $|n = pq$ jest iloczynem dwóch różnych liczb pierwszych. Do dzisiaj nie jest znana żadna efektywna uniwersalna metoda rozstrzygania, czy kongruencja (1) ma rozwiązanie. Załóżmy jednak, że dobra wróżka rzekła: Tak, kongruencja $|(1)$ jest rozwiązalna, a Twoje zadanie to znaleźć jej wszystkie rozwiązania $|x$ w zbiorze ${1,2,...,n − 1}$ . Załóżmy dalej, że jakimś cudem wypisaliśmy wszystkie (cztery - wynika to z chińskiego twierdzenia o resztach) rozwiązania kongruencji (1):

1⩽ x1 < x2 < x3 < x4⩽ pq − 1.

Ponieważ kongruencja $|y2≡ 2 (mod p)$ ma dokładnie dwa rozwiązania $|y1,y2$ w zbiorze $|{1,2,...,p −1},$ więc dla pewnych $1⩽ i < j ⩽ 3$ mamy $|x ≡ x (mod p), i j$ a zatem liczba $|x − x j i$ dzieli się przez $|p.$ Oczywiście, $|x j− xi$ nie dzieli się przez $n = pq,$ gdyż $1 ⩽xj −xi < pq− 2.$ A zatem

NWD(xj − xi,n) = p.

Liczby NWD $(x2 −x1,n),$ NWD $(x3− x2,n),$ NWD $(x3− x1,n)$ potrafimy obliczyć, bardzo efektywnie stosując najsłynniejszy algorytm na świecie - algorytm Euklidesa. W ten sposób znaleźliśmy nietrywialny dzielnik $| p$ liczby $| n = pq.$ Najbardziej pomógł nam cud (a nie wróżka). Tym samym naszkicowaliśmy główną myśl dowodu twierdzenia, że kompletne rozwiązanie kongruencji (1) dla modułu złożonego $|n$ jest co najmniej tak trudne, jak rozkład $n$ na czynniki pierwsze. Natomiast samo tylko rozstrzygnięcie, czy (1) ma rozwiązanie, wydaje się istotnie łatwiejsze niż rozkład na czynniki, ale jak już wspomnieliśmy wcześniej, nikt nie umie zrobić efektywnie nawet tego.