Str087

170    5. I .iozhy pforwifc i rozkład na czynniki

9. («) Wykorzystaj test (1) do pokazania, że liczba 2047 = 2¹¹ - 1 jest złożona.

(b) Wyjaśnij, dlaczego nic powinniśmy testować, czy liczba Fermata 2²* + 1 lub liczba Mcrscnnc’a 2^r - 1 jest pierwsza, za pomocą testu (I) z b = 2. A czy można użyć testu (2) z b = 2? A testu (3) z b = 2?

JO. Przypuśćmy, że liczba m jest taką całkowitą liczbą dodatnią, że liczby 6m+l. 12/w-fl i 18m + l są pierwsze. Niech n = (6m + l)(\2m + -f l)(I8m + 1). Udowodnij, że liczba n jest liczbą Carmichaela. Uwaga. Nic wiadomo, czy istnieje nieskończenie wiele liczb Carmichaela postaci n = (6m -F l)(12m + l)(18m + 1), ale argumenty heurystyczne sugerują, że tak jest.

11.    Wykaż, że następujące liczby są liczbami Carmichaela: 1105 = 5 • 13 * 17; 1729 = 7 13 19; 2465 = 5-17 - 29; 2821 =7-13-31; 6601 =7-23-41; 29341 = 13 - 37 - 61; 172081 = 7-13-31-61; 278545 = 5-17-29-113.

12.    (a) Znajdź wszystkie liczby Carmichaela postaci 3pq (gdzie liczby p i q są

pierwsze).

(b)    Znajdź wszystkie liczby Carmichaela postaci 5pq (gdzie liczby p i q są pierwsze).

(c)    Udowodnij, że dla ustalonej liczby pierwszej r istnieje tylko skończenie wiele liczb Carmichaela postaci rpq (gdzie liczby p i q są pierwsze).

13.    Udowodnij, że liczba 561 jest najmniejszą liczbą Carmichaela.

14.    Podaj przykład liczby złożonej n i podstawy b, takich że b^{n~^l)l2 = ±1 (mod n), ale n nie jest liczbą pseudopierwszą Eulera przy podstawie b.

15.    (a) Udowodnij, że jeśli n jest liczbą pseudopierwszą Eulera przy podstawie

be(Z/nZ)*, to jest też liczbą pseudopierwszą Eulera przy podstawach —b i b~^l.

(b) Udowodnij, że jeśli n jest liczbą pseudopierwszą Eulera przy podstawach b_t i b₂, to jest też liczbą pseudopierwszą Eulera przy podstawie ś = V₂.

16.    Niech liczba n będzie postaci p(2p — 1), jak w ćwiczeniu l(d).

(a)    Udowodnij, że n jest liczbą pseudopierwszą Eulera dla 25% wszystkich możliwych podstaw 6g(Z//iZ)*.

(b)    Znajdź klasę takich liczb n tej postaci, że n jest liczbą silnie pseudopierwszą dla 25% wszystkich możliwych podstaw.

17.    Niech liczba n będzie postaci n — (6m + l)(12m -I- l)(18m -f 1), jak w ćwiczeniu 10. Udowodnij, że (a) jeśli liczba m jest nieparzysta, to n jest liczbą pseudopierwszą Eulera dla 50% wszystkich możliwych podstaw 6g(Z/«Z)*; (b) jeśli liczba m jest parzysta, to n jest liczbą pseudopierwszą Eulera dla 25% wszystkich możliwych podstaw.

18.    (a) Oszacuj za pomocą notacji O liczbę operacji na bitach potrzebnych do

przeprowadzenia testu Millera-Rabina na liczbie n tyle razy, by prawdopodobieństwo tego, że liczba n jest złożona, było mniejsze od 1/m, przy założeniu, że przeszła ona pomyślnie przez wszystkie testy (liczby m i n są tu bardzo duże).

5,1, Liczby jweodopierww* 171

(b) Zakładając uogólnioną hipotezę Riemanna, oszacuj liczbę operacji na bitach potrzebnych do przeprowadzenia testu Millera-Rabina tyle razy, by mieć pewność, źe liczba n, która przeszła pomyślnie przez wszystkie testy, jest pierwsza,

,ę (a) Udowodnij, źe jeśli liczba n jest pseudopierwszą przy podstawie 2, to liczba N - 2" - 1 jest liczbą silnie pseudopierwszą i liczbą pseudopierwszą Eulera przy podstawie 2.

(b) Udowodnij, że istnieje nieskończenie wiele liczb silnie pseudopierw-szych i pseudopierwszych Eulera przy podstawie 2.

20.    Udowodnij, że jeśli liczba n jest silnie pseudopierwszą przy podstawie b, to jest silnie pseudopierwszą przy podstawie b^k dla dowolnej liczby całkowitej dodatniej k.

21.    Niech n będzie liczbą Carmichaela 561.

(a)    Wyznacz liczbę podstaw óe(Z/561Z)*, dla których liczba 561 jest liczbą pseudopierwszą Eulera.

(b)    Wyznacz liczbę podstaw, przy których liczba 561 jest silnie pseudopierwszą oraz wypisz te podstawy.

22.    Udowodnij, że jeśli liczba n jest potęgą liczby pierwszej p^J, gdzie i > 1, to jest ona silnie pseudopierwszą przy podstawie b wtedy i tylko wtedy, gdy jest pseudopierwszą przy podstawie b.

23.    (a) Wykaż, że liczba 65 jest silnie pseudopierwszą przy podstawach 8 i 18,

ale nie jest silnie pseudopierwszą przy podstawie 14, będącej iloczynem liczb 8 i 18 modulo 65.

(b) Dla dowolnej nieparzystej liczby złożonej n niech (*) oznacza zdanie: , jeśli n jest silnie pseudopierwszą przy podstawach i ń₂, to jest też silnie pseudopierwszą przy podstawie b = b_xbi (inaczej mówiąc, własność bycia liczbą silnie pseudopierwszą ma się zachowywać przy mnożeniu podstaw). Udowodnij, że liczba n ma własność (*) wtedy i tylko wtedy, gdy jest potęgą liczby pierwszej lub jest podzielna przez liczbę pierwszą przystającą do 3 modulo 4.

24.    (a) Udowodnij, że jeśli umiemy znaleźć taką podstawę b, że liczba n jest

pseudopierwszą przy podstawie 6, ale nie jest silnie pseudopierwszą przy podstawie ó, to umiemy też szybko znaleźć nietrywialny dzielnik n.

(b) Wyjaśnij, w jaki sposób można się przed tym zabezpieczyć, wybierając liczbę n == pq potrzebną do systemu kryptograficznego RSA.

Uwaga. Wiele testów pierwszości ma tę własność, że jeśli liczba złożona n przechodzi pomyślnie przez pewien początkowy test, a następnie nie przechodzi przez następny, to nie tylko dowiadujemy się, żc jest ona liczbą złożoną, ale również możemy łatwo znaleźć jej nietrywialny dzielnik. Ćwiczenie 24 jest przykładem tego: jeśli liczba n przechodzi pomyślnie przez test polegający na sprawdzeniu, czy jest ona pseudopierwszą przy jakiejś podstawie 6, a następnie okazuje się, żc nic jest ona silnie pseudopierwszą, to możemy łatwo rozłożyć ją