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
(link corr.)
m
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 10: Line 10:
 
*[[Lucas primality test|Lucas Test]]: Used when the number N-1 is completely factored.
 
*[[Lucas primality test|Lucas Test]]: Used when the number 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 N-1 must be less than the [[square root]] of 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).
+
*[[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).
 
*[[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.
 
*[[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.
 
*[[Lucas-Lehmer test]]: Used in [[GIMPS]]
 
*[[Lucas-Lehmer test]]: Used in [[GIMPS]]
 
*[[Pépin's test]]: Used to test primality in Fermat numbers.
 
*[[Pépin's test]]: Used to test primality in Fermat numbers.
*[[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]].
+
*[[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]].
  
 
==Primality tests for numbers N without special form==
 
==Primality tests for numbers N without special form==

Revision as of 10:30, 6 February 2019

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