 For instance the Solovay–Strassen primality test on a given number formula_20 chooses a number formula_34 randomly from formula_137 through formula_213 and uses modular exponentiation to check
whether formula_214 is divisible by formula_20.If so, it answers yes and otherwise it answers no.If formula_20 really is prime, it will always answer yes, but if formula_20 is composite then it answers yes with probability at most 1/2 and no with probability at least 1/2.