Obsah

• Kroky
• Časť 1 z 3: Testy jednoduchosti
• Časť 2 z 3: Ako fungujú testy jednoduchosti
• Časť 3 z 3: Použitie čínskej vety o zvyšku
• Tipy
• Čo potrebuješ

Prvočísla sú čísla, ktoré sú deliteľné iba samy sebou a 1. Všetky ostatné čísla sa nazývajú zložené čísla. Existuje mnoho spôsobov, ako zistiť, či je číslo prvočíslo, a všetky majú svoje výhody a nevýhody. Na jednej strane sú niektoré metódy veľmi presné, ale sú dosť zložité, ak máte do činenia s veľkým počtom. Na druhej strane existujú oveľa rýchlejšie spôsoby, ale môžu viesť k nesprávnym výsledkom. Voľba vhodnej metódy závisí od toho, s akými veľkými číslami pracujete.

Kroky

Časť 1 z 3: Testy jednoduchosti

Poznámka: vo všetkých vzorcoch n označuje číslo, ktoré sa má skontrolovať.

1. 1 Výpočet deliteľov. Stačí rozdeliť n na všetky prvočísla od 2 do zaokrúhlenej hodnoty (${ displaystyle { sqrt {n}}}$).
2. 2 Fermatova malá veta. Varovanie: niekedy test falošne identifikuje zložené čísla ako prvočísla, dokonca aj pre všetky hodnoty a.
   • Vyberme celé číslo ataké, že 2 ≤ a ≤ n - 1.
   • Ak a (mod n) = a (mod n), potom je číslo pravdepodobne prvočíslo. Ak rovnosť nie je splnená, číslo n je zložené.
   • Viaceré hodnoty skontrolujte v danej rovnosti aaby sa zvýšila pravdepodobnosť, že testovaný počet je skutočne prvočíselný.
3. 3 Miller-Rabinov test. Varovanie: niekedy, aj keď len zriedka, pri viacerých hodnotách a, test falošne identifikuje zložené čísla ako prvočísla.
   • Nájdite veličiny s a d také, aby ${ Displaystyle n-1 = 2 ^ {s} * d}$.
   • Vyberte celé číslo a v rozsahu 2 ≤ a ≤ n - 1.
   • Ak a = +1 (mod n) alebo -1 (mod n), potom n je pravdepodobne prvočíslo. V takom prípade prejdite na výsledok testu. Ak rovnosť neplatí, prejdite na ďalší krok.
   • Svoju odpoveď umocnite${ displaystyle a ^ {2d}}$). Ak dostanete -1 (mod n), potom n je pravdepodobne prvočíslo. V takom prípade prejdite na výsledok testu. Ak rovnosť zlyhá, zopakujte (${ displaystyle a ^ {4d}}$ a tak ďalej) až ${ Displaystyle a ^ {2 ^ {s-1} d}}$.
   • Ak v určitom kroku po vygenerovaní čísla iné ako ${ Displaystyle pm 1}$ (mod n), dostali ste +1 (mod n), takže n je zložené číslo. Ak ${ Displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), potom n nie je prvočíslo.
   • Výsledok testu: ak n prejde testom, zopakujte ho pre ďalšie hodnoty ana zvýšenie dôvery.

Časť 2 z 3: Ako fungujú testy jednoduchosti

1. 1 Výpočet deliteľov. Podľa definície číslo n je jednoduchý iba vtedy, ak nie je deliteľný 2 a inými celými číslami okrem 1 a seba. Vyššie uvedený vzorec vám umožňuje odstrániť zbytočné kroky a ušetriť čas: napríklad po kontrole, či je číslo deliteľné 3, nie je potrebné kontrolovať, či je číslo deliteľné 9.
   • Funkcia floor (x) zaokrúhľuje x na najbližšie celé číslo menšie alebo rovné x.
2. 2 Získajte informácie o modulárnej aritmetike. Operácia „x mod y“ (mod je skratka z latinského slova „modulo“, to znamená „modul“) znamená „delíme x o y a nájdeme zvyšok“. Inými slovami, v modulárnej aritmetike po dosiahnutí určitej hodnoty, ktorá sa nazýva modul, sa čísla opäť „otočia“ na nulu. Hodiny napríklad odpočítavajú s modulom 12: zobrazujú 10, 11 a 12 hodín a potom sa vrátia na 1.
   • Mnoho kalkulačiek má kláves mod. Koniec tejto časti ukazuje, ako manuálne vypočítať túto funkciu pre veľké čísla.
3. 3 Získajte informácie o úskaliach Fermatovej malej vety. Všetky čísla, pre ktoré nie sú splnené testovacie podmienky, sú zložené, ale ostatné čísla sú iba pravdepodobne sú jednoduché. Ak sa chcete vyhnúť nesprávnym výsledkom, hľadajte n v zozname „čísla Carmichael“ (zložené čísla, ktoré vyhovujú tomuto testu) a „pseudoprime čísla Fermat“ (tieto čísla spĺňajú testovacie podmienky iba pre niektoré hodnoty a).
4. 4 Ak je to vhodné, použite Miller-Rabinov test. Aj keď je táto metóda pre manuálne výpočty dosť ťažkopádna, často sa používa v počítačových programoch. Poskytuje prijateľnú rýchlosť a menej chýb ako Fermatova metóda. Zložené číslo nebude brané ako prvočíslo, ak sa výpočty vykonávajú pre viac ako ¼ hodnôt a... Ak náhodne vyberiete rôzne hodnoty a a pre všetky testy prinesú pozitívny výsledok, môžeme to s pomerne vysokou mierou spoľahlivosti predpokladať n je prvočíslo.
5. 5 Pri veľkých počtoch použite modulárnu aritmetiku. Ak nemáte k dispozícii kalkulačku modov alebo kalkulačka nie je navrhnutá tak, aby zvládala také veľké počty, na uľahčenie výpočtov použite výkonové vlastnosti a modulárnu aritmetiku. Nasleduje príklad pre ${ displaystyle 3 ^ {50}}$ režim 50:
   • Prepíšte výraz pohodlnejšou formou: ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ režim 50. Ručné výpočty môžu vyžadovať ďalšie zjednodušenia.
   • ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ režim 50 = ${ displaystyle (3 ^ {25}}$ režim 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50. Tu sme vzali do úvahy vlastnosť modulárneho násobenia.
   • ${ displaystyle 3 ^ {25}}$ režim 50 = 43.
   • ${ displaystyle (3 ^ {25}}$ režim 50 ${ displaystyle * 3 ^ {25}}$ režim 50) režim 50 = ${ displaystyle (43 * 43)}$ režim 50.
   • ${ displaystyle = 1849}$ režim 50.
   • ${ displaystyle = 49}$.

Časť 3 z 3: Použitie čínskej vety o zvyšku

1. 1 Vyberte dve čísla. Jedno z čísel musí byť zložené a druhé musí byť presne to, ktoré chcete kvôli jednoduchosti otestovať.
   • Číslo1 = 35
   • Číslo2 = 97
2. 2 Vyberte dve hodnoty, ktoré sú väčšie ako nula, respektíve menšie ako čísla Number1 a Number2. Tieto hodnoty nesmú byť rovnaké.
   • Hodnota1 = 1
   • Hodnota2 = 2
3. 3 Vypočítajte MMI (matematický multiplikatívny inverzný) pre číslo 1 a číslo 2.
   • Vypočítajte MMI
     • MMI1 = Number2 ^ -1 Mod Number1
     • MMI2 = Number1 ^ -1 Mod Number2
   • Len pre prvočísla (toto dá číslo pre zložené čísla, ale nebude to jeho MMI):
     • MMI1 = (Číslo2 ^ (Číslo1-2))% Číslo1
     • MMI2 = (Číslo1 ^ (Číslo2-2))% Číslo2
   • Napríklad:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Vytvorte tabuľku pre každé MMI až po moduly log2:
   • Pre MMI1
     • F (1) = Číslo2% Číslo1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Číslo1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Číslo1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Číslo1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Číslo1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Číslo1 = 1 * 1% 35 = 1
   • Vypočítajte párové čísla 1 - 2
     • 35 -2 = 33 (10001) základňa 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 režim 35
     • MMI1 = 27
   • Pre MMI2
     • F (1) = Číslo1% Číslo2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Číslo2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Číslo2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Číslo2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Číslo2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Číslo2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Číslo2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Číslo2 = 35 * 35 mod 97 = 61
   • Vypočítajte párové číslo 2 - 2
     • 97 - 2 = 95 = (1011111) základňa 2
     • MMI2 = ((((((((64 (64)) * * (16)% 97) * F (8)% 97) * F (4)% 97) * F (2)% 97) * F (1)% 97)
     • MMI2 = ((((((((35 * 35)% 97) * 61)% 97) * 35% 97) * 61% 97) * 35% 97)
     • MMI2 = 61
5. 5 Vypočítať (hodnota1 * číslo2 * MMI1 + hodnota2 * číslo1 * MMI2)% (číslo1 * číslo2)
   • Odpoveď = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Odpoveď = (2619 + 4270)% 3395
   • Odpoveď = 99
6. 6 Skontrolujte, či číslo 1 nie je prvočíslo
   • Vypočítajte (odpoveď - hodnota1)% číslo1
   • 99 – 1 % 35 = 28
   • Pretože 28 je väčšie ako 0, 35 nie je prvočíslo.
7. 7 Skontrolujte, či je Number2 prvočíslo.
   • Vypočítajte (odpoveď - hodnota2)% Number2
   • 99 – 2 % 97 = 0
   • Pretože 0 je 0, 97 je s najväčšou pravdepodobnosťou prvočíslo.
8. 8 Kroky 1 až 7 zopakujte ešte najmenej dvakrát.
   • Ak v kroku 7 získate 0:
     • Ak číslo 1 nie je prvočíslo, použite iné Číslo1.
     • Ak je číslo 1 prvočíslo, použite iné Číslo1. V takom prípade by ste v krokoch 6 a 7 mali dostať 0.
     • Použite iný význam 1 a význam 2.
   • Ak v kroku 7 dôsledne dostanete 0, potom bude číslo 2 pravdepodobne prvoradé.
   • Kroky 1 až 7 môžu mať za následok chybu, ak Číslo1 nie je prvočíslo a Číslo2 je deliteľom čísla1. Popísaná metóda funguje vo všetkých prípadoch, keď sú obe čísla prvočíselné.
   • Kroky 1 až 7 musíte zopakovať preto, že v niektorých prípadoch, aj keď číslo 1 a číslo 2 nie sú prvočíselné, v kroku 7 dostanete 0 (pre jedno alebo obe čísla). To sa stáva málokedy.Vyberte iné číslo1 (zložené) a ak číslo2 nie je prvočíslo, potom sa číslo 2 v kroku 7 nebude rovnať nule (s výnimkou prípadu, keď je číslo 1 deliteľom čísla 2 - prvočísla sa v kroku 7 vždy rovnajú nule).

Tipy

• Prvočísla 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.
• Napriek tomu, že testovanie hrubou silou je únavný test pri práci s veľkými číslami, je pri malých číslach celkom účinný. Aj v prípade veľkých čísel začnite testovaním malých deliteľov a potom prejdite na sofistikovanejšie metódy kontroly jednoduchosti čísel (ak sa malé delitele nenachádzajú).

Čo potrebuješ

• Papier, pero alebo počítač