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
m (Main page of category)
m (Using internal link)
 
Line 20: Line 20:
 
*[[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).
 
*[[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 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.
+
*[[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==

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