Jak zjistit, zda je číslo prvočíslem

Prvočísla lze dělit pouze jimi samými a číslem 1. Všechna ostatní čísla nazývám čísly složenými. Způsobů, jak otestovat, zda je číslo prvočíslem, existuje spousta, vždy se však jedná o určitý kompromis. Jedny testy jsou dokonale přesné, avšak v případě velkých čísel extrémně pomalé, druhé jsou pak mnohem rychlejší, mohou však dávat nesprávné výsledky. Níže najdete nabídku z několika možností testování, přičemž výběr té správné bude vždy záležet na velikosti zkoumaného čísla.

Část 1

Část 1 ze 3:

Testování prvočíselnosti

Stáhnout PDF

Pozn: Ve všech následujících vzorcích označuje n číslo, u kterého testujeme, zda je prvočíslem.

1
Zkouška postupným dělením. Dělte n každým prvočíslem od 2 až po horní mez( ${\sqrt {n}}$ ).
2
Malá Fermatova věta. Pozor: může dávat falešné pozitivní výsledky, dokonce i pro všechny hodnoty „a“.
- Zvolte si celočíselnou hodnotu a, například 2 ≤ a ≤ n - 1.
- Pokud platí aⁿ (mod n) = a (mod n), pak je n nejspíše prvočíslo. Pokud toto neplatí, n prvočíslem není.
- Opakujte s jinou hodnotou a, abyste zvýšili jistotu platnosti výsledku.
3
Millerův-Rabinův test. Pozor: může dávat falešně pozitivní výsledky, pro více hodnot „a“ však méně pravděpodobně.
- Zvolte si hodnoty s a d takové, aby platilo $n-1=2^{s}*d$ .
- Zvolte si pro a celočíselnou hodnotu, například 2 ≤ a ≤ n - 1.
- Pokud platí: a^d = +1 (mod n) nebo -1 (mod n), pak je n pravděpodobně prvočíslem. Přeskočte na výsledek testu. Pokud toto neplatí, pokračujte na další krok.
- Umocněte výsledek ( $a^{2d}$ ). Pokud se rovná +1 (mod n) nebo -1 (mod n), přeskočte na výsledek testu. Pokud ne, opakujte ( $a^{4d}$ atd.) až do $a^{2^{s-1}d}$ .
- Výsledek testu: Pokud n testem projde, opakujte test pro jinou hodnotu a, abyste zvýšili jistotu platnosti výsledku.
Reklama

Část 2

Část 2 ze 3:

Princip testování prvočíselnosti

Stáhnout PDF

1
Pochopte metodu postupného dělení. Z definice prvočíselnosti vyplývá, že je n prvočíslem pouze tehdy, pokud jej nelze beze zbytku dělit celými čísly většími než nebo rovnými 2. Daný vzorec pak šetří čas tím, že zamezí provádění zbytečných testů (například po testování dělení trojkou již není třeba testovat 9).
- Horní mez(x) zaokrouhlí číslo x na nejbližší celé číslo ≥ x.
2
Porozumějte modulární aritmetice. Operace "x mod y" (mod je zkratka pro "modulo") znamená: "vyděl x číslem y a najdi zbytek."^{[1]
X
Zroj výzkumu} Jinými slovy, v modulární aritmetice se čísla po dosažení určité hodnoty zvané modulo "vrátí zpět k nule ". Hodiny počítají do modulo 12: jdou od 10 k 11 a 12, a poté se vrátí zpět na 1.
- Řada kalkulaček má tlačítko mod, na konci této sekce však najdete návod, jak modul spočítat ručně i u velkých čísel.
3
Vezměte v potaz záludnosti Malé Fermatovy věty. Všechna čísla, která tímto testem neprojdou, jsou složená (tedy nejsou prvočísly), avšak čísla, která jím projdou, jsou pouze pravděpodobněprvočísly. Pokud se chcete s jistotou vyvarovat falešně pozitivních výsledků, podívejte se, zda se n nachází na seznamu "Carmichaelových čísel" (která tímto testem vždy projdou) a "Fermatových prvočísel" (které testem projdou jen při určitých hodnotách a).^{[2]
X
Zroj výzkumu}
4
Je-li to vhodné, použijte Millerův-Rabinův test. Ačkoliv je takovéto ruční testování zdlouhavé, často se tento test provádí softwarově. Lze jej totiž vykonat rozumnou rychlostí a dává méně falešně pozitivních výsledků než Fermatova metoda. ^{[3]
X
Zroj výzkumu} Složená čísla nikdy nedávají falešně pozitivní výsledek pro více než ¼ hodnot a.^{[4]
X
Zroj výzkumu} Pokud si tedy zvolíte několik náhodných hodnot a a všechny testem projdou, můžete si být vcelku jistí, že je n prvočíslem.
5
U velkých čísel provádějte modulární operace. Pokud nemáte kalkulačku s funkcí mod, nebo pokud vám kalkulačka takto vysoká čísla nezobrazí, můžete si operaci zjednodušit exponenciálním zápisem a modulárními počty. ^{[5]
X
Zroj výzkumu} Zde jako příklad uvádíme výpočet $3^{50}$ $3^{{50}}$ mod 50:
- Přepište si výraz do tvaru se snáze zvládnutelnými exponenty: $(3^{25}*3^{25})$ mod 50. (Pokud budete počítat ručně, můžete si čísla rozložit ještě více).
- $(3^{25}*3^{25})$ mod 50 = $(3^{25}$ mod 50 $*3^{25}$ mod 50) mod 50. (To je vlastnost modulárního násobení.)
- $3^{25}$ mod 50 = 43.
- $(3^{25}$ mod 50 $*3^{25}$ mod 50) mod 50 = $(43*43)$ mod 50
- $=1849$ mod 50
- $=49$
Reklama

Část 3

Část 3 ze 3:

Test s pomocí Čínské věty o zbytcích

Stáhnout PDF

1
Zvolte si dvě čísla. Jedno z nich není prvočíslem a to druhé chcete na prvočíselnost testovat.
- "Prime1" = 35
- Prime2 = 97
2
Zvolte si dva prvky z číselné řady (Data1 a Data2), které jsou větší než nula a menší než Prime1, respektive Prime2. Tyto dva prvky se nesmí vzájemně rovnat.
- Data1 = 1
- Data2 = 2
3
Spočtěte si převrácenou hodnotu čísel Prime1 a Prime2
- Vypočtěte převrácenou hodnotu (MMI)
  - MMI1 = Prime2 ^ -1 Mod Prime1
  - MMI2 = Prime1 ^ -1 Mod Prime2
- Platí pouze pro prvočísla (u složených čísel takto také dostanete nějaký výsledek, ne však hledanou inverzní hodnotu):
  - MMI1 = (Prime2 ^ (Prime1-2)) % Prime1
  - MMI2 = (Prime1 ^ (Prime2-2)) % Prime2
- např.
  - MMI1 = (97 ^ 33) % 35
  - MMI2 = (35 ^ 95) % 97
4
Vytvořte si binární tabulku (ve dvojkové soustavě) pro každé MMI až po Log2 z modulo
- Pro MMI1 tedy
  - 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čtěte binární hodnoty Prime1 - 2
  - 35 -2 = 33 (10001) v soustavě 2
  - MMI1 = F(33) = F(32) * F(1) mod 35
  - MMI1 = F(33) = 1 * 27 Mod 35
  - MMI1 = 27
- Pro 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čtěte binární hodnoty Prime2 - 2
  - 97 - 2 = 95 = (1011111) base 2
  - MMI2 = (((((F(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
5
Spočtěte (Data1 * Prime2 * MMI1 + Data2 * Prime1 * MMI2) % (Prime1 * Prime2)
- Výsledek = (1 * 97 * 27 + 2 * 35 * 61) % (97 * 35)
- Výsledek = (2619 + 4270) % 3395
- Výsledek = 99
6
Ověřte, že "Prime1" není prvočíslem
- Spočtěte (Výsledek - Data1) % Prime1
- 99 -1 % 35 = 28
- Jelikož je 28 větší než 0, 35 není prvočíslem
7
Ověřte, zda je prvočíslem Prime2
- Spočtěte (Výsledek - Data2) % Prime2
- 99 - 2 % 97 = 0
- Jelikož se 0 rovná 0, 97 je potenciálním prvočíslem
8
Kroky 1 až 7 ještě nejméně dvakrát zopakujte.
- Pokud je výsledkem 7. kroku 0:
  - Použijte jinou hodnotu "prime1" tak, aby prime1 nebylo prvočíslem.
  - Použijte jinou hodnotu prime1 tak, aby prime1 prvočíslem bylo. Potom by kroky 6 i 7 měly vyjít 0.
  - Pro proměnné data1 a data2 zvolte dvě odlišné hodnoty z řady.
- Pokud se krok 7 pokaždé rovná 0, je číslo prime2 s velmi vysokou prvočíslem.
- Kroky 1 až 7 tradičně selhávají v určitých případech, kdy první číslo (prime1) není prvočíslem a druhé číslo (prime2) je jeho dělitelem. Postup však vždy, když jsou obě čísla prvočísly.
- Důvodem k opakování kroků 1 až 7 je to, že v několika určitých případech i přesto, že ani prime1, ani prime2 nejsou prvočísly, může v kroku 7 vyjít pro jedno nebo obě čísla 0. Okolnosti takových případu jsou však vzácné. Změnou hodnoty prime1 na jiné složené číslo dosáhnete toho, že pokud není prime2 prvočíslem, bude se od nuly v kroku 7 výrazně lišit. Až na případy, kdy je "prime1" dělitelem prime2, vyjde vždy pro prvočíslo v kroku 7 výsledek 0.
Reklama

Tipy

168 prvočísel do 1000 vypadá takto: 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 ^{[6]
X
Zroj výzkumu}
Ačkoliv je zkouška dělením u velkých čísel pomalejší než sofistikovanější metody, stále ji lze vcelku efektivně využívat u malých čísel. A i při testování prvočíselnosti velkých čísel není vzácností, že se nejprve otestují malé dělitele, a pak (pokud se žádné nenaleznou) se teprve přejde ke složitějším metodám.

Reklama