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 "Fermat pseudoprimality test"

From Prime-Wiki
Jump to: navigation, search
(restored)
 
(Adding to new subcategory)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 
The '''Fermat pseudoprimality test''' is based on the Fermat Little Theorem that states:
 
The '''Fermat pseudoprimality test''' is based on the Fermat Little Theorem that states:
:<math>a^{p-1}\equiv 1</math> (mod <math>p</math>)
+
:<math>a^{p-1}\equiv 1\,\pmod{p}</math>
where <math>p</math> is a [[prime number]] and <math>a</math> is not multiple of <math>p</math>.
+
where ''p'' is a [[prime]] number and ''a'' is not multiple of <math>p</math>.
  
When testing the number <math>N</math>, we perform <math>a^{N-1}\equiv 1</math> (mod <math>N</math>). If the result is not 1, the number must be composite. Otherwise the number is either a prime or a Fermat [[pseudoprime]] with respect to base <math>a</math>.
+
When testing the number ''N'', we perform <math>a^{N-1}\equiv 1\,\pmod{N}</math>. If the result is not 1, the number must be composite. Otherwise the number is either a prime or a Fermat [[pseudoprime]] with respect to base <math>a</math>.
  
In the last case several tests are performed in order to increase the confidence that the number is not composite. But there are some numbers, known as Carmichael numbers, for which the result is 1 whenever the numbers <math>a</math> and <math>N</math> are [[coprime]]. The smallest Carmichael number is 561.
+
In the last case several tests are performed in order to increase the confidence that the number is not composite. But there are some numbers, known as Carmichael numbers, for which the result is 1 whenever the numbers ''a'' and ''N'' are [[coprime]]. The smallest Carmichael number is 561.
  
 
At any rate, it is much better to perform the [[Miller-Rabin pseudoprimality test]] which run in the same computational complexity, and which does not have the equivalent of Carmichael numbers.
 
At any rate, it is much better to perform the [[Miller-Rabin pseudoprimality test]] which run in the same computational complexity, and which does not have the equivalent of Carmichael numbers.
  
 
==External links==
 
==External links==
*[https://en.wikipedia.org/wiki/Fermat_primality_test Wikipedia]
+
*[[Wikipedia:Fermat_primality_test|Wikipedia]]
[[Category:Primality tests]]
+
 
 +
[[Category:Probabilistic primality tests]]

Latest revision as of 01:19, 11 August 2024

The Fermat pseudoprimality test is based on the Fermat Little Theorem that states:

[math]\displaystyle{ a^{p-1}\equiv 1\,\pmod{p} }[/math]

where p is a prime number and a is not multiple of [math]\displaystyle{ p }[/math].

When testing the number N, we perform [math]\displaystyle{ a^{N-1}\equiv 1\,\pmod{N} }[/math]. If the result is not 1, the number must be composite. Otherwise the number is either a prime or a Fermat pseudoprime with respect to base [math]\displaystyle{ a }[/math].

In the last case several tests are performed in order to increase the confidence that the number is not composite. But there are some numbers, known as Carmichael numbers, for which the result is 1 whenever the numbers a and N are coprime. The smallest Carmichael number is 561.

At any rate, it is much better to perform the Miller-Rabin pseudoprimality test which run in the same computational complexity, and which does not have the equivalent of Carmichael numbers.

External links