Vipul at 23:26, 4 January 2012

2012-01-04T23:26:55Z

← Older revision		Revision as of 23:26, 4 January 2012
Line 3:		Line 3:
	==Definition==		==Definition==

	The '''Fermat primality test''' is a quick and often inconclusive [[primality test]]. In the version below, we consider only <math>n > 2 </math>.		The '''Fermat primality test''' is a quick and often inconclusive [[primality test]]. In the version below, we consider only <math>n > 1</math>.

	Given a [[natural number]] <math>n > 2</math>, the test works as follows:		Given a [[natural number]] <math>n > 1</math>, the test works as follows:

	# Pick a random element <math>a</math> from the congruence classes of integers mod <math>n</math> (exclude the congruence ~~classes~~ of 0 ~~and 1~~). Explicitly, pick <math>a</math> as an integer among <math>2,3,\dots,n-1</math>.		# Pick a random element <math>a</math> from the congruence classes of nonzero integers mod <math>n</math> (exclude the congruence class of 0). Explicitly, pick <math>a</math> as an integer among <math>1,2,3,\dots,n-1</math>.
	# Check whether <math>a^{n-1} \equiv 1 \pmod n</math>. To compute the power use [[repeated squaring]]. If the condition does ''not'' hold, then <math>n</math> is composite. If the condition ''does'' hold, then <math>n</math> may be prime or composite.		# Check whether <math>a^{n-1} \equiv 1 \pmod n</math>. To compute the power use [[repeated squaring]]. If the condition does ''not'' hold, then <math>n</math> is composite. If the condition ''does'' hold, then <math>n</math> may be prime or composite.

Vipul: Created page with "{{primality test}} ==Definition== The '''Fermat primality test''' is a quick and often inconclusive primality test. In the version below, we consider only $n > 2$
2012-01-04T23:23:37Z

Created page with "{{primality test}} ==Definition== The '''Fermat primality test''' is a quick and often inconclusive primality test. In the version below, we consider only <math>n > 2 </..."

New page
{{primality test}}

==Definition==

The '''Fermat primality test''' is a quick and often inconclusive [[primality test]]. In the version below, we consider only <math>n > 2 </math>.

Given a [[natural number]] <math>n > 2</math>, the test works as follows:

# Pick a random element <math>a</math> from the congruence classes of integers mod <math>n</math> (exclude the congruence classes of 0 and 1). Explicitly, pick <math>a</math> as an integer among <math>2,3,\dots,n-1</math>.
# Check whether <math>a^{n-1} \equiv 1 \pmod n</math>. To compute the power use [[repeated squaring]]. If the condition does ''not'' hold, then <math>n</math> is composite. If the condition ''does'' hold, then <math>n</math> may be prime or composite.

The above is a ''single iteration'' of the test. Multiple iterations of the test may be carried out with multiple random elements. If at any stage the condition <math>a^{n-1} \equiv 1 \pmod n</math> is violated, we can conclude that the number is composite. If, however, the condition holds every time, the situation is inconclusive and <math>n</math> may be prime or composite.

==Theory==

===Why it works===

The primality test above is correct because of [[Fermat's little theorem]], which says that for a prime <math>p</math> and <math>a</math> relatively prime to <math>p</math>, we have:

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

===Behavior on composite numbers===

For any composite number <math>n</math>, we use the following terms:

* A [[Fermat witness]] for <math>n</math> is a value <math>a</math> such that <math>a^{n-1} \not \equiv 1 \pmod n</math>.
* A [[Fermat liar]] for <math>n</math> is a value <math>a</math> such that <math>a^{n-1} \equiv 1 \pmod n</math>.
* We say that <math>n</math> is a [[Fermat pseudoprime]] to base <math>a</math> if <math>a</math> is a Fermat liar for <math>n</math>.

Nonzero numbers that have a common factor with <math>n</math> ''always'' serve as Fermat witnesses. There are <math>n - \varphi(n) - 1</math> of these where <math>\varphi</math> is the [[Euler totient function]]. For <math>n</math> composite, this number is ''at least'' equal to <math>\sqrt{n} - 1</math>, the worst case arising when <math>n</math> is a square of a prime. In general, if <math>n</math> has a small number of large prime factors, there are very few such numbers and a uniform random choice is highly unlikely to hit them.

For the numbers that are relatively prime to <math>n</math>, we have the [[formula for probability of relatively prime integer being a Fermat liar]]. If the probability is 1, then <math>n</math> is a [[Carmichael number]]. If the probability is less than 1, then it is at most 1/2, which means that the Fermat primality test can find a witness with arbitrarily high probability of success in a finite number of trials.

==Related tests==

* [[Miller-Rabin primality test]]
* [[Solovay-Strassen primality test]]