15033 Str090

176    5. tJorby plerws/o rozkład tui czynniki

v₇ a? f(2bl(i) » 3734 (mod 4087); N^,]VD(x₁ — x₃, ń) -*NWD[3734 - 3307,4087) * 61.

Zatem otrzymujemy poszukiwany rozkład 4087 = 61 • 67.

Twierdzenie 5.2.2. Niech n będzie nieparzystą liczbą złożoną i niech r będzie nietrywialnym dzielnikiem liczby n, mniejszym od n (tzn. r\n oraz 1 <r < sjn ; zakładamy, że próbujemy znaleźć ten dzielnik r). Je Mi wybrana para (/. .v₀), składająca się z wielomianu f o współczynnikach całkowitych i wartości początkowej x₀, zachowuje się tak jak para losowa w sensie twierdzenia S.2J (/ traktujemy jako funkcję ze zbioru Z/rZ w siebie, a x₀jako element tego zbioru), to metoda p odnajdzie z dużym prawdopodobieństwem dzielnik r, wykonując 0{^jn\o%^ln) operacji na bitach. Mówiąc dokładniej, istnieje taka stała C, że dla dowolnej dodatniej liczby rzeczywistej X prawdopodobieństwo tego, że metoda p nie wskaże nietrywialnego dzielnika n po wykonaniu C*JX \fn log³ w operacji na bitach, jest mniejsze niż e~^l.

Dowód. Niech Cj będzie taką stalą, że dla dowolnych liczb y, z^n, NWD(y - z, n) może być obliczony za pomocą C₁log³n operacji na bitach (por. podrozdział 1.3). Niech C₂ będzie taką stałą, że dla dowolnej liczby x<n reszta z dzielenia f(x) przez n może być obliczona za pomocą C₂log²7* operacji na bitach (por. podrozdział 1.1). Jeśli k₀ jest pierwszym indeksem, dla którego istnieje indeks j_Q < k₀ taki, że x_ko s x_Jo (mod r), to opisany powyżej algorytm p znajdzie r w fc-tym kroku, gdzie k < 4k₀. (Mówiąc dokładniej, może się zdarzyć, że liczba x_k — Xj ma większy wspólny dzielnik z n, tzn. NWD((x_k - xj)/r, n/r) > 1; ale szansa na to, że losowa liczba całkowita ma nietrywialny dzielnik z n/r, jest mała, zwłaszcza wtedy, gdy n jest iloczynem małej liczby dużych liczb pierwszych. Możemy więc zaniedbać tę możliwość, która zresztą mogłaby tylko wpłynąć na niewielkie zwiększenie stałej C w tezie twierdzenia.)

Zatem liczba operacji na bitach potrzebnych do znalezienia r jest ograniczona z góry przez 4k₀(C_xlog³n + C₂log^?«). Z twierdzenia 5.2.1 wynika, że prawdopodobieństwo tego, iż liczba k₀ jest większa niż 1 -f- -j2Xr , jest mniejsze niż e~^x. Jeśli liczba k₀ nie jest większa niż 1 + \j2Xr , to liczba operacji na bitach potrzebnych do znalezienia r jest ograniczona przez (korzystamy tu z założenia r <yjn):

4(1 + j2Xr)(C₁\og³n + C₂log²n) <

<4(1 + -J2 y/X y/n)(C_k\og*n + C₂log²/j).

Jeśli wybierzemy stałą C trochę większą od 4^/2 (C_x -t- C₂) (tak by wziąć pod uwagę to, że dodajemy jedynkę), to okaże się, że dzielnik r zostanie znaleziony - tak jak należało udowodnić po wykonaniu C\/ż *//j log³n operacji na bitach, chyba źc dokonamy nieudanego wyboru pary (/, x₀), co może się zdarzyć z prawdopodobieństwem mniejszym od e"\

Uwagi:

1.    Podstawowym założeniem leżącym u podstaw metody p jest to, że można znaleźć wielomiany zachowujące się tak jak losowe funkcje w sensie twierdzenia 5.2.1. To nie zostało dowiedzione. Jednakże dotychczasowe doświadczenie w stosowaniu metody p do rozkładania liczb na czynniki sugeruje, że „przeciętny” wielomian zachowuje się jak „przeciętne” przekształcenie oraz źc pewne bardzo proste wielomiany (najbardziej popularnym jest f{x) = x² + 1) są takimi „przeciętnymi” wielomianami.

2.    Zgodnie z twierdzeniem 5.2.2, jeśli wybierzemy wystarczająco dużą liczbę ż, by wierzyć w powodzenie metody - np. e'¹ wynosi tylko 0,0001 dla >1 = 9 - to możemy być prawie pewni tego, że dla przeciętnej pary (/ x₀) rozłożymy liczbę n na czynniki za pomocą 3 Cyfn log³n operacji na bitach.

Ćwiczenia

W ćwiczeniach 1 -4 zastosuj metodę p dla podanych f(x) i x₀, by rozłożyć liczbę n na czynniki. W każdym przypadku porównuj x_k tylko z x. dla 7 = 2*- 1 (gdziek jest liczbą{h + l)-bitową).

1.    x² — 1, .x₀ = 2, n - 91.

2.    x² + 1, x₀ — 1, n = 8051.

3.    x² — 1, jc₀ = 5, n = 7031.

4.    x³ + x + 1, jc₀ = 1, n = 2701.

5.    Niech S będzie zbiorem mającym r elementów i niech przekształcenia / w parach (/, x₀) przebiegają wszystkie bijekcje zbioru S na siebie (tzn. przekształcenia wzajemnie jednoznaczne zbioru S na siebie - żadne dwa argumenty x nie dają tej samej wartości /(*)). Tak jak poprzednio, niech Xj_+l = f(xj) dla j = 0, 1,2,.... Dla każdej pary (f x₀) niech k oznacza pierwszy indeks, dla którego istnieje taki indeks j < k, że /(.r*) = f(xj). Udowodnij, że

(a)    liczba k jest nie większa niż r oraz dla każdej liczby z przedziału od 1 do r prawdopodobieństwo tego, że k jest tą liczbą, wynosi 1 /r;

(b)    wartość średnia k wynosi (r + l)/2 (przy czym wartość średnia jest brana ze względu na wszystkie pary (/ x₀), w których/jest bijekcją).

6.    Korzystając z ćwiczenia 5, wyjaśnij, dlaczego wielomian liniowy ax + b nigdy nie powinien być używany jako wielomian f(x) w metodzie p.

7.    Załóżmy, że chcemy za pomocą metody p rozłożyć na czynniki liczbę mającą dzielnik pierwszy r. Decydujemy się na wybór wielomianu f{x) — x² jako funkcji, której wartości będziemy iterować. (Jest to zły wybór f{x\ o czym wkrótce się przekonamy). Chcemy wyznaczyć pierwszą wartość