SPsPDem

Strong Pseudoprime Test Demonstration

Enter base $a$:

Enter modulus $m$:

How the Strong Pseudoprime Test Works

The strong pseudoprime test (also known as the Miller-Rabin test) is a probabilistic primality test that determines whether a number is likely prime or definitely composite:

1. 1First, we write $m - 1 = 2^j \cdot d$ where $d$ is odd, factoring out all powers of 2
2. 2We compute $a^d \bmod m$ using fast modular exponentiation
3. 3If $a^d \equiv \pm 1 \pmod{m}$, then $m$ passes the test (strong probable prime)
4. 4Otherwise, we repeatedly square the result: $a^{2d}, a^{4d}, a^{8d}, \ldots$ up to $a^{2^{j-1}d}$
5. 5If any of these intermediate values equals $-1 \pmod{m}$, then $m$ passes the test
6. 6If we find a value that squares to $1$ but is not $\pm 1$, then $m$ is definitely composite
7. 7Key insight: If $x^2 \equiv 1 \pmod{n}$ but $x \not\equiv \pm 1 \pmod{n}$, then $n$ is composite
8. 8This happens because $(x-1)(x+1) \equiv 0 \pmod{n}$, so $\gcd(x-1, n)$ gives a non-trivial factor
9. 9The test is based on Fermat's Little Theorem
10. 10If $m$ fails the test for any base $a$, then $m$ is definitely composite
11. 11If $m$ passes for many random bases, it is a strong probable prime with respect to base $a$
12. 12This test is widely used in cryptography for generating large prime numbers