Str092

180    5. Liczby piorwt/e i rozkłttd ni orynniki

rozkładu na czynniki. Mianowicie skorzystamy z tego, żc jeśli tylko uda nam się znaleźć kongrucncję postaci /* m s³ (niod n), przy czym t ±s (mod n), to natychmiast znajdziemy nictrywialny dzielnik n, obliczając NWD(i 4* .v, n) (lub NWD(t - .v, «)). Jest tak dlatego, żc wówczas njf² — .v² = (t + s){t — .ę), podczas gdy n nic dzieli ani t H- .y, ani / — .y; zatem a — NWD(l + .v, n) musi być właściwym dzielnikiem liczby n, a liczba b — nja dzieli NWD (/ — .y, «).

Przykład 3. Chcemy rozłożyć na czynniki liczbę 4633 i zauważyliśmy, żc liczba 118² daje resztę 25 = 5² przy dzieleniu przez 4633. Wtedy obliczamy NWD(\\% + 5, 4633) = 41, NWD(\\% — 5, 4633) = 113 i otrzymujemy rozkład 4633 = 41 • 113.

Można dziwić się, w jaki sposób w przykładzie 3 mogliśmy w ogóle natrafić na liczbę taką jak 118, tzn. taką, że jej kwadrat daje przy dzieleniu przez 4633 resztę też będącą pełnym kwadratem. Czy losowe wybory różnych liczb b wkrótce dadzą liczbę taką, że reszta z dzielenia b¹ przez n jest pełnym kwadratem? Jest to bardzo mało prawdopodobne dla dużych n, zatem musimy uogólnić tę metodę w taki sposób, by mieć większą elastyczność w wyborze tych liczb 6, dla których będziemy obliczać resztę z dzielenia b² przez n. Pomysł polega na tym, by wybrać wiele liczb 6, takich, że reszty z dzielenia bf przez n rozkładają się na iloczyn małych liczb pierwszych, i takich, że pewien podzbiór zbioru tych b_t, po wymnożeniu, daje liczbę b, której kwadrat przystaje modulo n do innego pełnego kwadratu. Teraz podamy szczegóły tej metody.

Przez „bezwzględnie najmniejszą resztę'* z dzielenia liczby a przez liczbę n będziemy rozumieć liczbę całkowitą z przedziału od —n/2 do n/2, przystającą do a modulo n. Będziemy oznaczać ją przez a mod n.

Definicja. Bazą rozkładu nazywamy zbiór B= {p_ly p₂, ...» Ph) różnych liczb pierwszych, z tym wyjątkiem, że liczba p_t może być równa — 1. Mówimy, że liczba b jest B-liczbą (dla danego n), jeśli bezwzględnie najmniejsza reszta b² mod n rozkłada się na iloczyn liczb należących do zbioru B.

Przykład 4. Dla n — 4633 i B = { — 1, 2, 3} liczby 67, 68 i 69 są B-liczbami, gdyż 67² = —144 (mod 4633), 68² = —9 (mod 4633) oraz 69² = 128 (mod 4633).

Niech Fj oznacza przestrzeń liniową nad ciałem dwuelementowym, składającą się z ciągów zerojedynkowych długości h. Pokażemy, jak dla danej liczby n i danej bazy rozkładu B, zawierającej h liczb, każdej ZMiczbie b można przypisać pewien wektor <f e Fj. Mianowicie liczbę b² mod n zapisujemy w po-

h

staci jfj^J i wtedy y-tą współrzędną Ej wektora s jest reszta z dzielenia aj przez j= 1

2, tzn. Ej = 0 dla aj parzystych i ^ = 1 dla a_} nieparzystych.

j,_r/ykład 5. W sytuacji z przykładu 4 wektorem odpowiadającym liczbie 67 jeit (| 0,0), wektorem odpowiadającym liczbie 68 jest (1,0,0) i wektorem odpowiadającym liczbie 69 jest (0,1,0).

Przypuśćmy, że mamy dany pewien zbiór iMiczb bif mod n takich, źe odpowiadające im wektory e, = (e_n,.... %) sumują się do wektora zerowego _w przestrzeni Fj. Wtedy iloczyn bezwzględnie najmniejszych reszt liczb bf jest Iloczynem parzystych potęg wszystkich liczb należących do zbioru Zatem, jeśli przez o, oznaczymy bezwzględnie najmniejszą resztę z dzielenia bf przez

„ i zapiszemy a, w postaci a, = f] pf', to otrzymamy równość w

p |

przy czym wykładniki przy wszystkich potęgach p, po prawej stronie są parzyste. Zatem prawa strona jest kwadratem liczby f]pj', gdzie ‘/_} =

■    _    i    ²i

A więc, jeśli weźmiemy b = [jó, mod n (jest to bezwzględnie najmniejsza re-

t

szta) oraz c = f]pj^j mod n (jest to też bezwzględnie najmniejsza reszta), to

.J

otrzymamy dwie liczby b i c, skonstruowane na dwa zupełnie różne sposoby (jedna jest iloczynem liczb 6,, druga jest iloczynem liczb pj), których kwadraty przystają do siebie modulo n.

Może się tak nieszczęśliwie zdarzyć, że b = ±c (mod n) i wtedy musimy na nowo wybrać inny zbiór takich 5-liczb, że odpowiadające im wektory sumują się do wektora zerowego. Tak się zdarzy, jeśli nierozsądnie wybierzemy Mczby mniejsze niż yjn/2, gdyż wtedy wszystkie wektory są wektorami zerowymi i otrzymujemy trywialną kongruencję.

Ale ponieważ liczba n jest złożona, to dla liczb b_{ wybranych w bardziej losowy sposób możemy spodziewać się, że liczby b i c będą przystawały do siebie modulo n (z dokładnością do znaku) w co najwyżej 50% przypadków. Jest tak dlatego, że każdy kwadrat modulo n ma 2^r £ 4 pierwiastki kwadratowe, jeśli n ma r różnych dzielników pierwszych (por. ćwiczenie 7 w podrozdziale 1.3); zatem losowy pierwiastek kwadratowy z 6² jest równy b lub -6 z prawdopodobieństwem 2/2^r ^ 1/2. A z chwilą gdy znajdziemy takie b ic,żc b² = c² (mod n) oraz b # ±c (mod n), natychmiast obliczamy nietrywiainy dzielnik NJVD(b + c, n) liczby n, jak już to widzieliśmy wcześniej. A więc, jeśli będziemy powtarzać powyższą procedurę szukania b i c, to z prawdopodobieństwem co najwyżej 2“* będziemy potrzebować więcej niż k prób, by znaleźć parę dającą nietrywiainy dzielnik n.

Jak w praktyce wybieramy naszą bazę rozkładu B i nasze B-liczby 6,? Jedna metoda polega na tym, że najpierw wybieramy zbiór B, składający się z początkowych h liczb pierwszych (lub początkowych h - 1 liczb pierwszych