You are here
Home ›Solovay-Strassen test
Primary tabs
Solovay-Strassen test
It is known that an odd number is prime if and only if for every such that we have
| (1) |
where is the Jacobi symbol. (The only if part is obvious; the if part follows from Theorem 1.) From this we can derive the following algorithm.
1. Choose a random number between and .
2. Check if (for example using the Euclidean algorithm). If it is not, then is not prime and is a divisor of .
3.
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.
Theorem 1.
Let be an odd composite integer. Then at least half of the elements of do not satisfy Equation (1).
Proof.
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.
Now suppose that is not squarefree. Let be a prime such that , and set . By the binomial theorem, we have
so the multiplicative order of is equal to , and hence in particular , since . On the other hand,
so does not satisfy Equation (1). ∎
Mathematics Subject Classification
11Y11 Primality- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)
- Other useful stuff
Recent Activity
new question: Sorry to steal a few minutes of your time for this question, but i honestly don't know what else to do. by Whrazithar
new question: equality of the determinants of submatrices of an orthogonal matrix by ismayli
Jun 11
new correction: Typo by suitangi
Jun 2
new question: Creating another set with same cardinality. by hkkass
Jun 1
new image: ProblemOneRevised by unlord
new Education: Chapter II by rspuzio
May 31
new collection: The Calculus by Davis and Brenke by rspuzio
new question: Proofs by weixifan
new question: Summation Integration Question by trevor.nickle
May 27
new correction: typo+finite measure hypothesis by Filipe


