Prvocisla - golden part

Úvod

Tento diel o prvočíslach bude ukážkou, ako sa dá pracovať s redukovanou Fermatovou vetou a algoritmom (prezentovaný v minulých dieloch). Výskum tejto problematiky nabaľuje ďalšie súvislosti a je možné nachádzať obrovské množstvo špecifických patternov (vzorov). Tieto vzory objavíme pri skúmaní chovania sa algoritmu (minulé diely, hlavne vylepšené hľadanie prvočísiel -2 diel).  V predchádzajúcom diely boli prezentované špeciálne prvočísla v tvare p=2ˆk+-1. Dnes sa pozrieme na schému všetkých prvočísiel, pretože každé prvočíslo sa dá zapísať ako:

Screenshot - 3_ 8jpg

Pre špeciálne prvočísla, s=1 je pattern/vzor ten najjednoduchší možný (s najkratšou periódou). Umožňuje nám však veľmi efektívne nájsť ľubovoľne veľké prvočíslo, resp. pseudoprvočíslo. To je možné na základe periódy m(i), n(i). Viac informácii v diely špeciálne prvočísla.


Príklady vzorov prvočísiel

Prezentované vlastnosti budú v tabuľkách excelu na príkladoch, pretože to je názornejšie. Z tabuliek zistíme, že pre rôzne "s" dostávame periódy T=(p-1)/2 alebo T=(p-1). V prípade, že prvočíslo má periódu T=(p-1), potom v hodnote (p-1)/2 sú hodnoty [ m(i),n(i) ] = [ 4,p-4 ]. Zložené čísla nemajú takéto periódy. Prvočísla teda okrem špeciálnych prvočísiel majú periódy veľké, dlhé. Prvočísla však majú aj kratšie periódy ako T=(p-1)/2, napríklad číslo 113, 8209. Viac informácii (o periódach) v diely o algoritme na prvočísla.

príklad kde s=3

Screenshot - 3_ 8 002jpg

príklady kde s=3*3

Screenshot - 3_ 8 003jpg


Pseudo prvočísla

V niektorom z predchádzajúcich dielov som načrtol to, že by som sa chcel povenovať aj problematike pseudo prvočísiel. Malá Fermatová veta dáva v niektorých prípadoch zhodu aj pre tzv. pseudoprime. Čitateľ si môže dohľadať o čo presne ide, napr. na Wikipédii.  Pseudoprvočísla majú veľmi krátke periódy.

Pre základ a=2 v malej Fermatovej vete je najmenšie pseudoprvočíslo p=341.

link: pseudoprvočísla (zdroj pre dáta)


vzťahy pre bunky:

m(i)=IF(MOD(G3;2)=1;$B$4-H4;(G3+2)/2)

n(i)=IF(MOD(H3;2)=1;$B$4-G4;(H3-2)/2)

pseudoprime1jpg

Dobre, skúsme to pre pseudoprvočíslo, ktoré sa objavuje pre viacero základov „a“ p=8911.

begin

pseudoprime2jpg

End

pseudoprime3jpg


Perióda prvočísla (v algoritme) tesne súvisí z jeho rozkladom na prvočísla.

Príklad:

341- má v algoritme periódu 10, rozklad čísla je 11.31 (najmenšie prvočíslo 11)

561- má v algoritme periódu 40, rozklad čísla je 561=3.11.17 (najmenšie prvočíslo 3)

1387- má v algoritme periódu 18, rozklad čísla je 1387=19.73 (najmenšie prvočíslo 19)

2047- má v algoritme periódu 11, rozklad čísla je 2047=23.89 (najmenšie prvočíslo 23)

...


Pre odhalenie zloženého čísla: Zložené číslo nesplní podmienku (p-1)=N,  -> N/perioda=integer. Pre zložené číslo nikdy nebude perióda celočíselným násobkom N ( s výnimkou pseudoprvočísiel, ktoré Fermatova veta nedokáže filtrovať).

Toto je veľmi zaujímavé z toho pohľadu, že efektivita takéhoto prehľadávania periódy  rastie pre rozklady, kde sú väčšie prvočinitele. Naopak kde sú rozklady na menších prvočiniteľov rastie efektivita klasického delenia (napr. Eratosovo sito). To sa dá použiť ako kombinácia metód (jedna z možnosti).

Existujú však pseudoprvočísla aj s veľmi krátkymi periódami, teda existujú aj pseudoprvočísla pre špeciálne prvočísla v tvare p=2^k +-1. Veľkosť periódy ich neodhalí.

Screenshot - 1_ 4jpg