Ako skontrolovať, či je číslo prvočíslo?
Ak chcete skontrolovať, či je číslo prvočíslo, vydelte ho každým prvočíslom začínajúcim 2 a končiacim vtedy, ak je druhá mocnina prvočísla väčšia ako číslo, proti ktorému kontrolujete. Ak nie je rovnomerne delené žiadnym celým číslom okrem 1 alebo samotného, je číslo prvočíslo. Ak sa chcete dozvedieť, ako urobiť modulárnu aritmetiku na testovanie veľkého počtu, pokračujte v čítaní článku!
Ak chcete skontrolovať, či je číslo prvočíslo, vydelte ho každým prvočíslom začínajúcim 2 a končiacim vtedy, ak je druhá mocnina prvočísla väčšia ako číslo, proti ktorému kontrolujete.
Prvočísla sú deliteľné iba samy osebe a 1. Všetky ostatné čísla sa nazývajú zložené čísla. Existuje mnoho spôsobov, ako otestovať, či je číslo prvočíslo, ale existuje kompromis. Na jednej strane existujú testy, ktoré sú perfektné, ale pri veľkom počte extrémne pomalé. Na druhej strane existujú testy, ktoré sú oveľa rýchlejšie, ale môžu poskytnúť falošné výsledky. Tu je niekoľko možností na výber v závislosti od toho, aké veľké číslo testujete.
Časť 1 z 3: Primárne testy
Prvočíslo sa skončí číslom 1, 3, 7 alebo 9, ale nie všetky tieto čísla sú prvočísla.
Poznámka: Vo všetkých vzorcoch je n číslo, ktoré sa testuje na primalitu.
- 1Skúšobný test rozdelenia. Rozdeľte n každým prvočíslom od 2 do poschodia ( n {\ Displaystyle {\ sqrt {n}}} ).
- 2Fermatova malá veta. Upozornenie: Falošné poplachy sú možné, dokonca aj pre všetky hodnoty a.
- Vyberte celočíselnú hodnotu a tak, že 2 ≤ a ≤ n - 1.
- Ak a n (mod n) = a (mod n), potom n je pravdepodobne prvočíslo. Ak to nie je pravda, n nie je prvočíslo.
- Opakujte s rôznymi hodnotami a, aby ste zvýšili dôveru v originalitu
- 3Miller-Rabinov test. Varovanie: Falošne pozitívne sú možné, ale len zriedka pre viac hodnôt a.
- Nájdite hodnoty s a d také, aby n − 1 = 2s ∗ d {\ Displaystyle n-1 = 2^{s}*d} .
- Vyberte celočíselnú hodnotu a tak, že 2 ≤ a ≤ n - 1.
- Ak a d = +1 (mod n) alebo -1 (mod n), potom n je pravdepodobne prvočíslo. Preskočiť na výsledok testu. V opačnom prípade prejdite na ďalší krok.
- Svoju odpoveď dajte na druhú stranu ( a2d {\ displaystyle a^{2d}}). Ak sa to rovná -1 (mod n), potom n je pravdepodobne prvočíslo. Preskočiť na výsledok testu. V opačnom prípade opakujte ( a4d {\ Displaystyle a^{4d}} atď.), Kým a2s − 1d {\ displaystyle a^{2^{s-1} d}} .
- Ak niekedy zadáte číslo, ktoré nie je ± 1 {\ Displaystyle \ pm 1} (mod n) a skončí na +1 (mod n), potom n nie je prvočíslo. Ak a2s − 1d ≠ ± 1 {\ Displaystyle a^{2^{s-1} d} \ neq \ pm 1} (mod n), potom n nie je prvočíslo.
- Výsledok testu: Ak n prejde testom, opakujte s rôznymi hodnotami a, aby ste zvýšili spoľahlivosť.
Ak nie je rovnomerne delené žiadnym celým číslom okrem 1 alebo samotného, je číslo prvočíslo.
Časť 2 z 3: Pochopenie primárneho testovania
- 1Pochopte metódu skúšobného rozdelenia. Podľa definície primality je n prvočíslo iba vtedy, ak ho nemožno rovnomerne rozdeliť na celé čísla 2 alebo väčšie. Uvedený vzorec šetrí čas odstránením nepotrebných testov (napr. Po testovaní 3 nie je potrebné testovať 9).
- Podlaha (x) zaokrúhľuje x na najbližšie celé číslo ≤ x.
- 2Pochopte modulárnu aritmetiku. Operácia „x mod y“ (skratka z „modulo“) znamená „delíme x o y a nájdeme zvyšok“. Inými slovami, v modulárnej aritmetike sa čísla „pohybujú“ späť na nulu po dosiahnutí určitej hodnoty, nazývanej modul. Hodiny sa počítajú v module 12: prejdú od 10 do 11 do 12 a potom sa vrátia späť na 1.
- Mnoho kalkulačiek má tlačidlo mod, ale pozrite sa na koniec tejto časti, ako to vyriešiť ručne pre veľké čísla.
- 3Poznáte úskalia Fermatovej malej vety. Všetky čísla, ktoré v tomto teste neuspejú, sú zložené (primárne), ale bohužiaľ čísla, ktoré týmto testom prešli, sú iba pravdepodobné prvočísla. Ak si chcete byť istí, že sa vyhnete falošným pozitívam, vyhľadajte n v zozname „Carmichaelských čísel“ (ktoré týmto testom prechádzajú vždy) a „Fermat pseudoprimes“ (ktoré týmto testom prechádzajú iba pre niektoré hodnoty a).
- 4Použite test Miller-Rabin, kedykoľvek je to praktické. Aj keď je manuálne namáhavé vykonávať tento test, bežne sa používa v softvéri. To sa dá vykonať praktickou rýchlosťou a dáva to menej falošných poplachov ako Fermatova metóda. Zložené číslo nikdy neposkytne falošne pozitívny výsledok pre viac ako 0,25 hodnôt a. Ak náhodne vyberiete niekoľko hodnôt a a všetky prejdú týmto testom, môžete si byť celkom istí, že n je prvočíslo.
- 5Vykonajte modulárnu aritmetiku pre veľké počty. Ak nemáte prístup k kalkulačke s funkciou mod alebo ak vaša kalkulačka nedokáže zobraziť čísla tak vysoko, uľahčite si to pomocou vlastností exponentov a modulárnej aritmetiky. Tu je príklad pre 350 {\ displaystyle 3^{50}} mod 50:
- Prepíšte výraz ovládateľnejšími exponentmi: ( 50. (325 ∗ 325) {\ displaystyle (3^{25}*3^{25})} mod 50. (Pri ručnom výpočte ho možno budete musieť ďalej rozobrať).
- (325 ∗ 325) {\ displaystyle (3^{25} *3^{25})} mod 50 = (325 {\ displaystyle (3^{25}} mod 50 ∗ 325 {\ displaystyle *3^{25} } mod 50) mod 50. (Toto je vlastnosť modulárneho násobenia.)
- 325 {\ Displaystyle 3^{25}} mod 50 = 43.
- (325 {\ displaystyle (3^{25}} mod 50 ∗ 325 {\ displaystyle *3^{25}} mod 50) mod 50 = (43 ∗ 43) {\ displaystyle (43 *43)} mod 50
- = 1849 {\ displaystyle = 1849} mod 50
- = 49 {\ displaystyle = 49}
Časť 3 z 3: Test čínskej zvyškovej vety
- 1Vyberte dve čísla. Jedno z čísel nie je prvočíslo a druhé číslo je číslo, ktoré je potrebné otestovať na prvenstvo.
- „Prime1“ = 35
- Prime2 = 97
- 2Vyberte dva datové body, ktoré sú väčšie ako nula a menšie ako prime1 a prime2, s rešpektom. Nemôžu sa navzájom rovnať.
- Údaje 1 = 1
- Údaje2 = 2
- 3Vypočítajte MMI (matematická multiplikácia inverzná) pre prime1 a prime2
- Vypočítajte MMI
- MMI1 = Prime2 ^ -1 Mod Prime1
- MMI2 = Prime1 ^ -1 Mod Prime2
- Len pre prvočísla (poskytne číslo pre iné ako prvočísla, ale nebude to jeho MMI):
- MMI1 = (Prime2 ^ (Prime1-2))% Prime1
- MMI2 = (Prime1 ^ (Prime2-2))% Prime2
- napr
- MMI1 = (97 ^ 33)% 35
- MMI2 = (35 ^ 95)% 97
- Vypočítajte MMI
- 4Vytvorte binárnu tabuľku pre každé MMI až do log2 modulu
- Pre MMI1
- F (1) = Prime2% Prime1 = 97% 35 = 27
- F (2) = F (1) * F (1)% Prime1 = 27 * 27% 35 = 29
- F (4) = F (2) * F (2)% Prime1 = 29 * 29% 35 = 1
- F (8) = F (4) * F (4)% Prime1 = 1 * 1% 35 = 1
- F (16) = F (8) * F (8)% Prime1 = 1 * 1% 35 = 1
- F (32) = F (16) * F (16)% Prime1 = 1 * 1% 35 = 1
- Vypočítajte binárku Prime1 - 2
- 35 -2 = 33 (10001) základňa 2
- MMI1 = F (33) = F (32) * F (1) mod 35
- MMI1 = F (33) = 1 * 27 Mod 35
- MMI1 = 27
- Pre MMI2
- F (1) = Prime1% Prime2 = 35% 97 = 35
- F (2) = F (1) * F (1)% Prime2 = 35 * 35 mod 97 = 61
- F (4) = F (2) * F (2)% Prime2 = 61 * 61 mod 97 = 35
- F (8) = F (4) * F (4)% Prime2 = 35 * 35 mod 97 = 61
- F (16) = F (8) * F (8)% Prime2 = 61 * 61 mod 97 = 35
- F (32) = F (16) * F (16)% Prime2 = 35 * 35 mod 97 = 61
- F (64) = F (32) * F (32)% Prime2 = 61 * 61 mod 97 = 35
- F (128) = F (64) * F (64)% Prime2 = 35 * 35 mod 97 = 61
- Vypočítajte binárku Prime2 - 2
- 97 - 2 = 95 = (1011111) základňa 2
- MMI2 = (((((((64 (64) * F (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
- Pre MMI1
- 5Vypočítajte (data1 * prime2 * mmi1 + data2 * prime1 * mmi2)% (prime1 * prime2)
- Odpoveď = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
- Odpoveď = (2619 + 4270)% 3395
- Odpoveď = 99
- 6Overte, či „prime1“ nie je prvočíslo
- Vypočítajte (odpoveď - údaje1)% Prime1
- 99 -1% 35 = 28
- Pretože 28 je väčšie ako 0, 35 nie je prvočíslo
- 7Skontrolujte, či je prime2 prime
- Vypočítajte (odpoveď - údaje2)% Prime2
- 99 - 2% 97 = 0
- Pretože 0 sa rovná 0, 97 je potenciálne prvočíslo
- 8Kroky 1 až 7 zopakujte ešte najmenej dvakrát.
- Ak je krok 7 0:
- Použite iný „prime1“, kde prime1 nie je prime
- Použite iný prvočíslo 1, kde prvočíslo 1 je skutočné prvočíslo. V tomto prípade by sa kroky 6 a 7 mali rovnať 0.
- Pre údaje1 a údaje2 použite rôzne dátové body.
- Ak je krok 7 vždy 0, je extrémne vysoká pravdepodobnosť, že prime2 je prvočíslo.
- Kroky 1 až 7 sú známe ako neúspešné v určitých prípadoch, keď je prvé číslo iné ako prvočíslo a druhé prvočíslo je faktorom iného ako prvočísla „prvočíslo 1“. To funguje vo všetkých prípadoch, kde obe čísla sú pripraviť.
- Dôvod, prečo sa kroky 1 až 7 opakujú, je ten, že existuje niekoľko scenárov, kde, aj keď prime1 nie je prime a prime2 nie je prime, krok 7 stále funguje ako nula pre jedno alebo obe čísla. Tieto okolnosti sú zriedkavé. Ak zmeníte prime1 na iné ako prvočíslo, v prípade, že prime2 nie je prvočíslo, prime2 sa v kroku 7 rýchlo nebude rovnať nule. S výnimkou prípadu, kde je „prime1“ faktorom prime2, sa v kroku 7 prvočísla vždy rovnajú nule..
- Ak je krok 7 0:
Ak niekedy zadáte číslo, ktoré nie je (mod n), a skončí sa +1 (mod n), potom n nebude prvočíslo.
- 168 prvočísel do 1000 je: 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
- Aj keď je skúšobné delenie pomalšie ako sofistikovanejšie metódy pre veľké počty, pre malé čísla je stále celkom efektívne. Dokonca aj pre testovanie primality veľkého počtu nie je neobvyklé najskôr skontrolovať malé faktory a potom prejsť na pokročilejšiu metódu, keď sa nenájdu žiadne malé faktory.
- Cvičenie nástrojov, ako je papier a pero alebo počítač
Prečítajte si tiež: Ako vypočítať čas zdvojnásobenia?
Otázky a odpovede
- Sú 57, 87, 89 a 91 prvočísla?57 je deliteľný 3 a 19 okrem 1 a sám o sebe, takže nie je prvočíselný. 87 je tiež deliteľný 3, takže nie je prvočíslo. 89 je prvočíslo, pretože je deliteľné iba 1 a samým sebou. 91 je deliteľné 7, takže nie je prvočíslo.
- Prečo pri testovaní prvočísel používam nepárne čísla?Pretože okrem 2 nemôžu existovať ani párne prvočísla (boli by deliteľné 2).
- Majú prvočísla vzor?Medzi prvočíslami bohužiaľ neexistujú žiadne zrejmé ani užitočné vzorce.
- Existuje nejaký rýchly spôsob, ako na prvý pohľad dobre odhadnúť, či je číslo prvočíslo alebo nie?Nie, ani na prvý pohľad. Najbližšie sa môžete dozvedieť, že prvočíslo je vždy nepárne, ale nikdy nekončí číslom 5. Prvočíslo sa skončí číslom 1, 3, 7 alebo 9, ale nie všetky tieto čísla sú prvočísla.
- Je pravda, že keďže 43 x 1069 = 45967, nemôže to byť prvočíslo?Áno. Prvočísla nemôžu byť súčinom akýchkoľvek dvoch iných čísel ako 1 a samotného čísla. 45967 teda nie je prvočíslo.
