Úvod

Tento diel bude venovaný periódam algoritmu na m(i), n(i). Zároveň tieto periódy využijeme pri Redukovanej Fermatovej vete (autor: Robopol). V tom diely bude aj náčrt algoritmu na prvočísla s lepším, resp. porovnateľným s Miller -Rabin testom. Miller- Rabin test dokáže eliminovať aj väčšinu pseudoprvočísiel, no nie všetky (silné pseudoprvočísla).

Miller- Rabin test a program si môžete stiahnuť tu:

Testy na prvočísla s využitím Fermatovej vety (malej) fungujú práve preto tak rýchlo, pretože vstavané algoritmy na umocňovanie fungujú rýchlo. Teda počítač dokáže vyrátať naozaj obrovské mocniny.

Periódy prvočísiel

príklady pre overenie Wolfram:
(1)

https://www.wolframalpha.com/input/?i=2%5E31+mod+%282%5E31-1%29

preverenie periody:

https://www.wolframalpha.com/input/?i=%282147483647-1%29%2F2+mod+31

TRUE

(2)

https://www.wolframalpha.com/input/?i=2%5E82589933+mod+%282%5E82589933-1%29

preverenie periódy:

https://www.wolframalpha.com/input/?i=%282%5E82589933-1-1%29%2F2+mod+82589933

TRUE

Poznámka:

Pre špeciálne prvočísla postačuje preveriť periódu.Nie je nutné počítať Fermatovú vetu. Pre prvočísla v tvare:

1. p=2 ^k-1, perioda T=k, podmienka: (p-1)/2 mod T=0
   
2. p= 2 ^k+1, perioda T=2k, podmienka: (p-1) mod T=0
3. Ak platí podmienka ide pravdepodobne o prvočíslo.