<span title="Home" class="fa-solid-900 icon"></span> Home

Codex Wiki

Computer science

Theoretical computer science

Computational complexity theory

Primality testing

Miller-Rabin primality test

{title2=$n<2^{64}$}

A <deterministic Miller-Rabin primality test> chooses bases justified to distinguish every composite in a specified input range, instead of sampling bases for a probabilistic guarantee. For each base, write $n-1=2^sd$ with odd $d$, test $a^d\bmod n$, and square successively according to the <Miller-Rabin primality test>. A failing base certifies compositeness; passing a fixed list certifies primality only under the proven range theorem for that list. For machine <integers> such as $n<2^{64}$, established finite-range base <sets> permit deterministic implementations. The exact bases, bound, treatment of small primes and modular-arithmetic overflow are part of the <algorithm>'s contract.


Deterministic Miller-Rabin primality test ( $n < 2^{64}$ )

 Ancestors (6)

 Incoming links (1)

 Discussion (0) New discussion

 Articles by others on the same topic (0)

Deterministic Miller-Rabin primality test (n<264)

 Ancestors (6)

 Incoming links (1)

 Discussion (0)  Subscribe (1) New discussion

 Articles by others on the same topic (0)

Deterministic Miller-Rabin primality test ( $n < 2^{64}$ )

 Discussion (0) New discussion