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.

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

Screenshot - 22_ 9jpg

príklady pre overenie Wolfram:
(1)

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

preverenie periody:

https://www.wolframalpha.com/input/?i=2147483647-1+mod+31

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

TRUE

(2)

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

preverenie periódy:

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

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

TRUE


Screenshot - 22_ 9 002jpg
Celý algoritmus nebude zverejnený (iba) na požiadanie na študijne, či vedecké účely.