Program na prvočísla

Úvod

Tento demonštračný program slúži na ukážku toho, ako sa dnes rýchlo dajú hľadať veľké prvočísla. Zároveň demonštruje všetky uvedené informácie na tomto blogu (v súvislosti s prvočíslami). Program si môžete voľne stiahnuť a používať.

Download (size:40 KB) : komprimované WinRar

Download (size:40 KB) : exe súbor

Metódy - Eratostenovo sito

Táto metóda patrí medzi klasické algoritmy na hľadanie prvočísiel, v programe je možné si zobraziť postupne prvočísla po zadané číslo „n“ – (kolónka test number). Viac informácii o tejto metóde nájdete napr. na Wikipédii.

Klasický algoritmus

V demonštračnom programe je čiastočne optimalizovaný, kde tento algoritmus delí zadané číslo- „n“ postupne do hodnoty sqrt(n). Pričom nedelí číslo párnymi číslami, ani číslami končiacimi päťkou. Dal by sa optimalizovať v súvislosti s rozšírenou Riemanovou hypotézou do hodnoty menšej ako je sqrt(n). Vzťah sa dá nájsť (logaritmický vzťah).

Redukovaná malá, Fermatová veta

Tento algoritmus je vytvorený a navrhnutý autorom stránky. Jeho princíp je zmesou využitia redukovanej, Fermatovej vety (viď. príspevky na blogu), využitia toho ako optimálne hľadať periódu prvočísiel. Následne využitie tejto periódy na rýchlejší výpočet oproti Rabin – Miller metóde. Rabin – Miller (program je možné stiahnuť z predošlého dielu)počíta s vyššími mocninami ako táto metóda, využíva dlhšie periódy, výpočet robí pre veľmi vysoké základy a>2. Princíp je približne rovnaký. Tento demonštračný program to robí len pre základ a=2, teda najmenším možným základom, napriek tomu odfiltruje veľmi veľa pseudoprvočísiel.

Fermatová veta potrebuje počítať vysoké mocniny, pri bežnom programovaní premenná pretečie u hodnoty 2^1000. V demonštračnom programe to je urobené tak, že je tu cyklus výpočtu po kroku 2^900, čo metódu extrémne spomalí pri vysokých číslach, nad 11 cifier. Tento fakt sa rieši tým, že sa napr. čísla prehodia do HEX sústavy (číslo potrebuje menší počet číslic) urobí sa výpočet a následne prevedie do desiatkovej sústavy. Tento demonštračný program tieto rozšírenia neobsahuje.

Program je určený ako ukážka správnosti tejto metódy, napriek tomu, že je obmedzená na rátanie po 2^900.

Experimentálna metóda

Princíp tejto metódy je vhodne upraviť malú Fermatovú vetu napr.

8208*2^(1500-x) mod 8209=6861 , kde chceme nejak elegatne vyriešiť tuto rovnicu bez použitia napr. Newtonovej metódy. Existuje Lambertová W funkcia, ktorá rieši napr. takúto rovnicu:

2^x-6x-2=0, 

Pokial by bolo teda možné nejak trnasfomovať Fermatovu vetu pre výpočet Lambertovej W funkcie, potom by bolo možné nájsť periódu prvočísla ešte efektívnejšie.Kedže v pôvodnej Fermatovej vete sú vysoké mocniny je možné použiť rovnicu na zvyšky algoritmu m(i),n(i).

Mersennové prvočísla

Program vypíše prvých 51 Mersennových prvočísiel. Zároveň obsahuje výpočet pre vyššie prvočísla. Pri tomto spôsobe je využitá veľmi krátka perióda T=exponent mocniny, platí pre základ a=2 malej, Fermatovej vety. Teda je možné extrémne rýchlo preveriť kandidátov na ďalšie Mersennové prvočísla. Pre základ a=2 však existuje pomerne veľa pseudoprvočísiel, teda pre optimalizáciu toho, či dané číslo je naozaj prvočíslo by sme museli urobiť výpočty aj pre iné základy a=2,3,4,5... No prvotný nestrel ďalších prvočísiel je extrémne rýchly a ukazuje to, že pokiaľ je exponent Mersennoveho čísla prvočíslo, potom je dobrá pravdepodobnosť, že to môže byť ďalšie Mersennové prvočíslo.