Algoritmus na extrémne prvočísla v Pythone

11. 3. 2025 Ing. Róbert Polák Matematika

Ú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):

Screenshot - 1_ 4jpg

Verzie algoritmu, zdrojový kód

Screenshot - 11_ 3png
Obr. 1 Užívateľské prostredie programu

Verzie:
download súboru - Github: prime_test_GUI.py (novšia verzia s GUI)
html verzia: prime-numbers-test.html

Popis: Algoritmus obsahuje klasické vyhľadávanie prvočísiel + špeciálny algoritmus na extrémne veľké čísla.

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.