Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3).
Navigation
Topics Help • Register • News • History • How to • Sequences statistics • Template prototypes

Difference between revisions of "Primality test"

From Prime-Wiki
Jump to: navigation, search
(restored)
 
m (Using internal link)
 
(6 intermediate revisions by 2 users not shown)
Line 1: Line 1:
A '''primality test''' is a test that determines whether a given number is [[prime number|prime]] or [[composite number|composite]]. When the number is declared composite, the algorithm does not reveal the prime [[factor]]s. That is the job of the [[Factorization|factorization methods]].
+
A '''primality test''' is a test that determines whether a given number is [[prime]] or [[composite number|composite]]. When the number is declared composite, the algorithm does not reveal the prime [[factor]]s. That is the job of the [[Factorization|factorization methods]].
  
 
Some primality tests are really probable primality tests. When they determine that a number is composite, it really is, but otherwise we are not completely sure if it is prime because they fail for some input values. Combining several probable primality tests the confidence grows, but we cannot be completely sure that the number is prime until a primality test (which is far slower than a probable primality test except when the input number has a special form) is run on it.
 
Some primality tests are really probable primality tests. When they determine that a number is composite, it really is, but otherwise we are not completely sure if it is prime because they fail for some input values. Combining several probable primality tests the confidence grows, but we cannot be completely sure that the number is prime until a primality test (which is far slower than a probable primality test except when the input number has a special form) is run on it.
Line 7: Line 7:
 
Since all primality tests use [[modular arithmetic]], reading the modular arithmetic article is a prerequisite to understanding those methods.
 
Since all primality tests use [[modular arithmetic]], reading the modular arithmetic article is a prerequisite to understanding those methods.
  
==Primality tests for numbers N with special form==
+
==Primality tests for numbers {{V|N}} with special form==
*[[Lucas primality test|Lucas Test]]: Used when the number N-1 is completely factored.
+
*[[Lucas primality test|Lucas Test]]: Used when the number {{V|N}}-1 is completely factored.
*[[Pocklington's Theorem]]: Used when most of the prime factors of the input number - 1 are known (the unfactored part of N-1 must be less than the [[square root]] of N).
+
*[[Pocklington's theorem]]: Used when most of the prime factors of the input number - 1 are known (the unfactored part of {{V|N}}-1 must be less than the [[square root]] of {{V|N}}).
*[[wikipedia:Morrison's Theorem]]: Used when most of the prime factors of the input number + 1 are known (the unfactored part of N+1 must be less than the [[square root]] of N).
+
*[[Morrison's Theorem]]: Used when most of the prime factors of the input number + 1 are known (the unfactored part of {{V|N}}+1 must be less than the square root of {{V|N}}).
*[[wikipedia:Selfridge's Cube Root Primality Test]]: This method can be used when the product of the known prime factors of N-1 is greater than the cube root of N.
+
*[[Selfridge's Cube Root Primality Test]]: This method can be used when the product of the known prime factors of {{V|N}}-1 is greater than the cube root of {{V|N}}.
*[[Lucas-Lehmer test]]: Used in [[GIMPS]]
+
*[[Lucas-Lehmer test|Lucas–Lehmer test]]: Used in [[GIMPS]].
*[[Pépin Test]]: Used to test primality in Fermat numbers.
+
*[[LLR|Lucas–Lehmer–Riesel test]]: Used for [[Riesel prime]]s.
*[[Proth's Theorem]]: Used to test numbers of the form k*2<sup>n</sup>+1 with 2<sup>n</sup> > k, making it useful in several [[distributed computing projects]].
+
*[[Pépin's test]]: Used to test primality in Fermat numbers.
 +
*[[Proth's theorem]]: Used to test numbers of the form {{Kbn|+|k|n}} with 2<sup>{{Vn}}</sup> > {{Vk}}, making it useful in several [[distributed computing project]]s.
  
==Primality tests for numbers N without special form==
+
==Primality tests for numbers {{V|N}} without special form==
*[[wikipedia:Agrawal-Kayal-Saxena primality test|Agrawal-Kayal-Saxena (AKS) primality test]]: A new method which is very slow but it is provably the fastest for numbers with several million digits (so it is not useful for now).
+
*[[wikipedia:AKS primality test|Agrawal–Kayal–Saxena (AKS) primality test]]: A new method which is very slow but it is provably the fastest for numbers with several million digits (so it is not useful for now).
*[[Elliptic Curve Primality Test]] (ECPP): A method that provides a certificate that can be checked very fast.
+
*[[Elliptic curve primality test]] (ECPP): A method that provides a certificate that can be checked very fast.
*[[wikipedia:Adleman-Pomerance-Rumely Test|Adleman-Pomerance-Rumely Test (APR) and APR-CL (modification of the previous by Cohen and Lenstra)]]: A very fast primality test for numbers less than 10000 digits, especially with the improvements by Mihailescu. But ECPP is preferred because of the certificates it provides.
+
*[[Adleman–Pomerance–Rumely primality test|Adleman–Pomerance–Rumely Test (APR) and APR-CL (modification of the previous by Cohen and Lenstra)]]: A very fast primality test for numbers less than 10000 digits, especially with the improvements by Mihailescu. But ECPP is preferred because of the certificates it provides.
  
 
==Probable primality tests==
 
==Probable primality tests==
Line 27: Line 28:
 
==See also==
 
==See also==
 
*[[Primality testing program]]
 
*[[Primality testing program]]
[[Category:Primality tests]]
+
 
 +
[[Category:Primality tests| ]]

Latest revision as of 05:03, 11 August 2024

A primality test is a test that determines whether a given number is prime or composite. When the number is declared composite, the algorithm does not reveal the prime factors. That is the job of the factorization methods.

Some primality tests are really probable primality tests. When they determine that a number is composite, it really is, but otherwise we are not completely sure if it is prime because they fail for some input values. Combining several probable primality tests the confidence grows, but we cannot be completely sure that the number is prime until a primality test (which is far slower than a probable primality test except when the input number has a special form) is run on it.

When the number to be tested for primality is very large, making it impossible even to run probable primality tests on it, the only reasonable procedure is to run a factorization method which may reveal a small factor, showing that the number is composite. This is the purpose of trial factoring on GIMPS.

Since all primality tests use modular arithmetic, reading the modular arithmetic article is a prerequisite to understanding those methods.

Primality tests for numbers N with special form

Primality tests for numbers N without special form

Probable primality tests

See also