strong pseudoprime test

A primality test that provides an efficient probabilistic algorithm for determining if a given number is prime. It is based on the properties of strong pseudoprimes. The algorithm proceeds as follows. Given an odd integer n, let n = 2^r s + 1 with s odd. Then choose a random integer a with 1<=a<=n - 1. If a^s congruent 1 (mod n) or a^(2^j s) congruent -1 (mod n) for some 0<=j<=r - 1, then n passes the test. A prime will pass the test for all a.

Baillie-PSW primality test | Lucas-Lehmer test | primality test | pseudoprime | strong pseudoprime