It is known that an odd number is prime if and only if for every such that we have
Choose a random number between and .
By repeating this algorithm we can increase the chance that the result is correct. In order to estimate the probability of error, we make use of Theorem 1, which says that every independent iteration of the algorithm has a chance of at most of being wrong. Hence, after iterations there is at most a chance of getting a wrong result.
It suffices to exhibit one element which does not satisfy Equation (1). Indeed, if there exists one such element, then the set of all elements which do satisfy Equation (1) forms a proper subgroup of , from which we conclude that the elements satisfying Equation (1) number no more than half of the elements of .
We consider separately the cases where is squarefree and not squarefree. If is squarefree, let be a prime dividing and let be a quadratic non-residue mod . Using the Chinese Remainder Theorem, choose an integer such that:
The Jacobi symbol is given by
We will assume that and derive a contradiction. The equation implies that . However, since , we must have , so that , which is a contradiction.
|Date of creation||2013-03-22 14:27:33|
|Last modified on||2013-03-22 14:27:33|
|Last modified by||mathwizard (128)|