Vylepsene hladanie prvocisiel

Úvod

Tento diel je voľným pokračovaním na Prvočísla -5 diel, kde bol rozobratý geometrický aspekt malej Fermatovej vety. Tento diel bude zovšeobecnením a upresnením toho, ako by sa dali hľadať efektívne veľké prvočísla. Keďže metóda je postavená na malej Fermatovej vete, nie je 100% záruka, že nájdeme prvočíslo, no pravdepodobnosť určenia prvočísla je veľmi vysoká (99,99..%)

Fermatová veta nie je 100% nástroj na určenie prvočísla. Tento problém sa rieši tak, že sa vyskúšajú aj iné základy pre a=2,3,4,....N. Testy ukázali, že pri aplikácii rovníc a k ním prislúchajúcich originálnych zvyškov MUSIA platiť pre naozaj veľký rozsah prvočísiel. Presne sa to dá dohľadať v literatúre.

Napr. pre tieto neplatí:

Screenshot - 30_ 6 002png

Tieto nedostatky malej Fermatovej vety sa riešia napr. takto:

Screenshot - 30_ 6 003png

zdroj: thales.doa.fmph.uniba.sk/sleziak/papers/aks.pdf


Dnes zhrnieme, čo testy ďalej ukazujú:

Pozitívna správa je, že nám vypadli rovnice, ktoré v algoritme nedávajú test prvočíselnosti. To znamená, že potrebné sú len tieto vzťahy:

upravena fermatova vetapng

Poznámka:

Ak preveríme rovnice pre y- smer, nie je potrebné úž preverovať rovnice pre x - smer, pretože sú vzájomne závislé. Toto tvrdenie platí aj naopak. Ak preverujeme rovnice pre x - smer, nie je potrebné preverovať pre y- smer. Vysvetlenie, prečo je tomu, viď nižšie.


Delenie intervalu 2ˆp

V predchádzajúcom diely o prvočíslach bolo konštatované, že orezávanie pôvodnej plochy cez periódu čísiel, teda zmenšovanie plochy 2ˆp číslom 10 ˆr*p, pre r=1,2,3.... nie je účinné, v zmysle zníženia výpočtovej náročnosti (veľké prvočísla – viď. diel prvočísla 5 diel).

priklad_delenie_intervalupng

Obr.1 Príklad delenia os – x, pre p=11, p=13, zdroj: vlastný obrázok.

Pri delení plochy v zmysle. Obr.1 nám prvočísla končia pre os x zvyšok x(1)-> stred+1, teda v príklade to je: 2 ˆ(int(p/2)+1)/2+1=2 ˆint(p/2)+1. Tam končia prvočísla (v zmysle celočíselného násobku). Zistíme však, že všeobecne platí pre všetky prvočísla os x, v zmysle obr.2.

vseobecne_delenie_intervalupng

Obr. 2 Predelenie os x, pre p=prvočíslo, zdroj: vlastný obrázok.

Všeobecne teda platí pre zvyšok x(1), že prvočísla končia -> stred+1, pre zvyšok x(2) končia -> stred -1.


Poďme túto novú vlastnosť použiť nasledovne:

Ak teda všetky prvočísla po predelení končia v polovici intervalu os : x +-1, potom teda musí platiť vzťah:

upravene_vztahypng

Dosadením tejto novej vlastnosti do vzťahov dostaneme identické vzťahy pre y(1), y(2), viď. vzťahy vyššie. Z toho plynie záver ten, že postačuje nám preveriť iba dve rovnice, viď. algoritmus výpočtu.


Z tejto vlastnosti obr.2 sa dajú vytvoriť jednoduchšie vzťahy (ako doposiaľ):

vylepsena_fermatova_vetapng

Mohli by skúsiť predeliť na polovicu y-novú hodnotu 2 ˆint(p/2) a pozrieť sa, kde budú končiť prvočísla (znížime výpočtovú náročnosť o jeden rad), nájdeme tento vzťah:

vylepsena_fermatova_veta2png


Čo, keby sme našli algoritmus, ktorý bude znižovať rád mocniny 2ˆint(p/2) o ľubovoľne veľkú hodnotu?

No zdá sa, že to také jednoduché nebude. Zatiaľ som našiel zhodu pre predelenie plochy na ½ a následne na ¼. Vzťahy sú vyššie. No takto jednoducho sa nebude dať pokračovať, pretože prvočísla nebudú v rovnakých pozíciách, pre ľubovoľné predelenia intervalu (plochy).

Update: pripravuje sa ďalší diel, pretože sa zdá, že je možno nájsť celkom jednoduchý algoritmus pre pokračovanie.


Náročnosť výpočtu by sme mohli troška znížiť ešte tým, že pred samotným delením čitateľa  menovateľom p, odčítame ešte hodnotu 2 ˆk*p. Z toho dostaneme vzťahy:

Screenshot - 30_ 6png


Upravený vzťah:

1 krok: preveriť 1rovnicu v 2 celkoch: //dosadiť za p: preverované číslo
wolfram
https://www.wolframalpha.com/input/?i=%282%CB%86int%28p%2F2%29%2B1%29mod+p%3D
https://www.wolframalpha.com/input/?i=%282%CB%86int%28p%2F2%29-1%29modp%3D
ak výsledok je rozdielny od nuly, potom skúmané číslo nie je prvočíslo (veľká pravdepodobnosť).
2.krok" ak vyšlo v jednej z rovníc :0, potom testované číslo je prvočíslo (veľká pravdepodobnosť ).

Príklad:

P=1381

https://www.wolframalpha.com/input/?i=%282%CB%86int%281381%2F2%29%2B1%29mod1381%3D

mod 0, tesované číslo je prvočíslo. 


Záver

Takže zatiaľ som sa dostal k tejto formule, ktorá by mohla byť výpočtovo menej náročná, ako malá Fermatová veta, možno aj s použitím modulárnej aritmetiky (viď. príklady):

Better_Fermat_robopolSKpng