Algoritmus na extremne prvocisla v pythone

Úvod

V tomto článku bude zverejnený efektívny algoritmus na testovanie extrémne veľkých čísiel (autor: Robopol). Algoritmus otestuje číslo a vyhodnotí, či sa jedná o zložené číslo alebo prvočíslo. Tento diel je zároveň update článku z minulosti - Program na prvočísla. Algoritmus je naprogramovaný v programovacom jazyku Python. Pre bližšie informácie o Pythone (inštalácia, spustenie..) navštívte stránku - Matematika v Pythone, resp. informácie sú dostupné online na internete.
V algoritme sa využívajú aj vzťahy (Robopol theorem):

Robopol_theoremjpg


Verzie algoritmu, zdrojový kód

prime_number_pyjpg
Obr. 1 Ukážka kódu programu, zdroj: vlastný obrázok.
Verzia č.1:
download súboru v Pythone: prime_numbers.py
Pozrieť kód vo formáte .txt: prime_numbers.txt
Popis: Algoritmus obsahuje klasické vyhľadávanie prvočísiel + špeciálny algoritmus na extrémne veľké čísla.
Verzia č.2:
download súboru v Pythone: pm1.py
Pozrieť kód vo formáte .txt: pm1.txt
Popis: Špeciálny algoritmus na extrémne veľké čísla. Tento algoritmus je o niečo rýchlejší ako verzia č.1, pretože nehľadá konkrétnych deliteľov.
Spustenie kódu:
Pre spustenie konzolového programu je potrebné si nainštalovať Python. Následne po inštalácii spustíme interpretéra s názvom  IDLE(..) , ktorý je nainštalovaný v ponuke štart. Otvoríme Python súbor(koncovka ". py"):
otvorenie_prime_numbersjpg
Obr.2 Otvorenie kódu v IDLE, zdroj: vlastný obrázok.
Následne spustíme kód v ponuke Run, Run module. Následne sa spustí kód kde zadávame čísla. Veľké čísla si môžete kopírovať a vkladať, viď. nižšie na príklade. Ukončenie programu je zadaním 0 a potvrdením cez enter.
Online spustenie programu:
Kód si môžete spustiť aj online na prehliadači napr. na stránke: https://www.onlinegdb.com/online_python_interpreter
Následne si skopírujte celý kód programu z textového súboru, viď. verzia vyššie. Potom už len spustíme program cez Run. Pozor však na veľkosť čísla, tento server ma limit a pri veľkých číslach vyhodí zlý výsledok.
online_interprete_pythonjpg
Obr.3 Online spustenie programu, zdroj: vlastný obrázok.

Príklady extrémnych prvočísiel

Vyskúšame teraz ako rýchly je tento algoritmus na bežnom pc s troška lepšou grafickou kartou, priemerným procesom a 16 GB RAM:
Pre zaujímavosť nech sa trocha zapotí si vyberieme Mersennové prvočísla (https://sk.wikipedia.org/wiki/Mersennovo_prvo%C4%8D%C3%ADslo)
vyberieme si napr. číslo na 25. pozícií s 6533 ciframi. Najskôr však potrebujeme mať celý číselný tvar. Otvoríme si teda príkazový riadok cmd, napíšeme Python, čím spustíme Python v príkazovom riadku Windowsu. vypočítame hodnotu 2ˆ21701-1:
mesrenn_prime25jpg
Obr.4 Výpočet 2 ˆ21701-1 v Pythone, zdroj: vlastný obrázok.
Následne si skopírujeme toto číslo do otvoreného programu pre zadanie čísiel.

Skuska_2jpg
Obr. 5 Výsledok v programe, zdroj: vlastný obrázok.
Algoritmus zhruba za 45 sec vyhodí výsledok, že ide o prvočíslo, resp. pseudoprvočíslo. To je veľmi dobrý výsledok v rýchlosti.
Pri skúšaní čísiel môžeme meniť parametre v programe, teda konštanty:
1. Môžeme meniť základ Fermatovej vety, premenná "a", napr. chceme posúdiť výsledok aj pre a=3,4,5,7..atď.
2. Môžeme meniť big_num, big_num1, čo sú konštanty pokiaľ ma klasický algoritmus hľadať deliteľov.
3. Môžeme meniť aj b_first, čo je počiatočná premenná v algoritme, no zmena neprinesie žiaden viditeľný rozdiel, preto je hodnota nižšia, nezadávajte viac ako 1000.

Záver

Dúfam, že tieto informácie, program sa čitateľom páčil. Na internete nenájdete bežne program na efektívne preverovanie obrovských čísiel. Tento algoritmus obsahuje veľmi efektívny spôsob ako sa zbaviť obrovských mocnín v malej Fermatovej vete. Algoritmus sa dá napr. efektívne spojiť s Rabin - Miler testom na prvočísla.