Very fast algoritmus na prvocisla

Ú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. Miler- 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:

http://www.naturalnumbers.org/tools.html#MR

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ú neskutočne rýchlo. Teda počítač dokáže vyrátať naozaj obrovské čísla.

Periódy prvočísiel

Mersenjpg

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.
Pre základ a=2 malej, Fermatovej vety sa pseudoprvočísla vyskytujú pomerne často. Rýchle hľadanie Mersennových prvočísiel sa redukuje na preverenie toho, či exponent je prvočíslo, alebo nie je. Ak je exponent prvočíslo (perioda T),  potom ide o Mersennove prvočíslo, resp. pseudoprvočíslo!

Algorithmjpg
Celý algoritmus nebude zverejnený (iba) na požiadanie na študijne, či vedecké účely. Viac informácii v článku program na prvočísla.