75261 Str102

200    5. UcrHy (ijcrwut i ro?kbi(! ni cfylttilkl

Funkcja    >• którą zetknęliśmy się już w tym rozdziale

i która tradycyjnie jest oznaczana przez. lĄn), ma rząd wielkości między wielomianami zmiennej log n i wielomianami zmiennej n. Jeśli n « 10”, to L(n) ta 400. W poniższych przykładach wybierzemy P = 50, A = 500.

2. Dla t - \yjn) + I, [yjn ] -f 2.....[yjn) + A tworzymy kolumnę zawierającą

liczby i¹ - n.

X Dla każdej nieparzystej liczby pierwszej p < P sprawdzamy najpierw, czy

I (por. podrozdział 2.2); jeśli ta równość nie zachodzi, to wyrzuca

my liczbę p z bazy rozkładu.

4.    Dla nieparzystych liczb pierwszych p takich, że liczba n jest resztą kwadratową modulo p (przypadkiem p — 2 zajmujemy się osobno), rozwiązujemy kongrucncjc t² = n (mod p^p) dla [i = 1, 2,korzystając z metody opisanej w ćwiczeniu 20, w podrozdziale 2.2. Bierzemy coraz to większe wartości /i tak długo, aż stwierdzimy, że nie istnieją rozwiązania l przystające modulo n do jakiejkolwiek liczby całkowitej z przedziału [y/n ] + 1 ^ / < [Jn ] 4- A. Niech [i będzie największą liczbą, dla której istnieje w tym przedziale liczba t taka, że t² = n (mod p^p). Niech t_i i t₂ będą dwoma rozwiązaniami kongrucncji t¹ = n (mod p^p) takimi, że t₂ = - /_Ł (mod p^p) (t_i i t₂ nie muszą być wybrane z przedziału od [yjn ] + 1 do [Jn | + A).

5.    Nadal dla tej samej liczby pierwszej p przeglądamy listę liczb t² — n utworzoną w punkcie 2. W kolumnie poniżej p umieszczamy 1 przy wszystkich tych wartościach t² - n, dla których l różni się od t₂ o wielokrotność /?, zmieniamy 1 na 2 przy wszystkich tych wartościach t² — n, dla których / różni się od t_l o wielokrotnośćp², zmieniamy 2 na 3 przy wszystkich tych wartościach t² - n, dla których t różni się od t_Y o wielokrotność p³ itd. aż do p^p. Następnie robimy to samo dla t₂ zamiast t_v Największą liczbą, która pojawi się w tej kolumnie, będzie /?.

6.    Za każdym razem, gdy w czasie wykonywania procedury opisanej w punkcie 5 umieszczamy w kolumnie liczbę 1, zmieniamy 1 na 2, 2 na 3 itd., dzielimy odpowiednią liczbę t² — n przez p i zapamiętujemy wynik.

7.    W kolumnie odpowiadającej liczbie p — 2, jeśli n fś 1 (mod 8), to obok liczby t² - n dla nieparzystej liczby t umieszczamy 1 i dzielimy t² — n przez 2. Jeśli n = 1 (mod 8), to rozwiązujemy kongruencję t² = n (mod 2^P) i postępujemy dokładnie tak samo jak w przypadku nieparzystej liczby p (z tą tylko różnicą, że teraz będziemy mieli cztery różne rozwiązania: t_v t_2i /₃ i /₄ modulo 2* dla P > 3).

8.    Gdy wyczerpiemy wszystkie liczby pierwsze p < P, wykreślamy wszystkie liczby t² — ń\ z wyjątkiem tych, które po podzieleniu przez potęgi liczb p < P dały w wyniku 1. Otrzymamy w ten sposób tablicę taką jak w przykładzie 9 z podrozdziału 5.3, w której kolumna oznaczona przez b_{ zawiera

te liczby t z przedziału [jn ]+!</< [-Jn ] + A, dla których t² — n jest

/Miczbą, a pozostałe kolumny odpowiadają tym liczbom pierwszym p <■ P, dla których n jest resztą kwadratową modulo p.

9, Dalsze czynności są dokładnie takie same jak w podrozdziale 5.3.

przykład. Rozłóżmy na czynniki liczbę n = 1042387, przyjmując ograniczenia górne P = 50 i A - 500. Wtedy [yjn ] = 1020. Nar/a baza rozkładu składa się i ośmiu liczb pierwszych {2, 3, 11, 17, 19, 23, 43, 47}, dla których liczba 1042387 jest resztą kwadratową. Ponieważ n $ I (mod 8j, więc kolumna odpowiadająca liczbie p = 2 zawiera tylko 1 i 0, przy czym 1 występuje obok wszystkich nieparzystych / z przedziału 1021 < / < 1520.

Opiszemy teraz szczegółowo, w jaki sposób tworzy się kolumnę odpowiadającą liczbie p = 3. Szukamy rozwiązania = t_{l 0}+ /,, • 3 + t_{l 2} • 3² + +... + fi,f-i * 3*"¹ kongruencji t\ s 1042387 (mod 3*), gdzie t_UJe{0, l, 2} (drugie rozwiązanie t₂ otrzymamy ze wzoru t₂ = 3* - /,). Oczywiście możemy przyjąć /₁₍q = 1. (Dla każdej z ośmiu naszych liczb pierwszych pierwszy krok - rozwiązanie kongruencji t² = 1042387 (mod p) - może być zrobiony metodą kolejnych prób; jeśli mamy do czynienia z większymi liczbami pierwszymi, możemy skorzystać z metody opisanej na końcu podrozdziału 2.2.) Następnie rozwiązujemy kongruencję modulo 9: (1 + 3/_u)² = 1042387 = 7 (mod 9), czyli 6ł_ltl s 6 (mod 9), czyli 2/_u = 2 (mod 3); stąd /_u = 1. Następnie mamy kongruencję modulo 27: (1 + 3 + 9f_lt2)²s 1042387 = 25 (mod 27), czyli 16 + 18/_li2 = 25 (mod 27), czyli 2/₁₂ = 1 (mod 3); stąd t_i2 = 2. Następna kongruencja modulo 81: (1 -ł- 3 + 18 + 27/₁₃)² = 1042387 = 79 (mod 81), prowadzi do rozwiązania f₁₃ = 0. Powtarzamy to postępowanie aż do 3⁷, znajdując rozwiązania (zapisane w systemie pozycyjnym o podstawie 3, zgodnie z notacją z podrozdziału 1.1): /_t = (210211)₃ (mod 3⁷) oraz t₂ = = (2012012)₃ (mod 3⁷). Jednakże żadna liczba t z przedziału między 1021 i 1520 nie przystaje do t_t lub do t₂ modulo 3⁷. Zatem § - 6 i możemy przyjąć t_{ = (210211)₃ = 589 = 1318 (mod 3⁶) oraz t₂ = 3⁶ -1_{ = 140 = 1112 (mod 3⁵) (zauważmy, że żadna liczba z przedziału od 1021 do 1520 nie przystaje do t₂ modulo 3⁶).

Teraz konstruujemy nasze „sito” dla liczby pierwszej p = 3 w następujący sposób. Jako pierwszą bierzemy liczbę 1318, a następnie odliczamy co trzecią liczbę w dół, aż dojdziemy do 1021, oraz w górę, aż dojdziemy do 1519, za każdym razem stawiając 1 w naszej kolumnie, dzieląc odpowiednią liczbę t² — n przez 3 i zapamiętując wynik dzielenia. (W rzeczywistości dla nieparzystych liczb t dzielimy przez 3 połowę liczby l² - n, gdyż samą liczbę t² - n podzieliliśmy już przez 2, gdy tworzyliśmy kolumnę zer i jedynek, odpowiadającą liczbie 2). Następnie robimy to samo, skacząc co 9 i za każdym razem zmieniając 1 na 2, dzielimy ostatni iloraz liczby t² - n przez następną trójkę i zapamiętujemy wynik. Powtarzamy tę procedurę, skacząc co 27, 81, 243 i 729 liczb (skok o 729 nie jest możliwy, po prostu zmieniamy 5 na 6 obok liczby 1318 i dzielimy ostatni iloraz 1318² - 1042387 przez następną trójkę).