ROZDZIAŁ 3

DANE O LICZBACH
PSEUDOPIERWSZYCH
I SILNIE PSEUDOPIERWSZYCH


Informacje wstępne

Większość poniższych danych została opracowana przez autora pracy w oparciu o wyniki otrzymane dzięki dwóm specjalnie do tego celu napisanym programom, z których pierwszy sprawdzał pseudopierwszość danych liczb, a drugi – silną pseudopierwszość. W przypadku bardzo dużych liczb (szczególnie w przypadku danych zamieszczonych w części Informacje dodatkowe) informacje zaczerpnięto z książek, podanych w bibliografii.

W rozpatrywanym przez nas przedziale liczb naturalnych od 1 do 100001 włącznie występuje 9591 liczb pierwszych.

Liczby pseudopierwsze przy podstawie 2

Istnieje 78 liczb mniejszych od 100001, które są pseudopierwsze przy tej podstawie. Podajemy pierwsze dziesięć z nich i największą.

n = 341; n = 561; n = 645; n = 1105; n = 1387; n = 1729; n = 1905; n = 2047;
n = 2465; n = 2701; n = 93961

Liczby pseudopierwsze przy podstawie 3

Istnieje 76 liczb mniejszych od 100001, które są pseudopierwsze przy tej podstawie. Podajemy pierwsze dziesięć z nich i największą.

n = 91; n = 121; n = 671; n = 703; n = 949; n = 1105; n = 1541; n = 1729;
n = 1891; n = 2465; n = 97567

Liczby pseudopierwsze przy podstawie 5

Istnieje 66 liczb mniejszych od 100001, które są pseudopierwsze przy tej podstawie. Podajemy pierwsze dziesięć z nich i największą.

n = 217; n = 561; n = 781; n = 1541; n = 1729; n = 1891; n = 2821; n = 4123;
n = 5461; n = 5611; n = 98173

Liczby pseudopierwsze przy podstawie 7

Istnieje 69 liczb mniejszych od 100001, które są pseudopierwsze przy tej podstawie. Podajemy pierwsze dziesięć z nich i największą.

n = 25; n = 325; n = 561; n = 703; n = 817; n = 1105; n = 1825; n = 2101;
n = 2353; n = 2465; n = 97921

Liczby pseudopierwsze dla podstaw 2 i 3

Oto wszystkie liczby mniejsze od 100001, które są pseudopierwsze przy tych podstawach. Jest ich 17.

n = 1105; n = 1729; n = 2465; n = 2701; n = 2821; n = 6601; n = 8911; n = 10585; n = 15841; n =18721; n = 29341; n = 31621; n = 41041; n = 46657; n = 49141;
n = 52633; n = 63973

Liczby pseudopierwsze dla podstaw 2 i 5

Oto wszystkie liczby mniejsze od 100001, które są pseudopierwsze przy tych podstawach. Jest ich 16.

n = 561; n = 1729; n = 2821; n = 5461; n = 6601; n = 8911; n = 12801; n = 13981; n = 15841; n =29341; n = 41041; n = 46657; n = 52633; n = 63973; n = 68101;
n =
75361

Liczby pseudopierwsze dla podstaw 2 i 7

Oto wszystkie liczby mniejsze od 100001, które są pseudopierwsze przy tych podstawach. Jest ich 11.

n = 561; n = 1105; n = 2465; n = 3277; n = 8321; n = 10585; n = 18721;
n = 29341; n = 46657; n = 62745; n = 75361

Liczby pseudopierwsze dla podstaw 3 i 5

Oto wszystkie liczby mniejsze od 100001, które są pseudopierwsze przy tych podstawach. Jest ich 14.

n = 1541; n = 1729; n = 1891; n = 2821; n = 6601; n = 8911; n = 15841;
n = 29341; n = 41041; n = 46657; n = 52633; n = 63973; n = 75361; n = 88831

Liczby pseudopierwsze dla podstaw 3 i 7

Oto wszystkie liczby mniejsze od 100001, które są pseudopierwsze przy tych podstawach. Jest ich 13.

n = 703; n = 1105; n = 2465; n = 10585; n = 18721; n = 19345; n = 29341;
n = 38503; n = 46657; n = 50881; n = 75361; n = 76627; n = 88831

Liczby pseudopierwsze dla podstaw 5 i 7

Oto wszystkie liczby mniejsze od 100001, które są pseudopierwsze przy tych podstawach. Jest ich 9.

n = 561; n = 11041; n = 29341; n = 38081; n = 46657; n = 50737; n = 75361;
n = 79381; n = 88831

Liczby pseudopierwsze dla podstaw 2, 3 i 5

Oto wszystkie liczby mniejsze od 100001, które są pseudopierwsze przy tych podstawach. Jest ich 11.

n = 1729; n = 2821; n = 6601; n = 8911; n = 15841; n = 29341; n = 41041;
n =
46657; n = 52633; n = 63973; n = 75361

Liczby pseudopierwsze dla podstaw 2, 3 i 7

Oto wszystkie liczby mniejsze od 100001, które są pseudopierwsze przy tych podstawach. Jest ich 7.

n = 1105; n = 2465; n = 10585; n = 18721; n = 29341; n = 46657; n = 75361

Liczby pseudopierwsze dla podstaw 2, 5 i 7

Oto wszystkie liczby mniejsze od 100001, które są pseudopierwsze przy tych podstawach. Są tylko 4 takie.

n = 561; n = 29341; n = 46657; n = 75361

Liczby pseudopierwsze dla podstaw 3, 5 i 7

Oto wszystkie liczby mniejsze od 100001, które są pseudopierwsze przy tych podstawach. Są tylko 4 takie.

n = 29341; n = 46657; n = 75361; n = 88831

Informacje dodatkowe

Istnieje stosunkowo niewiele liczb pseudopierwszych dla podstawy b i tylko nieliczne liczby złożone przechodzą test bn º b (mod n). W szczególności mamy 455052512 liczb pierwszych mniejszych niż 1010, podczas gdy w tym samym przedziale istnieje 14884 liczb pseudopierwszych przy podstawie 2.

Liczby silnie pseudopierwsze przy podstawie 2

Test Millera-Rabina dla tej podstawy przechodzi 16 liczb mniejszych od 100001.

n = 2047; s = 1 i t = 1023; bt º 1 (mod n)

n = 3277; s = 2 i t = 819; b2t º –1 (mod n)

n = 4033; s = 6 i t=63; b2t º –1 (mod n)

n = 4681; s = 3 i t = 585; bt º 1 (mod n)

n = 8321; s = 7 i t = 65; b2t º –1 (mod n)

n = 15841; s = 5 i t = 495; bt º 1 (mod n)

n = 29341; s = 2 i t = 7335; b2t º –1 (mod n)

n = 42799; s = 1 i t = 21399; bt º 1 (mod n)

n = 49141; s = 2 i t = 12285; b2t º –1 (mod n)

n = 52633; s = 3 i t = 6579; bt º 1 (mod n)

n = 65281; s = 8 i t = 255; b16t º –1 (mod n)

n = 74665; s = 3 i t = 9333; b2t º –1 (mod n)

n = 80581; s = 2 i t = 20145; b2t º –1 (mod n)

n = 85489; s = 4 i t = 5343; b2t º –1 (mod n)

n = 88357; s = 2 i t = 22089; b2t º –1 (mod n)

n = 90751; s = 1 i t = 45375; bt º 1 (mod n)

Liczby silnie pseudopierwsze przy podstawie 3

Test Millera-Rabina dla tej podstawy przechodzą 23 liczby mniejsze od 100001.

n = 121; s = 3 i t = 15; bt º 1 (mod n)

n = 703; s = 1 i t = 351; bt º –1 (mod n)

n = 1891; s = 1 i t = 945; b2t º –1 (mod n)

n = 3281; s = 4 i t = 205; bt º –1 (mod n)

n = 8401; s = 4 i t = 525; bt º –1 (mod n)

n = 8911; s = 1 i t = 4455; bt º –1 (mod n)

n = 10585; s = 3 i t = 1323; b2t º –1 (mod n)

n = 12403; s = 1 i t = 6201; bt º –1 (mod n)

n = 16531; s = 1 i t = 8265; bt º –1 (mod n)

n = 18721; s = 5 i t = 585; b16t º –1 (mod n)

n = 19345; s = 4 i t = 1209; b2t º –1 (mod n)

n = 23521; s = 5 i t = 735; bt º –1 (mod n)

n = 31621; s = 2 i t = 7905; bt º –1 (mod n)

n = 44287; s = 1 i t = 22143; bt º –1 (mod n)

n = 47197; s = 2 i t = 11799; bt º 1 (mod n)

n = 55969; s = 5 i t = 1749; b16t º –1 (mod n)

n = 63139; s = 1 i t = 31569; bt º –1 (mod n)

n = 74593; s = 5 i t = 2331; b16t º –1 (mod n)

n = 79003; s = 1 i t = 39501; bt º –1 (mod n)

n = 82513; s = 4 i t = 5157; bt º 1 (mod n)

n = 87913; s = 3 i t = 10989; bt º 1 (mod n)

n = 88573; s = 2 i t = 22143; bt º 1 (mod n)

n = 97567; s = 1 i t = 48783; bt º –1 (mod n)

Liczby silnie pseudopierwsze przy podstawie 5

Test Millera-Rabina dla tej podstawy przechodzi 16 liczb mniejszych od 100001.

n = 781; s = 2 i t = 195; bt º 1 (mod n)

n = 1541; s = 2 i t = 385; bt º –1 (mod n)

n = 5461; s = 2 i t = 1365; bt º –1 (mod n)

n = 5611; s = 1 i t = 2805; bt º 1 (mod n)

n = 7813; s = 2 i t = 1953; b2t º –1 (mod n)

n = 13021; s = 2 i t = 3255; bt º –1 (mod n)

n = 14981; s = 2 i t = 3745; bt º 1 (mod n)

n = 15751; s = 1 i t = 7875; bt º 1 (mod n)

n = 24211; s = 1 i t = 12105; bt º 1 (mod n)

n = 25351; s = 1 i t = 12675; bt º 1 (mod n)

n = 29539; s = 1 i t = 14769; bt º 1 (mod n)

n = 38081; s = 6 i t = 595; b16t º –1 (mod n)

n = 40501; s = 2 i t = 10125; bt º 1 (mod n)

n = 44801; s = 8 i t = 175; bt º 1 (mod n)

n = 53971; s = 1 i t = 26985; bt º 1 (mod n)

n = 79381; s = 2 i t = 19845; bt º –1 (mod n)

Liczby silnie pseudopierwsze przy podstawie 7

Test Millera-Rabina dla tej podstawy przechodzi 21 liczb mniejszych od 100001.

n = 25; s = 3 i t = 3; b2t º –1 (mod n)

n = 325; s = 2 i t = 81; b2t º –1 (mod n)

n = 703; s = 1 i t = 351; bt º 1 (mod n)

n = 2101; s = 2 i t = 525; bt º –1 (mod n)

n = 2353; s = 4 i t = 147; b2t º –1 (mod n)

n = 4525; s = 2 i t = 1131; b2t º –1 (mod n)

n = 11041; s = 5 i t = 345; b2t º –1 (mod n)

n = 14089; s = 3 i t = 1761; b4t º –1 (mod n)

n = 20197; s = 2 i t = 5049; bt º 1 (mod n)

n = 29857; s = 5 i t = 933; b4t º –1 (mod n)

n = 29891; s = 1 i t = 14945; bt º –1 (mod n)

n = 39331; s = 1 i t = 19665; bt º 1 (mod n)

n = 49241; s = 3 i t = 6155; b4t º –1 (mod n)

n = 58825; s = 3 i t = 7353; b2t º –1 (mod n)

n = 64681; s = 3 i t = 8085; bt º –1 (mod n)

n = 76627; s = 1 i t = 38313; bt º 1 (mod n)

n = 78937; s = 3 i t = 9867; b4t º –1 (mod n)

n = 79381; s = 2 i t = 19845; bt º –1 (mod n)

n = 87673; s = 3 i t = 10959; b4t º –1 (mod n)

n = 88399; s = 1 i t = 44199; bt º 1 (mod n)

n = 88831; s = 1 i t = 44415; bt º –1 (mod n)

Liczby silnie pseudopierwsze przy podstawie 2, 3

Podajemy kilka przykładów liczb silnie pseudopierwszych dla tych podstaw. Otrzymano je dzięki programowi, który sprawdzał liczby począwszy od najmniejszej znanej liczby silnie pseudopierwszej dla dwóch podstaw.

n = 1373653; s = 2 i t = 343413; b12t º –1 (mod n); b2t º 1 (mod n)

n = 1373717; s = 2 i t = 343429; b12t º –1 (mod n); b22t º –1 (mod n)

n = 1373761; s = 6 i t = 21465; b116t º –1 (mod n); b264t º –1 (mod n)

n = 1373819; s = 1 i t = 686909; b1t º –1 (mod n); b2t º 1 (mod n)

n = 1400821; s = 2 i t = 350205; b12t º –1 (mod n); b2t º 1 (mod n)

Liczby silnie pseudopierwsze przy podstawie 2, 5

Podajemy kilka przykładów liczb silnie pseudopierwszych dla tych podstaw.

n = 1373677; s = 2 i t = 343419; b12t º –1 (mod n); b22t º –1 (mod n)

n = 1377031; s = 1 i t = 68851; b1t º 1 (mod n); b2t º 1 (mod n)

n = 1377037; s = 2 i t = 344259; b12t º –1 (mod n); b22t º –1 (mod n)

n = 1377847; s = 1 i t = 688923; b1t º 1 (mod n); b2t º –1 (mod n)

n = 1377853; s = 2 i t = 344463; b12t º –1 (mod n); b22t º –1 (mod n)

Liczby silnie pseudopierwsze przy podstawie 2, 7

Podajemy kilka przykładów liczb silnie pseudopierwszych dla tych podstaw.

n = 1373683; s = 1 i t = 686841; b1t º –1 (mod n); b2t º 1 (mod n)

n = 1377811; s = 1 i t = 688905; b1t º –1 (mod n); b2t º –1 (mod n)

n = 1377829; s = 2 i t = 344457; b12t º –1 (mod n); b22t º –1 (mod n)

n = 1377043; s = 1 i t = 688521; b1t º –1 (mod n); b2t º 1 (mod n)

n = 1377853; s = 2 i t = 344463; b1t º –1 (mod n); b2t º –1 (mod n)

Liczby silnie pseudopierwsze przy podstawie 3, 5

Podajemy kilka przykładów liczb silnie pseudopierwszych dla tych podstaw.

n = 1373683; s = 1 i t = 686841; b1t º –1 (mod n); b2t º –1 (mod n)

n = 1373717; s = 2 i t = 343429; b12t º –1 (mod n); b22t º –1 (mod n)

n = 1377037; s = 2 i t = 344259; b1t º 1 (mod n); b22t º –1 (mod n)

n = 1377791; s = 1 i t = 688895; b1t º 1 (mod n); b2t º 1 (mod n)

n = 1377821; s = 2 i t = 344455; b12t º –1 (mod n); b2t º 1 (mod n)

Liczby silnie pseudopierwsze przy podstawie 3, 7

Podajemy kilka przykładów liczb silnie pseudopierwszych dla tych podstaw.

n = 1373689; s = 3 i t = 171711; b1t º –1 (mod n); b22t º –1 (mod n)

n = 1373761; s = 6 i t = 21465; b164t º –1 (mod n); b264t º –1 (mod n)

n = 1373777; s = 4 i t = 85861; b116t º –1 (mod n); b216t º –1 (mod n)

n = 1377781; s = 2 i t = 344445; b1t º 1 (mod n); b22t º –1 (mod n)

n = 1377787; s = 1 i t = 688893; b1t º 1 (mod n); b2t º 1 (mod n)

Liczby silnie pseudopierwsze przy podstawie 5, 7

Podajemy kilka przykładów liczb silnie pseudopierwszych dla tych podstaw.

n = 1373789; s = 2 i t = 343447; b1t º 1 (mod n); b2t º –1 (mod n)

n = 1373803; s = 1 i t = 686901; b1t º –1 (mod n); b2t º –1 (mod n)

n = 1377023; s = 1 i t = 688511; b1t º –1 (mod n); b2t º –1 (mod n)

n = 1377031; s = 1 i t = 688515; b1t º 1 (mod n); b2t º 1 (mod n)

n = 1377041; s = 4 i t = 688515; b1t º –1 (mod n); b24t º 1 (mod n)

Informacje dodatkowe

Test Millera-Rabina jest stosunkowo dobrym testem sprawdzającym pierwszość, szczególnie gdy posiadamy następujące informacje. Najmniejsza liczba silnie pseudopierwsza złożona dla podstawy 2 to 2047, więc wszystkie liczby mniejsze od niej, które pozytywnie przejdą test Millera-Rabina, są pierwsze. Podobnie 1373653 to najmniejsza liczba silnie pseudopierwsza złożona dla podstaw 2 i 3, 25326001 – dla podstaw 2, 3 i 5, a 3215031751 – dla podstaw 2, 3, 5 i 7. Co więcej, istnieje tylko jedna liczba złożona silnie pseudopierwsza dla podstaw 2, 3, 5 i 7, która jest mniejsza niż 25 • 109, a jest nią 3251031751.

Hop do następnej części

więcej...