Understanding Primality Testing and Fermat's Little Theorem

What does primality testing means? Describe how little fermar's theorem test for prime numbers with suitable example. A primality test is a test to determine whether or not a given number is prime, as opposed to actually decomposing the number into its constituent prime factors (which is known as prime factorization). Primality tests come in two varieties: deterministic and probabilistic. Deterministic tests determine with absolute certainty whether a number is prime. Examples of deterministic tests include the Lucas-Lehmer test and elliptic curve primality proving Probabilistic tests can potentially. (although with very small probability) falsely identify a composite number as prime (although not vice versa). However, they are in general much faster than deterministic tests. Numbers that have passed a probabilistic prime test are therefore properly referred to as probable primes until their primality can be demonstrated deterministically. Fermat's Little Theorem: If p is prime and a is an integer not divisible by p, then ap-11 (mod p). Furthermore, for every integer a we have a= a (mod p). Remark: Fermat's little theorem tells us that if a e zy, then an-1-1 Example: Find 7222 and 11. Solution: We can fermat's little theorem to evaluate 72 mod 11 rather than using the fast modular exponentiaion algorithm. By Fermat's little theorem we know that 70 (mod 11), so (7101 (mod 11) for every positive integer k. To take advantage of this last congruence, we divide the exponent 222 by 10, findings that 222 22. 10+2. We know see that 7222 + 72.10+2 (710) 72 = (1)22.495 (mod 11) If follow that 7222 mod 11 = 5 Example 9 Illustrated how we can use Fermat's little theorem compute a mod p, which p is prime and p xa: First, we use the division algorithm to find the quotient q and remainder r when n is divided by p-1, so that n = q (p-1)+r where 0≤r(lessthan)p-1. It follows that aa (p-1)+r=(a-1) ar1qarar (mod p). Henos to find a mod p, we only need to compute a mod p. We will take advantage of the simplification many times in our study of number theory.