49959 Str139

375 Odpowiedzi tło ćwiczeń

6.    Przypuśćmy, że a nic ma wspólnego dzielnika z n (w przeciwnym przypadku natychmiast znaleźlibyśmy dzielnik n, obliczając NWD(a, n), i nie musielibyśmy stosować metody p). Wtedy f(x) = fljr + /» jest przekształceniem wzajemnie jednoznacznym zbioru Z/rZ na siebie (dla dowolnego r|w), a więc oczekiwana liczba kroków, zanim nastąpi powtórzenie module r. jest rzędu r/2 (na podstawie ćwiczenia 5(b)), a nie s/r , czyli jest znacznie gorsza.

7.    (a) 2* ss f (mod r - 1)

(b)    /1= ,v i k = s + m, gdzie m jest rzędem liczby 2 modulo t, tzn. najmniejszą liczbą dodatnią taką, że 2" = 1 (mod /). Liczba m jest także długością okresu w rozwinięciu dwójkowym liczby 1 //, o czym możemy się

oo

przekonać, pisząc 2^m — 1 = ut i następnie 1// = u £ 2~^mt.

i=i

(c)    Liczba k może łatwo mieć rząd tak duży jak r, np. jeśli r — 1 jest podwojoną liczbą pierwszą oraz 2 okaże się być generatorem modulo ta liczba pierwsza (w tym przypadku s = 1, m = (r — 3)/2).

5.3

1.    (a) (korzystamy z / = [>/n] + 1 = 93) 89 • 97; (b)_ (korzystamy z t - [yjn] + 4 = 903) 823 * 983; (c) (korzystamy z t = [>/n] + 6 = 9613) 9277 • 9949; (d) (korzystamy z i = [*s/w] + 1 = 9390) 9343 • 9437; (e) (korzystamy z t = [>/n] + 8 = 75) 43 • 107.

2. W rozkładzie n — ab, gdzie a > b, jeśli a <n+ ifn, to b — nja> nfty/n +tfn)> Jn - tjn. Natomiast, jeśli b> <Jn — yn, to wtedy a <<Jn + %jn +2, gdyż w przeciwnym razie mielibyśmy n = = ab > (Jn + Mn + 2)(yjn - łjn) = n -I- <Jn — 2yjn > n (dla n>15; dla kilku początkowych n wykonujemy ćwiczenie 2 oddzielnie). Zatem w każdym przypadku a — b< 2($/n + 1). Jeżeli metoda Fermata zawiedzie w pierwszej próbie, to s i t odpowiadające rozkładowi n — ab spełniają nierówności: t>-Jn +1, a więc s = Jt²—n >\]Ęjj& +1)² — n =

= y2Jn 4* 1 > yj2 ijn, co przeczy nierówności s = (a ~ b)l2 <i/n + l dla n > 33.

3.    (a) Mielibyśmy t² — s² = kn = 2 (mod 4); ale różnica dwóch kwadratów

nie może przystawać do 2 modulo 4.

(b) Mielibyśmy t² — s² = An = 4 (mod 8), co może mieć miejsce tylko dla t i s parzystych; ale wtedy (//2)² — n = (s/2)² i prosta metoda fakto-ryzacji Fermata działałaby równie dobrze.

4.    (a) (korzystamy z / = [-y/3/i] + 1 = 455) 149 • 463; (b) (korzystamy z t =

= [v/3«]+2=9472) 3217*9293; (c) (korzystamy z /=[>/5n]+1 = 9894) 1973 • 9923; (d) (korzystamy z / = [yjtn] + 2 = 9226) 1877 • 9067.

5    s (2, 3}; wektorami są (0, I) i (0, I); b » 52 *53 morf w» 55,

' _c • 2 • 3² = 18; AffW>(55 + 18,2701) = 73; 2701 - 37'73.

6    ff = { — 1, 2, 3, 61}; wektorami są (1, 0, 0, 0), (1, 0, 0, 1) i (0, 0, 0, 1);

’ /_;= 68- 152- 153 mod n = 1555, c * 2 • 3 • 61 =366;

ATO(1555 + 366,4633) =113; 4633 = 41 • 113.

7.    (a) Oszacuj różnicę, obliczając sumę pól „obszarów trójkątnych” między

wykresem funkcji logarytmicznej i sumą prostokątów sumy Ricraanna.

n

(b)    Porównaj Jlog jcrfx z sumą pól trapezów, których górne ramiona łączą

i

punkty o współrzędnych (), logj), a następnie wykaż, że całkowite pole obszaru zawartego między krzywą i tymi trapezami jest ograniczone przez stalą.

(c)    lim lógj/1 - (logy - l)j = 0, a więc wynikiem jest log>- - 1.

8.    (a) (7* 2“")(1 - 2""⁺¹)...(l - r"**'¹); (b) 0,298.

9.    Wyrażenie z metody p zwiększy się 3,2 • 10¹² razy, podczas gdy wyrażenie z metody baz rozkładu zwiększy się 2,6 * 10* razy.

10.    (a) Dla s<s₀ mamy h(ś) ź f(s) > f(s₀) = ~ h(s_a), a dla s> s₀ mamy

Ks)’źg(s)>g(s₀) = ^h(s_(i).

(b) Zastosuj (a) do funkcji log(/(f)) i log(g(j)).

5.4

, SI 11 II II ¹'^(a)^⁺ii⁺[«^:

^(b) [J+lJ+l+l+lJ+lJ+lJ+l+lm¹

^{(0) 1+}fł⁺fł⁺f2⁺|4‘    j

2. (a) Ponieważ a H— -x_t więc x jest pierwiastkiem dodatnim równania

x² - ax — 1 = 0, czyli x = (a -ł- Ja² + 4 )/2.

(b) Ponieważ wszystkie a, są równe 1, więc równania rekurencyjne opisujące liczniki i mianowniki reduktów są takie same jak dla liczb Fibonacciego.

o ii i ii ii

^ 'KpifeSl

1 1+6

można pokazać, że wszystkie

flj dla i = 2 (mod 3) są kolejnymi liczbami parzystymi, a wszystkie pozostałe a, są równe 1.

3.