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

Fermat pseudoprimality test

From Prime-Wiki
Revision as of 15:23, 28 January 2019 by Karbon (talk | contribs) (restored)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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

[math]\displaystyle{ a^{p-1}\equiv 1 }[/math] (mod [math]\displaystyle{ p }[/math])

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

When testing the number [math]\displaystyle{ N }[/math], we perform [math]\displaystyle{ a^{N-1}\equiv 1 }[/math] (mod [math]\displaystyle{ 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 [math]\displaystyle{ a }[/math] and [math]\displaystyle{ N }[/math] 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