= −1 mod 221 mod n = mod 221 = −1 mod 221. This gives that, either 221 is prime, or 47 is an Euler liar for 221. We try another random a, this time choosing a = 2: a(n−1)/2 mod n = 2110 mod 221 = 30 mod 221 mod n = mod 221 = −1 mod 221. Hence 2 is an Euler witness for the compositeness of 221, and 47 was in fact an Euler liar. Note that this tells us nothing about the prime factors of 221, which are actually 13 and 17. Algorithm and running time The algorithm can be written in pseudocode as follows: inputs: n, a value to test for primality k, a parameter that determines the accuracy of the test output: composite if n is composite, otherwise probably prime repeat k times: choose a randomly in the range [2,n − 1] if or then return composite return probably prime Using fast algorithms for modular exponentiation, the running time of this algorithm is O(k·log3 n), where k is the number of different values of a we test. Accuracy of the test It is possible for the algorithm to return an incorrect answer. If the input n is indeed prime, then the output will always correctly be probably prime. However, if the input n is composite then it is possible for the output to be incorrectly probably prime. The number n is then called an Euler–Jacobi pseudoprime. When n is odd and composite, at least half of all a with gcd(a,n) = 1 are Euler witnesses. We can prove this as follows: let {a1, a2, ..., am} be the Euler liars and a an Euler witness. Then, for i = 1,2,...,m: Because the following holds: now we know that This gives that each ai gives a number a·ai, which is also an Euler witness. So each Euler liar gives an Euler witness and so the number of Euler witnesses is larger or equal to the number of Euler liars. Therefore, when n is composite, at least half of all a with gcd(a,n) = 1 is an Euler witness. Hence, the probability of failure is at most 2−k (compare this with the probability of failure for the Miller–Rabin primality test, which is at most 4−k). For purposes of cryptography the more bases a we test, i.e. if we pick a sufficiently large value of k, the