math-prime-number-miller-rabin-test.html
* created: 2025-10-21T22:33
* modified: 2025-11-25T17:59
title
Miller Rabin Test
description
Description
related notes
Miller-Rabin-Test
This is an improved version of the fermats primality test, which takes fermat liar into account.
Works with x \geq 3:
- Take a random a \geq 2
- Check if gcd(x, a) \neq 1
- Take a random odd d that solves for x - 1 = d \cdot 2^j
- For r \in \{0,..j-1\}
- Check if a^{d \cdot 2^{r}} \mod x = 1