ROZDZIAŁ 4

WIADOMOŚCI TEORETYCZNE
O LICZBACH BARDZO SILNIE PSEUDOPIERWSZYCH


Definicja liczb bardzo silnie pseudopierwszych

Niech n będzie liczbą nieparzystą złożoną, p liczbą pierwszą dzielącą n – 1, a b1,…, bk liczbami naturalnymi względnie pierwszymi z n. Niech n – 1 = prm, gdzie p nie dzieli m. Mówimy że n jest bardzo silnie pseudopierwsza ze względu na liczbę pierwszą p i podstawy b1, b2, …, bk, (n jest bspp(p;b1, …, bk)), jeśli dla każdego a pojawiającego się w sekwencji:

(*)

Zbiór S(a) (czyli zbiór wszystkich reszt modulo n pojawiających się we wszystkich sekwencjach (*) przed a) ma następujące własności (II):

  1. Ostatnim wyrazem w sekwencji (*) modulo n jest 1.
  2. Dla każdych trzech różnych elementów y1, y2, y3 Î S(a), y3/y1 jest potęgą y2/y1 modulo n. W szczególności zbiór S(a) ma co najwyżej p elementów.
  3. Dla p = 2 mamy S(1) Ì {1, –1}.

Liczby pierwsze w obliczu definicji liczb pseudopierwszych

Załóżmy że n jest liczbą pierwszą. W takim przypadku prm = n – 1 = j(n) (gdzie j(n) to funkcja Eulera – patrz Definicja 7; dla liczby pierwszej n ma ona własność j(n) = n – 1). Stąd ostatnim wyrazem w sekwencji (*) jest 1 (mod n) (z twierdzenie Eulera – patrz Twierdzenie 3). Jeśli w sekwencji (*) pojawi się a (mod n) oraz

b > a,

to bp º a (mod n), tzn. b jest rozwiązaniem kongruencji xp º a (mod n), a ta kongruencja z Twierdzenia 13 ma dokładnie p rozwiązań. Niech x1, x2, …, xp będą tymi rozwiązaniami. W takim przypadku grupa {1, x2/x1, …, xp/x1} jest cykliczna rzędu p, gdyż każda grupa o rzędzie równym liczbie pierwszej jestcykliczna (jest to wniosek z twierdzenia Lagrange’a (1) - patrz Wniosek 2 do Twierdzenia 1). Ponieważ zaś S(a) = {y1, y2, …, yl} jest podzbiorem {x1, x2, …, xp} możemy stwierdzić, że w zbiorze {y2/y1, …,yl/y1} każdy element jest potęgą jakiegoś innego.

Tak więc liczby pierwsze spełniałyby założenia definicji liczb bardzo silnie pseudopierwszych, gdyby nie fakt, że n ma być liczbą nieparzystą złożoną.

Twierdzenie 17

Jeśli n jest liczbą bardzo silnie psuedopierwszą przy podstawie b i p = 2, to jest silnie pseudopierwsza przy podstawie b (bspp(2; b) jest spp(b)).

Dowód: Dane są n i b spełniające warunek (II). Musimy wykazać, że spełniają one warunek (I). Niechn – 1 = prm, gdzie p nie dzieli m. Dla p = 2 m musi być liczbą nieparzystą, a więc pełni rolę t. Mamy więc rozkład analogiczny jak w przypadku liczb silnie pseudopiewszych: n – 1 = 2rm. Dla p = 2 wiemy, że zbiór S(1) składa się wyłącznie z 1 i –1, a więc w sekwencji (*) może pojawić się –1, tzn. będzie istniała liczba h z przedziału [0, r), taka że , dzięki czemu liczba n spełnia warunek (I). W przypadku, gdy w sekwencji (*) mamy same 1, to spełniony jest warunek bt º 1 (mod n), co kończy dowód.

ROZDZIAŁ 5

PRZYKŁADY I WYNIKI
OBLICZEŃ DOTYCZĄCE LICZB
BARDZO SILNIE PSEUDOPIERWSZYCH


Informacje wstępne

Poniższe danych została opracowana przez autora pracy w oparciu o wyniki otrzymane dzięki specjalnie do tego celu napisanemu programowi.

Przykłady liczb bardzo silnie pseudopierwszych przy podstawie 2

n = 29341, p = 163, r = 1, m = 180, (*) modulo n: 1 1

n = 30121, p = 251, r = 1, m = 120, (*) modulo n: 1 1

n = 30889, p = 13, r = 1, m = 2376, (*) modulo n: 22288 1

n = 31417, p = 17, r = 1, m = 1848, (*) modulo n: 1 1

n = 31609, p = 439, r = 1, m = 72, (*) modulo n: 1 1

n = 31621, p = 31, r = 1, m = 1020, (*) modulo n: 1 1

Uwaga: Z powyższych liczb jedynie 29341 przechodzi test Millera-Rabina.

Przykłady liczb bardzo silnie pseudopierwszych przy podstawach 2, 3, 5

W wierszach podano kolejne wyrazy sekwencji (*) modulo n dla kolejnych podstaw, czyli pierwszy wiersz to kolejne wyrazy sekwencji (*) modulo n dla podstawy 2, drugi – dla podstawy 3, a trzeci – 5.

n = 2821, p = 5, r = 1, m = 564,

(*) modulo n: 729 1

1366 1

1 1

(1366/1)4 (mod 2821) = (729/1)


n = 6601, p = 3, r = 1, m = 2200,

(*) modulo n: 2830 1

1887 1

2830 1

(2830/1)2 (mod 6601) = (1887/1)

n = 29341, p = 3, r = 1, m = 5868,

(*) modulo n: 1925 1

1925 1

8659 1

(8659/1)3 (mod 29341) = (1925/1)

n = 41041, p = 3, r = 3, m = 1520,

(*) modulo n: 22551 1 1 1

40140 1 1 1

35179 1 1 1

(40140/22551)1 (mod 41041) = (35179/22551)

n = 46657, p = 3, r = 6, m = 64,

(*) modulo n: 20140 41614 1 1 1 1 1

13835 3784 1 1 1 1 1

41965 3784 1 1 1 1 1

(13835/1)3 (mod 46657) = (3784/1)

(20140/1)3 (mod 46657) = (3784/1)

(41695/1)3 (mod 46657) = (3784/1)

(41695/1)3 (mod 46657) = (3784/1)

n = 75361, p = 5, r = 1, m = 15072,

(*) modulo n: 39560 1

26079 1

68511 1

(68511/26079)120 (mod 7531) = (39560/26079)

Dla porównania, z powyższych liczb jedynie 29341 i 75361 przechodzą test Millera-Rabina i to tylko dlab = 2. Dla pozostałych dwóch podstaw nie przechodzą.

Garść danych

W przedziale od 1 do 100001 (oczywiście wyłączając z tego przedziału wszystkie liczby pierwsze, jako że liczby bardzo silnie pseudopierwsze są naturalne złożone) mamy 78 liczb bardzo silnie pseudopierwszych dla b = 2, w tym najmniejszą jest 341. Dla porównania test Millera-Rabina przechodzi 16 liczb z tego przedziału.

W przedziale od 1 do 100001 (oczywiście wyłączając z tego przedziału wszystkie liczby pierwsze, jako że liczby bardzo silnie pseudopierwsze są naturalne złożone) mamy 9 liczb bardzo silnie pseudopierwszych dla b1 = 2, b2 = 3 i b3 = 5 w tym najmniejszą jest 2821.

Porównanie liczb silnie pseudopierwszych i bardzo silnie pseudopierwszych

Najmniejszą liczbą silnie pseudopierwszą przy podstawach 2, 3 i 5 jest 25326001. Liczba ta jest jednocześnie bardzo silnie pseudopierwsza tylko dla dwóch podstaw: 2 i 3.

n = 25326001, p = 2, r = 4, m = 1582875; podstawy b1 = 2, b2 = 3

(*) modulo n: 2532600 1 1 1 1

2532600 1 1 1 1

n = 25326001, p = 2, r = 4, m = 1582875; podstawy b1 = 2, b2 = 5

(*) modulo n: 2532600 1 1 1 1

1 1 1 1 1

n = 25326001, p = 2, r = 4, m = 1582875; podstawy b1 = 3, b2 = 5

(*) modulo n: 2532600 1 1 1 1

1 1 1 1 1

Podobnie dzieje się i dla innych liczb.

n = 25326023, p = 2, r = 1, m = 12663011, b1 = 2, b2 = 3

(*) modulo n: 1 1

1 1

n = 25326047, p = 2, r = 1, m = 12663026, b1 = 2, b2 = 3

(*) modulo n: 1 1

1 1


BIBLIOGRAFIA


1. Jerzy Browkin Teoria ciał, PWN, 1977

2. Jerzy Browkin On very strong pseudoprimes, maszynopis

3. Neal Koblitz Wykład z teorii liczb i kryptografii, Wydawnictwa Naukowo-‑Techniczne, 1994

4. Ivan Niven i Herbert S. Zuckerman An Introduction to the Theory of Numbers (second edition), John Wiley & Sons, Inc., 1966

5. Kenneth H. Rosen Elementary Number Theory and its Applicatopns (third edition), Adison-Wesley Publishing Company, 1993

6. Wacław Sierpiński Arytmetyka teoretyczna, PWN, 1955

Hop do Archiwaliów.

więcej...