Rabin-Millerův test prvočíselnosti

Implementace pravděpodobnostního testu provočíselnosti dle algoritmu Rabin-Miller. Pro operace s dlouhými čísly je možno využít knihovnu, ale je třeba použít algoritmus Montgomeryho umocňování. Celková složitost jednoho testu by měla být O(N^2+ε), za předpokladu, že knihovna umí sčítání, odčítání, porovnávání a bitové operace v lineárním čase, násobení dvou čísel délky N v čase O(N^1+ε) a dělení čísel délky N a M v čase O(N*M).

Zpět