Fermat’s and Euler’s theorem, Primality testing

Fermat’s Little Theorem

Fermat’s Little Theorem, proposed by Pierre de Fermat, states that if

$p$ is a prime number and $a$ is an integer not divisible by $p$ , then

$a^{p - 1} \equiv 1 (mod p)$ . In other words:

$a^{p - 1} mod p = 1$

This theorem has several applications in number theory and cryptography, including primality testing and the RSA algorithm.

Euler’s Totient Theorem

Euler’s Totient Theorem, proposed by Leonhard Euler, states that if

$n$ is a positive integer and

$a$ is an integer coprime to

$n$ , then $a^{ϕ (n)} \equiv 1 (mod n)$ , where

$ϕ (n)$ is Euler’s totient function, which counts the number of positive integers less than

$n$ that are coprime to $n$ .

$a^{ϕ (n)} mod n = 1$

Euler’s Totient Theorem is a generalization of Fermat’s Little Theorem and has important applications in number theory, cryptography, and modular arithmetic.

Primality Testing

Primality testing is the process of determining whether a given number

$n$ is prime or composite. There are various algorithms and techniques for primality testing, each with different efficiency and accuracy. Some common methods include:

Trial Division: Check whether
$n$ is divisible by any integer

$a$ in the range

$2$ to

$n$ . If $n$ is divisible by any $a$ , then $n$ is composite; otherwise, it is prime. This method is simple but inefficient for large numbers.
Fermat Primality Test: Utilizes Fermat’s Little Theorem. Choose a random integer

$1 < a < n$ and check whether $a^{n - 1} \equiv 1 (mod n)$ . If the congruence holds, $n$ is likely prime; otherwise, it is composite. This test is fast but can produce false positives (composites mistakenly identified as primes) for certain composite numbers called Carmichael numbers.
Miller-Rabin Primality Test: An improved version of the Fermat Primality Test that reduces the probability of false positives. It repeatedly applies Fermat’s Little Theorem with randomly chosen bases $a$ and performs additional checks to enhance accuracy.
AKS Primality Test: A deterministic polynomial-time algorithm for primality testing, proposed by Agrawal, Kayal, and Saxena in 2002. It efficiently determines whether a given number $n$ is prime or composite without any probability of error.

Primality testing algorithms play a crucial role in cryptography, particularly in the generation of secure cryptographic keys and the implementation of cryptographic protocols.

Fermat’s Little Theorem and Euler’s Totient Theorem are important results in number theory with applications in cryptography, particularly in primality testing. Various primality testing algorithms, ranging from simple to sophisticated, are used to determine whether a given number is prime or composite, serving as a foundation for secure cryptographic systems.