Pseudoprime

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 from Fermat's little theorem and hence are called Fermat pseudoprimes. This theorem states that if "p" is prime and "a" is coprime to "p", then "a""p"-1 - 1 is divisible by "p". If a number "x" is not prime, "a" is coprime to "x" and "x" divides "a""x"-1 - 1, then "x" is called a "pseudoprime to base a". A number "x" that is a pseudoprime for all values of "a" that are coprime to "x" is called a Carmichael number.

The smallest Fermat pseudoprime for the base 2 is 341. It is not a prime, since it equals 11 · 31, but it satisfies Fermat's little theorem: 2340≡1 (mod 341).

The rarity of such pseudoprimes has important practical implications. For example, public-key cryptography algorithms such as RSA require the ability to quickly find large primes. The usual algorithm to generate prime numbers is to generate random odd numbers and test them for primality. However, deterministic primality tests are slow. If the user is willing to tolerate an arbitrarily small chance that the number found is not a prime number but a pseudoprime, it is possible to use the much faster and simpler Fermat primality test.

Another approach is to use more refined notions of pseudoprimality, e.g. strong pseudoprimes or Euler-Jacobi pseudoprimes, for which there are no analogues of Carmichael numbers. This leads to probabilistic algorithms such as the Solovay-Strassen primality test and the Miller-Rabin primality test, which produce what are known as industrial-grade primes. Industrial-grade primes are integers for which primality has not been "certified" (i.e. rigorously proven), but have undergone a test such as the Miller-Rabin test which has nonzero, but arbitrarily low, probability of failure.

There are infinitely many pseudoprimes to a given base (in fact, infinitely many Carmichael numbers), but they are rather rare. There are only 3 pseudo-primes to base 2 below 1000, and below a million there are only 245. Pseudoprimes to base 2 are called Poulet numbers or sometimes Sarrus numbers or Fermatians OEIS|id=A001567. The factorizations of the 60 Poulet numbers and 13 Carmichael numbers (in bold) up to 60787 are in the below table.

|

A Poulet number all of whose divisors "d" divide 2"d" - 2 is called a super-Poulet number. There are infinitely many Poulet numbers which are not super-Poulet Numbers.

The first smallest pseudoprimes for bases "a" ≤ 200 are given in the following table; the colors mark the number of prime factors.

ee also


*Euler pseudoprime
** base-2 Euler pseudoprimes (sequence [http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=006970 A006970] in OEIS)
*Euler-Jacobi pseudoprime
** base-2 Euler-Jacobi pseudoprimes (sequence [http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=047713 A047713] in OEIS)
** base-3 Euler-Jacobi pseudoprimes (sequence [http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=048950 A048950] in OEIS)
*Extra strong Lucas pseudoprime
*Fibonacci pseudoprime
*Lucas pseudoprime
*Perrin pseudoprime
*Somer-Lucas pseudoprime
*Strong Frobenius pseudoprime
*Strong Lucas pseudoprime
*Strong pseudoprime
** base-2 strong pseudoprimes (sequence [http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=001262 A001262] in OEIS)

External links

* [http://de.wikibooks.org/wiki/Pseudoprimzahlen:_Tabelle_Pseudoprimzahlen_(15_-_4999) Pseudoprimes up to 5,000]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • pseudoprime — 1. noun An integer that possesses at least one characteristic of a prime number without actually being prime. 2. adjective Describing such an integer …   Wiktionary

  • 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

  • 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… …   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

  • 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

  • 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

  • Somer-Lucas pseudoprime — In mathematics, in particular number theory, an odd composite number N is a Somer Lucas d pseudoprime (with given dle 1) if there exists a nondegenerate Lucas sequence :U(P,Q) with :U 0=0, U 1=1, D=P^2 4Q, such that :(N,D)=1 and the rank… …   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

  • Псевдопростое число — Натуральное число называется псевдопростым, если оно обладает некоторыми свойствами простых чисел, являясь тем не менее составным числом. В зависимости от рассматриваемых свойств существует несколько различных типов псевдопростых чисел.… …   Википедия

Share the article and excerpts

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