Fermat's primality test

2016-06-09T22:05:00Z

2602:306:CE33:B4A0:D92E:E6D3:EFD5:E27D:

'''Fermat's primality test''' is an [[algorithm]]. It can test if a given number ''p'' is probably [[prime number|prime]]. There is a [[flaw]] however: There are numbers that pass the test, and that are not prime. These numbers are called [[Carmichael number]]s.

==Concept==
[[Fermat's little theorem]] states that if ''p'' is prime and <math>1 \le a < p</math>, then

:<math>a^{p-1} \equiv 1 \pmod{p}</math>.

If we want to test if ''n'' is prime, then we can pick random ''a'''s in the [[interval]] and see if the [[equation]] above holds. If the equality does not hold for a value of ''a'', then ''n'' is [[composite number|composite]] (not prime). If the equality does hold for many values of ''a'', then we can say that ''n'' is probably prime, or a [[pseudoprime]].

It may be in our tests that we do not pick any value for ''a'' such that the equality fails. Any ''a'' such that

:<math>a^{n-1} \equiv 1 \pmod{n}</math>

when ''n'' is composite is known as a ''Fermat liar''. If we do pick an ''a'' such that

:<math>a^{n-1} \not\equiv 1 \pmod{n}</math>

then ''a'' is known as a ''Fermat witness'' for the compositeness of ''n''.

''<math>\pmod n</math>'' is the [[Modular arithmetic|modulo]] operation. Its result is what remains, if p is divided by n. As an example,

:<math> 5 \equiv 2 \pmod 3</math>.

==What this test is used for==
The [[RSA algorithm]] for [[Public-key cryptography|public-key encryption]] can be done in such a way that it uses this test. This is useful in [[cryptography]].

[[Category:Computer science]]
[[Category:Number theory]]

TCS Wiki - User contributions [en]

Fermat's primality test