Fermat's little theorem
The small Fermat's theorem, or " the little Fermat ", is a theorem in number theory. He makes a statement about the properties of prime numbers and was erected in the 17th century by Pierre de Fermat. The sentence describes the general congruence:
Wherein a is an integer and p is a prime number ( the other symbols are described in the article congruence ).
If a is not a multiple of p, can be the result in the commonly used form
Bring.
Evidence
The theorem can be proved by induction on or be construed as a special case of the theorem of Lagrange from the group theory. This says that every group element to the power of the (finite) group order the unit element results.
See: proof of Fermat's little theorem in the proof Archives
Conclusion by Euler
The third binomial formula states:
Referring now an odd prime number and an arbitrary integer. If a divider is comprised of, it follows from the Fermat's little theorem, that the right side of the equation is a multiple of the prime. This is one of the factors is a multiple of.
It is therefore
This conclusion is attributed to Leonhard Euler.
Generalization
One can generalize the Fermat's little theorem to Euler's theorem.
For two relatively prime integers n and a
The Euler φ - function referred. This returns the number of integers between 1 and n- 1 which are relatively prime to n. If n is a prime number, then, so that one gets Fermat's little theorem as a special case.
Application as a primality test
After the small Fermat's theorem is true for any prime p and each to prime a:
With an integer k This relationship can also be a composite number p and a number a, 1
For a number p with 100 or more points, however, a prime factorization is possible only with more efficient methods such as the quadratic sieve.
The sentence can therefore be used in its inversion to determine with great certainty whether a number is prime.
For large numbers with over 100 positions will be practically impossible to doubt that p is a prime number, if the equation for some a, 1
However, the examination of all values 1 < a < p-1 would be necessary for an exact proof, so that the trial division is more efficient in this case.
It is not known that a 100 -digit or greater number could be factored in this manner.
For some special numbers such exceptions may, however, be found more frequently.
Let n be the product of two large prime numbers p and q.
We consider a number x with 1 < x
Applies.
This raises the question whether this equation is already satisfied for smaller exponents.
The quantum part of Shor algorithm for factoring large numbers used to calculate the smallest number r for which this equation holds.
The classical part of this algorithm can be easily performed on almost any computer.
When one considers the magnitude of a number in the modulo operation, these are repeated in cycles.
This is unavoidable, since only the values 1, 2, 3, ..., n-1 can be adopted.
We consider this an example of smaller numbers.
We can restrict ourselves to the consideration of prime numbers, since the minimum cycle length results for the product of the least common multiple of the cycle lengths for the factors.
And so on.
The table was calculated from.
In order to avoid large numbers, one can calculate the result of easier.
In this example, with results for the following cycle of the values
For results
For all three bases 2, 3 and 5, with number 7
Or generally
For all and all natural a, for which it holds.
This is a direct consequence of the small set of Fermat.
The example of modulo values for it can be seen that the algorithm can be shortened when the cycle is shorter.
There is also, i.e..
For larger numbers can be saved as work.
If p has the form arise further simplification of the calculation.
This is demonstrated with p = 17 shows.
Since p -1 = a multiple of the cycle length is eligible for r only the numbers 2, 4, 8 and 16 into account, which can reduce the computational effort, especially for very large p significantly.
Even less work makes the case
Since the result then is fixed for the next power of 2 already as one.
Shor algorithm
Further simplification