| Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3). |
| Topics | Help • Register • News • History • How to • Sequences statistics • Template prototypes |
Difference between revisions of "Fermat pseudoprimality test"
(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>a^{p-1}\equiv 1\,\pmod{p}</math> |
| − | where | + | where ''p'' is a [[prime]] number and ''a'' is not multiple of <math>p</math>. |
| − | When testing the number | + | 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 | + | 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== | ||
| − | *[ | + | *[[Wikipedia:Fermat_primality_test|Wikipedia]] |
| − | [[Category: | + | |
| + | [[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.
