86001 Str089

174    5. IJc/by picrwwc ł rorkhid ni cenniki

.... v, sq różna, do liczby wszystkich takich par, gdzie f przebiega zbiór wszystkich funkcji z S do S i v₀ przebiega zbiór S, jest mniejszy od e~^x.

Dowód. Liczba wszystkich par jest równa r^H *, gdyż liczbę x₀ możemy wybrać na r sposobów oraz dla każdego argumentu at, wybranego spośród r różnych elementów v g S, wartość /(.v) możemy wybrać też na r sposobów. A ile jest par {f, .v₀), dla których wszystkie wartości x₀, x_l9 .... x, są różne? Liczbę jc₀ możemy wybrać na r sposobów, wartość f(x₀) = x_t możemy wybrać na r — I sposobów (gdyż nie może ona być równa x₀), wartość f(x_t) = x_z możemy wybrać na r - 2 sposoby itd., aż określimy wartości f(x) dla x = x₀, x_lt .... Xf_ j. Wartość f(x) dla pozostałych r — / argumentów x jest dowolna, tzn. istnieje r^T~^l sposobów wybrania tych wartości. Stąd wynika, żc całkowita liczba sposobów wybrania jc₀ i określenia wartości f(x) tak, by x₀, x_it...»x, były różne, wynosi

J-0

a szukany stosunek liczby par o żądanej własności do liczby wszystkich par (tzn. powyższa liczba podzielona przez r^r+1) wynosi

r—^ł n('--i)=ńfi-A

J-0    J=l \    ^TJ

Twierdzenie mówi, że logarytm tej liczby jest mniejszy od —A (gdzie /= 1 + [\/2Ar]). Aby dowieść twierdzenia, logarytmujemy iloczyn po prawej stronie i korzystamy z tego, że log(l — x) < — x dla 0 < x < 1 (geometrycznie oznacza to, że krzywa logarytmiczna leży poniżej stycznej do niej poprowadzonej w punkcie (1,0)). Korzystając ze wzoru na sumę pierwszych / liczb naturalnych, otrzymujemy

log

GaHhB

/(/+1) -/² < 2r ^<

U2Xr)^:

2 r    2r    2r

czego należało dowieść. To kończy dowód twierdzenia.

= -A ,

Znaczenie twierdzenia 5.2.1 polega na tym, że daje ono oszacowanie przypuszczalnego czasu działania metody p, o ile założymy, że nasz wielomian zachowuje się tak, jak losowe przekształcenie ze zbioru Z/rZ w siebie. Zanim jednak zajmiemy się bliżej tym oszacowaniem, dokonamy drobnego ulepszenia metody p, co zwiększy jej efektywność.

Przypomnijmy, że metoda p polega na kolejnym obliczaniu x_k — /(x_k_j) i porównywaniu x_k z wcześniejszymi x_i tak długo, aż znajdziemy taką parę, że NWD(x_k — Xj, ri) — r> 1. Ale dla dużych k obliczanie NWD(x_k — Xj, n) dla wszystkich j <k pochłania dużo czasu. Pokażemy teraz,

•_aIc można zmodyfikować ten algorytm, by dla każdego k wykonywać tylko •edno obliczenie największego wspólnego dzielnika. Przede wszystkim zauważ-_I„y_i że jeśli pewne indeksy k₀ i j₍₎ spełniają kongruencję x_kti m x_h (mod r) dla pewnego dzielnika r|n, to tę samą kongruencję będą spełniały dowolne indeksy lc i / mające tę samą różnicę k-j = k₀~ j₀. Aby się o tym przekonać, wystarczy przyjąć k = k₀ + m, j -j₀ + m i m razy podziałać wielomianem / na obie strony kongruencji x_ko s x_jo (mod r).

Opiszemy teraz sposób działania algorytmu p. Będziemy obliczać kolejne wartości x^k i dla każdego k postępujemy w następujący sposób. Przypuśćmy, że k jest liczbą (h + l)-bitową, tzn. 2* ^ k < 2*" *. Niech j będzie największą liczbą A-bitową: /= 2* - 1. Porównujemy wtedy x_k z tą szczególną liczbą Xj, tzn. obliczamy NWD(x_k - Xj, n). Jeśli ten największy wspólny dzielnik jest nietrywialnym dzielnikiem n, to kończymy wykonywanie algorytmu, w przeciwnym przypadku zamiast k bierzemy k +1.

Tak zmodyfikowany algorytm ma tę przewagę nad poprzednim, że dla każdego k musimy obliczyć tylko jeden największy wspólny dzielnik. Jego wadą jest to, że prawdopodobnie nie wykryjemy za pierwszym razem liczby k₀. dla której istnieje j_Q < k₀ taka, że NWD(x_ko - x_jo,n) = r> 1. Jednakże taką parę x_k, x_J} której różnica ma nietrywialny wspólny dzielnik z n, wykryjemy niedługo później. Mianowicie przypuśćmy, że liczba k_Q ma h +1 bitów. Weź-my/ = 2*⁺¹ - 1 i k=j+(k₀-j_Q) i zauważmy, że wtedy j jest największą liczbą (h + l)-bitową i k jest taką liczbą (A -I- 2)-bitową, że NWD(x_k - x_p ń) > 1. Zauważmy też, że k < 2^k+1 = 4 • 2* < 4]^.

Przykład 2. Powróćmy do przykładu 1, ale tym razem porównujmy każdą liczbę x_k tylko z liczbą x_jf gdzie j jest największą liczbą < k, postaci 2* - 1. Dla n = 91, f(x) = x² + 1 i jc₀ = 1 mamy x_k = 2, x₂ = 5, x₃ = 26, tak jak poprzednio, oraz jc₄ = 40 (gdyż 26² + 1 = 40 (mod 91)). Postępując zgodnie z opisanym wyżej algorytmem, znajdziemy dzielnik liczby n, gdy obliczymy NWDfa - x₃, n) = NWD (14,91) = 7.

Przykład 3. Rozłóżmy na czynniki liczbę 4087, używając do tego wielomianu f(x) = X² + x + 1 i wartości początkowej jc₀ = 2.

Rozwiązanie. Nasze obliczenia będą przebiegać w następujący sposób:

=/(2) = 7; NWD(x_l - % n) = NWD(1 - 2,4087) = 1;

*₂ =/(7) = 57; WD(jc₂ - *_lt n) = OTW>(57 - 7,4087) = 1;

*₃ =/(57) = 3307; NWD(x_z - *_lf n) = NMD(3307 - 7,4087) = I; m/(3307) s 2745 (mod 4087); NWD(x_A - % n) =

= NWD (2745 - 3307,4087) = 1;

*₅ s/(2745) a 1343 (mod 4087); NWD(x₅ - *₃, n) =

«JVH7)(1343 - 3307,4087) = 1;

*6 s/(1343) a 2626 (mod 4087); NWD(x₆ - % n) =

= NWD (2626 - 3307,4087) « 1;