# Strong pseudoprime

Jump to: navigation, search

## 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 Failed to parse (PNG conversion failed; check for correct installation of latex and dvipng (or dvips + gs + convert)):

```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.