Strong pseudoprime

Strong pseudoprime

In number theory, a strong pseudoprime is a composite number that passes a pseudoprimality test. All primes pass this test, but a small fraction of composites pass as well, making them "false primes". Unlike the Fermat pseudoprimes, for which there exist numbers that are pseudoprimes to all bases (the Carmichael numbers), there are no composites that are strong pseudoprimes to all bases.

Formal definition

Formally, a composite number "n" = "d" · 2"s" + 1 is called a strong pseudoprime to a relatively prime base "a" iff one of the following conditions hold:

: a^dequiv 1mod n

: a^{dcdot 2^r}equiv -1mod nquadmbox{ for some }0leq rleq(s-1)

The definition of a strong pseudoprime depends on the base used; different bases have different strong pseudoprimes.

It should be noted, however, that Guy uses a definition with only the first condition [Guy, "Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes." §A12 in "Unsolved Problems in Number Theory", 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.] . Because not all primes pass that condition, this definition of 'strong pseudoprimes' resembles the primes less closely.

Properties of strong pseudoprimes

A strong pseudoprime to base "a" is always an Euler pseudoprime Pomerance, Selfridge and Wagstaff, "The pseudoprimes to 25 · 109." "Mathematics of Computation", 35:151 pp. 1003-1026, 1980.] and a Fermat pseudoprime to that base, but not all Euler and Fermat pseudoprimes are strong pseudoprimes. Some Carmichael numbers are also strong pseudoprimes.

A composite number "n" is a strong pseudoprime to at most one quarter of all bases below "n" [Monier, "Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms." "Theoretical Computer Science", 12 pp. 97-108, 1980.] [Rabin, "Probabilistic Algorithm for Testing Primality." "Journal of Number Theory", 12 pp. 128-138, 1980.] ; thus, there are no "strong Carmichael numbers", numbers that are strong pseudoprimes to all bases. Thus given a random base, the probability that a number is a strong pseudoprime to that base is less than 1/4, forming the basis of the widely-used Miller-Rabin primality test. However, there are still infinitely many strong pseudoprimes to any base.

Examples

The first strong pseudoprimes to base 2 are:2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751, ... OEIS|id=A001262.The first to base 3 are:121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513, 87913, 88573, 97567, ... (OEIS2C|id=A020229).The first to base 5 are:781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, 79381, ... (OEIS2C|id=A020231).

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Pseudoprime — A pseudoprime is a probable prime (an integer which shares a property common to all prime numbers) which is not actually prime. Pseudoprimes can be classified according to which property they satisfy.The most important class of pseudoprimes come… …   Wikipedia

  • Strong prime — In mathematics, a strong prime is a prime number with certain special properties. The definitions of strong primes are different in cryptography and number theory. Definition in cryptography In cryptography, a prime number p is strong if the… …   Wikipedia

  • Strong Frobenius pseudoprime — A strong Frobenius pseudoprime is a pseudoprime which obeys an additional restriction beyond that required for a Frobenius pseudoprime.External links*MathWorld|title=Strong Frobenius pseudoprime|urlname=StrongFrobeniusPseudoprime …   Wikipedia

  • Lucas pseudoprime — In number theory, the classes of Lucas pseudoprime and Fibonacci pseudoprime comprise sequences of composite integers that passes certain tests that all primes pass: in this case, criteria relative to some Lucas sequence.DefinitionGiven two… …   Wikipedia

  • Euler pseudoprime — An odd composite integer n is called an Euler pseudoprime to base a , if a and n are coprime, and : a^{(n 1)/2} equiv pm 1pmod{n}(where mod refers to the modulo operation).The motivation for this definition is the fact that all prime numbers p… …   Wikipedia

  • Euler-Jacobi pseudoprime — In number theory, an odd composite integer n is called an Euler Jacobi pseudoprime to base a , if a and n are coprime, and : a ( n − 1)/2 = ( a / n ) (mod n ), where ( a / n ) is the Jacobi symbol.The motivation for this definition is the fact… …   Wikipedia

  • Frobenius pseudoprime — In number theory, a Frobenius pseudoprime is a composite number which passes a three step probable prime test set out by Jon Grantham in section 3 of his paper Frobenius pseudoprimes . [Jon Grantham. [http://www.pseudoprime.com/pseudo1.pdf… …   Wikipedia

  • Probable prime — In number theory, a probable prime (PRP) is an integer that satisfies a specific condition also satisfied by all prime numbers. Different types of probable primes have different specific conditions. While there may be probable primes that are… …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Miller–Rabin primality test — The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay–Strassen primality test. Its original version …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”