# Strong pseudoprime

From Number

Template:Base-relative pseudoprimality property

## Definition

Suppose is an odd composite natural number and is an integer relatively prime to . We say that is a **strong pseudoprime** (also called **Miller-Rabin pseudoprime**, **Rabin-Miller pseudoprime**, **Miller-Rabin strong pseudoprime**, **Rabin-Miller strong pseudoprime**) to base if the following holds.

Write </math>n-1 = 2^k s</math> where is odd and is a nonnegative integer. Then, either one of these conditions should hold:

- .
- . Further, consider the smallest for which . Then, . In other words, the last value before becoming should be .

The name *strong pseudoprime* is because the above condition is satisfied for all primes, and is a particularly strong condition for which finding composite numbers is hard.