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

Verzie algoritmu, zdrojový kód

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:

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.

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.

Introduction

This article presents an efficient algorithm for testing extremely large numbers (author: Robopol). The algorithm tests a number and determines whether it is a composite number or a prime number. This article is also an update to a previous article - Prime Number Program. The algorithm is programmed in the Python programming language. For more information about Python (installation, execution, etc.), visit the page - Mathematics in Python, or information is available online on the internet.

The algorithm also uses relationships (Robopol theorem):

Algorithm Versions, Source Code

Fig. 1 Program User Interface

---

Versions:
File download - Github: prime_test_GUI.py (newer version with GUI)
HTML version: prime-numbers-test.html

Description: The algorithm contains classical prime number search + special algorithm for extremely large numbers.

---

Examples of Extreme Prime Numbers

Let's now test how fast this algorithm is on a regular PC with a slightly better graphics card, average processor, and 16 GB RAM:

For interest, let's make it work a bit harder by selecting Mersenne prime numbers. (https://en.wikipedia.org/wiki/Mersenne_prime)

Let's select, for example, the number at position 25 with 6533 digits. First, however, we need to have the complete numerical form. So we open the command line cmd, type Python, which launches Python in the Windows command line. We calculate the value 2^21701-1:

Fig. 4 Calculation of 2^21701-1 in Python, source: own image.

Then we copy this number to the opened program for number input.

Fig. 5 Result in the program, source: own image.

The algorithm produces a result in approximately 45 seconds, stating that it is a prime number or pseudoprime. This is a very good result in terms of speed.

When testing numbers, we can change parameters in the program, i.e., constants:

1. We can change the base of Fermat's theorem, variable "a", e.g., we want to evaluate the result also for a=3,4,5,7, etc.
2. We can change big_num, big_num1, which are constants for when the classical algorithm should search for divisors.
3. We can also change b_first, which is the initial variable in the algorithm, but the change will not bring any visible difference, so the value is lower, do not enter more than 1000.

---

Conclusion

I hope that readers enjoyed this information and program. You won't commonly find a program on the internet for efficiently checking huge numbers. This algorithm contains a very efficient method for eliminating huge powers in Fermat's little theorem. The algorithm can be efficiently combined with the Rabin-Miller primality test, for example.