Zawartość

• Kroki
• Część 1 z 3: Testy prostoty
• Część 2 z 3: Jak działają testy prostoty
• Część 3 z 3: Korzystanie z chińskiego twierdzenia o reszcie
• Porady
• Czego potrzebujesz

Liczby pierwsze to liczby, które są podzielne tylko przez siebie i przez 1. Wszystkie inne liczby nazywane są liczbami złożonymi. Istnieje wiele sposobów określenia, czy liczba jest liczbą pierwszą, i wszystkie mają swoje wady i zalety. Z jednej strony niektóre metody są bardzo dokładne, ale są dość złożone, jeśli masz do czynienia z dużymi liczbami. Z drugiej strony są znacznie szybsze sposoby, ale mogą prowadzić do błędnych wyników. Wybór odpowiedniej metody zależy od tego, z jak dużymi liczbami pracujesz.

Kroki

Część 1 z 3: Testy prostoty

Notatka: we wszystkich formułach n oznacza numer do sprawdzenia.

1. 1 Wyliczanie dzielników. Wystarczy podzielić n do wszystkich liczb pierwszych od 2 do wartości zaokrąglonej (${ styl wyświetlania { sqrt {n}}}$).
2. 2 Małe twierdzenie Fermata. Ostrzeżenie: czasami test błędnie identyfikuje liczby złożone jako pierwsze, nawet dla wszystkich wartości a.
   • Wybierzmy liczbę całkowitą atak, że 2 ≤ a ≤ n - 1.
   • Jeśli a (mod n) = a (mod n), liczba jest prawdopodobnie liczbą pierwszą. Jeśli równość nie jest spełniona, liczba n jest złożona.
   • Sprawdź podaną równość dla wielu wartości aaby zwiększyć prawdopodobieństwo, że testowana liczba jest rzeczywiście pierwsza.
3. 3 Test Millera-Rabina. Ostrzeżenie: czasami, choć rzadko, dla wielu wartości a, test błędnie zidentyfikuje liczby złożone jako pierwsze.
   • Znajdź wielkości s i d takie, że ${ displaystyle n-1 = 2 ^ {s} * d}$.
   • Wybierz liczbę całkowitą a w zakresie 2 ≤ a ≤ n - 1.
   • Jeśli a = +1 (mod n) lub -1 (mod n), to n jest prawdopodobnie liczbą pierwszą. W takim przypadku przejdź do wyniku testu. Jeśli równość nie utrzyma się, przejdź do następnego kroku.
   • Podnieś swoją odpowiedź do kwadratu (${ displaystyle a ^ {2d}}$). Jeśli otrzymasz -1 (mod n), to n jest prawdopodobnie liczbą pierwszą. W takim przypadku przejdź do wyniku testu. Jeśli równość się nie powiedzie, powtórz (${ displaystyle a ^ {4d}}$ i tak dalej) aż ${ displaystyle a ^ {2 ^ {s-1} d}}$.
   • Jeśli w pewnym momencie po podniesieniu do kwadratu liczby innej niż ${ styl wyświetlania pm 1}$ (mod n), masz +1 (mod n), więc n jest liczbą złożoną. Jeśli ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), to n nie jest liczbą pierwszą.
   • Wynik testu: jeśli n przejdzie test, powtórz go dla innych wartości aaby zwiększyć pewność siebie.

Część 2 z 3: Jak działają testy prostoty

1. 1 Wyliczanie dzielników. Z definicji liczba n jest prosty tylko wtedy, gdy nie jest podzielny przez 2 i inne liczby całkowite z wyjątkiem 1 i siebie. Powyższy wzór pozwala na usunięcie zbędnych kroków i zaoszczędzenie czasu: np. po sprawdzeniu, czy liczba jest podzielna przez 3, nie ma potrzeby sprawdzania, czy jest podzielna przez 9.
   • Funkcja floor (x) zaokrągla x do najbliższej liczby całkowitej mniejszej lub równej x.
2. 2 Dowiedz się o arytmetyce modularnej. Operacja „x mod y” (mod jest skrótem łacińskiego słowa „modulo”, czyli „moduł”) oznacza „podziel x przez y i znajdź resztę”. Innymi słowy, w arytmetyce modularnej, po osiągnięciu pewnej wartości, która nazywa się moduł, liczby ponownie "zwracają" na zero. Na przykład zegar odlicza moduł 12: pokazuje 10, 11 i 12 godzin, a następnie wraca do 1.
   • Wiele kalkulatorów ma klawisz mod. Na końcu tej sekcji pokazano, jak ręcznie obliczyć tę funkcję dla dużych liczb.
3. 3 Poznaj pułapki Małego Twierdzenia Fermata. Wszystkie liczby, dla których nie są spełnione warunki testu, są złożone, ale pozostałe liczby są tylko prawdopodobnie są proste. Jeśli chcesz uniknąć błędnych wyników, wyszukaj n na liście „liczby Carmichaela” (liczby złożone, które spełniają ten test) i „liczby pseudopierwsze Fermata” (liczby te spełniają warunki testu tylko dla niektórych wartości a).
4. 4 Jeśli to wygodne, skorzystaj z testu Millera-Rabina. Chociaż ta metoda jest dość kłopotliwa w przypadku obliczeń ręcznych, jest często stosowana w programach komputerowych. Zapewnia akceptowalną prędkość i mniej błędów niż metoda Fermata. Liczba złożona nie będzie traktowana jako liczba pierwsza, jeśli obliczenia są wykonywane dla więcej niż ¼ wartości a... Jeśli losowo wybierzesz różne wartości a i dla wszystkich z nich test da wynik pozytywny, możemy z dość dużym stopniem pewności założyć, że n jest liczbą pierwszą.
5. 5 W przypadku dużych liczb użyj arytmetyki modularnej. Jeśli nie masz pod ręką kalkulatora modów lub kalkulator nie jest przeznaczony do obsługi tak dużych liczb, użyj właściwości mocy i arytmetyki modularnej, aby ułatwić obliczenia. Poniżej znajduje się przykład dla ${ styl wyświetlania 3 ^ {50}}$ mod 50:
   • Przepisz wyrażenie w wygodniejszej formie: ${ styl wyświetlania (3 ^ {25} * 3 ^ {25})}$ mod 50. Obliczenia ręczne mogą wymagać dalszych uproszczeń.
   • ${ styl wyświetlania (3 ^ {25} * 3 ^ {25})}$ mod 50 = ${ styl wyświetlania (3 ^ {25}}$ mod 50 ${ styl wyświetlania * 3 ^ {25}}$ mod 50) mod 50. Tutaj wzięliśmy pod uwagę właściwość mnożenia modularnego.
   • ${ styl wyświetlania 3 ^ {25}}$ mod 50 = 43.
   • ${ styl wyświetlania (3 ^ {25}}$ mod 50 ${ styl wyświetlania * 3 ^ {25}}$ mod 50) mod 50 = ${ styl wyświetlania (43 * 43)}$ mod 50.
   • ${ styl wyświetlania = 1849}$ mod 50.
   • ${ styl wyświetlania = 49}$.

Część 3 z 3: Korzystanie z chińskiego twierdzenia o reszcie

1. 1 Wybierz dwie liczby. Jedna z liczb musi być złożona, a druga musi być dokładnie tą, którą chcesz przetestować pod kątem prostoty.
   • Liczba1 = 35
   • Liczba2 = 97
2. 2 Wybierz dwie wartości, które są większe od zera i odpowiednio mniejsze niż liczby Numer1 i Numer2. Te wartości nie mogą być takie same.
   • Wartość1 = 1
   • Wartość2 = 2
3. 3 Oblicz MMI (Matematyczne odwrotność mnożenia) dla Liczby1 i Liczby2.
   • Oblicz MMI
     • MMI1 = Numer2 ^ -1 Numer modu1
     • MMI2 = Numer1 ^ -1 Numer modu2
   • Tylko dla liczb pierwszych (to da liczbę dla liczb złożonych, ale nie będzie to jego MMI):
     • MMI1 = (Liczba2 ^ (Liczba 1-2))% Liczba1
     • MMI2 = (Liczba1 ^ (Liczba 2-2))% Liczba2
   • Na przykład:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Utwórz tabelę dla każdego MMI aż do modułów log2:
   • Dla MMI1
     • F (1) = Liczba2% Liczba1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Liczba1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Liczba1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Liczba1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Liczba1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Liczba1 = 1 * 1% 35 = 1
   • Oblicz sparowane liczby 1 - 2
     • 35 -2 = 33 (10001) podstawa 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 mod 35
     • MMI1 = 27
   • Dla MMI2
     • F (1) = Liczba1% Liczba2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Liczba2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Liczba2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Liczba2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Liczba2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Liczba2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Liczba2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Liczba2 = 35 * 35 mod 97 = 61
   • Oblicz sparowaną liczbę 2 - 2
     • 97 - 2 = 95 = (1011111) podstawa 2
     • MMI2 = (((((K (64) * K (16)% 97) * K (8)% 97) * K (4)% 97) * K (2)% 97) * K (1)% 97)
     • MMI2 = (((((35 * 35)% 97) * 61)% 97) * 35% 97) * 61% 97) * 35% 97)
     • MMI2 = 61
5. 5 Oblicz (Wartość1 * Liczba2 * MMI1 + Wartość2 * Liczba1 * MMI2)% (Liczba1 * Liczba2)
   • Odpowiedź = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Odpowiedź = (2619 + 4270)% 3395
   • Odpowiedź = 99
6. 6 Sprawdź, czy Numer 1 nie jest liczbą pierwszą
   • Oblicz (Odpowiedź - Wartość1)% Liczba1
   • 99 – 1 % 35 = 28
   • Ponieważ 28 jest większe od 0, 35 nie jest liczbą pierwszą.
7. 7 Sprawdź, czy liczba 2 jest pierwsza.
   • Oblicz (Odpowiedź - Wartość2)% Liczba2
   • 99 – 2 % 97 = 0
   • Ponieważ 0 to 0, 97 jest najprawdopodobniej liczbą pierwszą.
8. 8 Powtórz kroki od 1 do 7 jeszcze co najmniej dwa razy.
   • Jeśli uzyskasz 0 w kroku 7:
     • Użyj innej liczby1, jeśli Liczba1 nie jest liczbą pierwszą.
     • Użyj innej Numer1, jeśli Numer1 jest liczbą pierwszą. W takim przypadku powinieneś otrzymać 0 w krokach 6 i 7.
     • Używaj różnych Znaczenie1 i Znaczenie2.
   • Jeśli w kroku 7 konsekwentnie otrzymujesz 0, to najprawdopodobniej numer 2 będzie liczbą pierwszą.
   • Kroki od 1 do 7 mogą spowodować błąd, jeśli Numer1 nie jest liczbą pierwszą, a Numer2 jest dzielnikiem Numer1. Opisana metoda działa we wszystkich przypadkach, gdy obie liczby są pierwsze.
   • Powodem, dla którego musisz powtórzyć kroki od 1 do 7, jest to, że w niektórych przypadkach, nawet jeśli Numer 1 i Numer 2 nie są pierwsze, w kroku 7 otrzymasz 0 (dla jednej lub obu liczb). To się rzadko zdarza.Wybierz inną Liczbę1 (złożoną), a jeśli Liczba2 nie jest liczbą pierwszą, to Liczba2 nie będzie równa zeru w kroku 7 (z wyjątkiem przypadku, gdy Liczba1 jest dzielnikiem Liczby2 - tutaj liczby pierwsze zawsze będą równe zeru w kroku 7).

Porady

• Liczby pierwsze od 168 do 1000: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79 , 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211 , 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359 , 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509 , 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673 , 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853 , 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.
• Chociaż testowanie brute force jest żmudnym testem podczas pracy z dużymi liczbami, jest dość wydajne w przypadku małych liczb. Nawet w przypadku dużych liczb zacznij od testowania małych dzielników, a następnie przejdź do bardziej wyrafinowanych metod sprawdzania prostoty liczb (jeśli nie zostaną znalezione małe dzielniki).

Czego potrzebujesz

• Papier, długopis lub komputer