Mala Fermatova veta - prvocisla 5 diel

Autor súvislosti: Robopol

Úvod

Tento diel je voľným pokračovaním na predchádzajúce diely o prvočíslach. Tak som si troška vyhrnul rukávy a pozrel sa ako bude vyzerať Fermatova veta geometricky. Stálo ma to trocha času rozkresliť súvislosti, ktoré Fermatová veta obsahuje. No myslím, že výsledok stál za tu trochu námahy..

Ešte predtým, ako sa pustime do geometrickej interpretácie si čitateľ môže pozrieť kombinačný aspekt malej Fermatovej vety.

Veľmi pekne vysvetlená malá Fermatova veta na videu:
https://cs.khanacademy.org/computing/computer-science/cryptography/random-algorithms-probability/v/f...

Geometria malej Fermatovej vety

Na obr.1 sú nakreslené súvislosti pre a=2, zo vzťahu malej Fermatovej vety. Vrchná časť obr.1 nám ukazuje ako sa množstvo (guličiek) s funkciou 2ˆn zväčšuje. Množstvo je vždy dvojnásobkom predchádzajúceho množstva guličiek. Pre a=3, to bude trojnásobok, pre a=7, sedemnásobok, atď.

Fermatova vetapng
Obr. 1 Geometria malej Fermatovej vety, zdroj: vlastný obrázok.

Zvyšok obr.1 ukazuje súvislosť Fermatovej vety pre malé „a“. To samozrejme nie je prekvapujúce, pretože malá Fermatová veta je platná a dokázaná. Tento obrázok som musel urobiť, aby boli jasné nasledujúce súvislosti. Zaujímavé to začne byť pri väčších prvočíslach obr.2.

Fermatova veta_zavislostpng
Obr.2 Geometria malej Fermatovej vety, zdroj: vlastný obrázok.

Počet guličiek sa nám vo funkcii 2ˆn rýchlo zväčšuje, ako je vidieť na obr. 2. Môžeme urobiť takú vec, že odčítame z celkového počtu guličiek rady prvočísiel (ako je vidieť pre číslo 7, obr.1, potom pre číslo 11,13 z obr. 2). Dostaneme obdĺžnik (zvyšok), ktorý je pre prvočísla špecifický a definovaný všeobecne pre 2ˆn: 

Screenshot - 15_ 6 004png

Obdĺžniky môžu byť aj pootočené o 90 stupňov. Teda x(1)=p-1 , y(1)=p-2, pre x(2)=p+2, y(2)=p+1.

Tento zvyšný obdĺžnik vyplníme do špirály (obr.2). Samozrejme dá sa do aj tak, že vytvoríme špecifického hadíka. Ja som to urobil do špecifickej špirály. To je detail ako zvyšný obdĺžnik vyplníme. Dôležité v tomto bode je, či existuje aj iný zvyšok pre prvočísla (?). Ak čitateľ vie, nech sa ozve.


Na obr. 2 je zvyšok pre a=9, ten zvyšok má iné hrany neplatí x=p-1, y=p-2. malá Fermatová veta však dáva celočíselná hodnoty aj pre zmiešané, nepárne čísla. Preto vytvorené algoritmy musia preveriť aj pre iné „a“ výsledok vzťahu. Viac informácii nájdete  Prvočísla -4 diel.

Obdĺžnik plochy guličiek 2ˆn bude mať hrany:

Screenshot - 15_ 6png
Funkcia int() vracia celočíselnú hodnotu v zátvorke. 

Z geometrickej závislosti dostaneme tieto odvodené vzťahy pre malú Fermatovú vetu, platí pre p=prvočísla:

rovnice-fermatpng
Algoritmus výpočtu (bez použitia modulárnej aritmetiky):
Dosadiť preverované číslo do každej rovnice, celkom 8, ak výsledok vzťahu je celé číslo pre jeden zo 4 zvyškov, teda presne dve celé čísla budú v jednej sústave o 2 rovniciach, potom je velmi vysoká pravdepodobnosť, že je to prvočíslo. Celý algoritmus je v krokoch, pre ručne zadanie na stránke Wolfram, pričom použijeme ešte funkciu MOD - modulus : zbytok po delení.

kroky:
1 krok: preveriť 1rovnicu v 4 celkoch: //dosadiť za p: preverované číslo
wolfram
https://www.wolframalpha.com/input/?i=%282%CB%86int%28p%2F2%29-p%2B1%29modp%3D
https://www.wolframalpha.com/input/?i=%282%CB%86int%28p%2F2%29-p-1%29modp%3D
https://www.wolframalpha.com/input/?i=%282%CB%86int%28p%2F2%29-p%2B2%29modp%3D
https://www.wolframalpha.com/input/?i=%282%CB%86int%28p%2F2%29-p-2%29modp%3D
ak výsledok je rozdielny od nuly, potom skúmané číslo nie je prvočíslo (velká pravdepodobnosť).
2.krok" ak vyšlo v jednej z rovníc :0, potom treba preveriť druhú rovnicu ku konkrétnemu zvyšku, viď. rovnice.
3. krok: Ak je výsledok v kroku 2 znova 0, potom hladané číslo je prvočíslo (velká pravdepodobnosť).
4. krok: Ak nie je výsledok v druhom kroku nula, hľadané číslo nie je prvočíslo. (veľká pravdepodobnosť).

Poznámka:
Vzťahy sa významne redukujú viď. nasledujúci diel.
Príklad:
a=2, p=521245847
https://www.wolframalpha.com/input/?i=%282%CB%86int%28521245847%2F2%29-521245847-1%29mod521245847%3D
je to prvočíslo

pra a=2, zvyšok ?
-vzťah zatiaľ nemám (za podmienky, že existujú aj iné zvyšky)
Samozrejme tieto vzťahy nie su na prvý pohľad jednoduchšie, ako vzťah pre malú Fermatovú vetu, lenže pri výpočtoch, pre preverenie veľkých prvočísiel musíme zistiť výsledok 2ˆp, následne deliť veľkým číslom. To číslo bude oveľa väčšie ako   2ˆint(p/2), no a hlavne výpočtova náročnosť pri delení čiastočne klesla (bez použitia modulárnej aritmetiky). Samozrejme nesmú existovať rôzne zvyšky (?), ktoré by výpočtovú náročnosť neúmerne zvýšili. Zatiaľ som iné nenašiel . Našiel som prvočísla len pre 1 a 2 rovnicu -Wolfram odkazy (teda len tieto zvyšky, pootočenia), iné pootočenia mi zatiaľ nevyšli. Vyzerá to nádejne aspoň z hľadiska pravdepodobnosti určenia prvočísla.


Dalo by sa na základe geometrických súvislosti nejak zmierniť výpočtovú náročnosť problému?

Odpoveď:

Podľa všetkého dalo na základe využitia vlastnosti periódy prvočísiel. Tá perióda prvočísiel je daná hodnotou:

10ˆr*p, pričom r=1,2,3....

Príklad:

r=2, p=11, potom perióda=10ˆ2*p=100*11=1100, teda po 1100 guličkách pre smer x, y sa to začne opakovať.

Toto sa teda dá využiť na orezanie pôvodnej plochy guličiek na menšiu plochu, ktorá bude výpočtovo omnoho menej náročná.

Pri podrobnejšej úvahe sa však ukázalo, že orezávanie plochy je princíp klasického delenia jedného čísla druhým .... Teda tento nápad už obsahuje algoritmus delenia (násobok, zvyšok..atď.). Orezanie pôvodnej plochy nezmení výpočtovú náročnosť, pri veľkých číslach.

Príklad:

Odčítali sme 7 krát hodnotu, aby sme znížili rád pôvodného čísla, čo je v zmysle klasického delenia...

Screenshot - 16_ 6png