Úvod

Update: 30.06.2021

Tento demonštračný program slúži na ukážku toho, ako sa dnes rýchlo dajú hľadať 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ť.

LINK: 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.

Algoritmus na extrémne, veľké prvočísla

---

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.

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 veľkých číslach pretečie násobenie, či umocňovanie. Program je určený ako ukážka správnosti a efektívnosti tejto metódy.

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

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ť veľké mocniny (zaberajú hodne číslic, potrebujú konverziu, bežne premenné sú ohraničené veľkosť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

Algoritmus pre aplikáciu Fermatovej vety, pre extrémne veľké čísla, program v Pythone:

Obr. 2 Využitie Fermatovej 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=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

Každé prvočíslo patrí do množiny nepárnych čísiel vyjadrených vzťahom (6k+-1), pre k=1,2,3....n.

Dosaďme za p:

(6k+-1)^2 -1 Mod 24=0

(36k ^2 +-12k+1) -1 Mod 24=0

36k ^2 +-12k  Mod 24=0    //vyjmeme 12k

12k (3k+-1) Mod 24 =0

člen (3k+-1) v rovnici je pre k=1,3,5...(každé nepárne k) vždy deliteľný 2, ostane nám

12k *(2*i) mod 24=0 , pričom i =1,2,3...n,  upravíme rovnicu

24k*i mod 24=0

Dostali sme rovnosť pretože akýkoľvek násobok 24 mod 24 je nula.

pre člen (3k+-1) v rovnici pre k=2,4,6,8 (každé párne k) nám dá vždy nepárne číslo "j". Člen 12k nám však dá vždy násobok čísla 24, pretože k je vždy deliteľné 2, teda platí:

(24*(k-1) *j) mod 24 =0, pričom "j" je prirodzené číslo a uvedená rovnica spĺňa vždy rovnosť, pretože akýkoľvek násobok (celým číslom) 24 Mod 24 dá vždy nulu.