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

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

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:

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

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.

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:

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.

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:

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é pridelenia intervalu (plochy).

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:

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, testované čí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):