Variations
An Euler probable prime to base a is an integer that is indicated prime by the somewhat stronger theorem that for any prime p, a(p − 1)/2 equals modulo p, where is the Legendre symbol. An Euler probable prime which is composite is called an Euler–Jacobi pseudoprime to base a.
This test may be improved by using the fact that the only square roots of 1 modulo a prime are 1 and −1. Write n = d · 2s + 1, where d is odd. The number n is a strong probable prime (SPRP) to base a if one of the following conditions holds:
A composite strong probable prime to base a is called a strong pseudoprime to base a. Every strong probable prime to base a is also an Euler probable prime to the same base, but not vice versa.
Read more about this topic: Probable Prime
Famous quotes containing the word variations:
“I may be able to spot arrowheads on the desert but a refrigerator is a jungle in which I am easily lost. My wife, however, will unerringly point out that the cheese or the leftover roast is hiding right in front of my eyes. Hundreds of such experiences convince me that men and women often inhabit quite different visual worlds. These are differences which cannot be attributed to variations in visual acuity. Man and women simply have learned to use their eyes in very different ways.”
—Edward T. Hall (b. 1914)