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ť.

Inštalačný súbor programu - Download (size:500 KB) : komprimované WinRar

Stiahnite si inštalačný súbor, rozbaľte v programe WinRar, nainštalujte do PC (súbor setupPrimeNumberTest.exe), nainštaluje sa Vám ikona v ponuke štart, súbor je bezpečný, povoľte nainštalovať súbor cez antivírovú ochranu.


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 využíva vzťahy modulárnej aritmetiky, kde medzi sebou násobí zvyšky miesto výpočtu obrovských mocnín. No pri velkých číslach pretečie násobenie, či umocňovanie.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 a efektívnosti tejto metódy v určitom rozsahu čísiel.

Efektívny spôsob rátania malej Fermatovej vety je schematicky znázorený na obr.1.


graf zvyskovjpg

Obr.1 Grafický priebeh zvyškov , zdroj: vlastný obrázok.

Priebeh zvyškov 2^x mod p si môžete pozrieť pre male prvočísla v súbore: prvočísla_pokusy.xlsx.

Dá sa nájsť efektívna metóda ako zbytočne nerátať velké mocniny (zaberajú hodne číslic, potrebujú konverziu, bežne premenné sú ohraničené velkosťou, napr. 16 číslic) tak, že miesto umocňovania 2^x  využijeme to, že platí:


príklad:

2 ^500 mod p =a,     2 ^1000 mod p=(a *a)/mod p=b,   2 ^2000 mod p=(b*b)/mod p=c

Pre znázorenie tejto jednoduchej metódy, pre rýchly výpočet malej Fermatovej vety prikladám tento algoritmus (visual basic):

simple_algorithm_eulerjpg

Obr. 2 Využitie Eulerovej vety a efektívneho rátania pomocou zvyškov: autor Robopol.


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.


Záhadné číslo 24

V diskusii na internete som narazil na hypotézu, že:
pre p=prvočíslo platí:
p ^ 2 Mod 24=0

Hypotéza bola preverená pre všetky čísla od >3 po 999 999 999. Pre určenie, či sa jedná o prvočíslo táto hypotéza nepostačuje, pretože podmienku spĺňa zhruba 1/10 čísiel. No je to dobrý, úvodný filter, pre určenie zložených čísiel. V tejto hypotéze (pri platnosti) n ---> infinity, táto hypotéza naznačuje filter štruktúry rozloženia prvočísiel.