0:00

We've established that determining the prime factorization of

Â a large randomly chosen integer

Â is not as easy as just performing trial division by all potential prime factors.

Â Or even using more sophisticated factorization algorithms,

Â such as the general number field sieve.

Â The reason is that none of these algorithms scale sufficiently as the size

Â of the number grows.

Â And as a consequence, we can always choose numbers that are large enough, but

Â these techniques are infeasible to carry out in a meaningful time frame.

Â In fact for cryptanalytic purposes,

Â that is precisely the goal that we want to achieve.

Â But in situations where we aren't interested in finding the actual factors,

Â just whether or

Â not non-trivial factors exist, we have some powerful tools at our disposal.

Â In this lesson, we will look at one of the simplest which is Fermat's Primality Test.

Â This test is probabilistic, meaning that when we perform the test,

Â it will not actually tell us definitively if the number is prime.

Â In fact, it isn't really a primality test as much as it is a compositeness test.

Â In that if it tells us that a number is composite, then we know for

Â a fact that it is, and hence not prime.

Â But the alternate outcome is only that it fails to establish that the number is

Â composite, which only implies that it might be prime, not that it must be.

Â To understand the sense of this, imagine an even simpler primality test,

Â Bob's primality test.

Â This test says that if you choose a random number greater than two and

Â if the number is even, then it is composite, without a doubt.

Â If the number is odd, however, it only tells you that the number

Â might not be composite or equivalently that it might be prime.

Â 1:56

If a and p are relatively prime, then a has a multiplicative inverse, mod p, and

Â this can then be rewritten as a raised to the p- 1 power is congruent to 1 (mod p).

Â This should look familiar since it is a special case of Euler's Totient Theorem.

Â So how do we construct a primality test from this?

Â After choosing a random candidate for p, we pick a value for a that is less than 8.

Â We can't chose 0 since 0 is not relatively prime to any number, including p.

Â We could choose 1, but this trivially satisfies the relation and so

Â tells us nothing.

Â Similarly, since p is going to be an odd number,

Â since two is the only even prime and two would be a rather poor choice for

Â a cryptographically useful prime number, then p- 1 will be even.

Â And hence choosing a = -1, which is congruent to p- 1 (mod p),

Â will also truly satisfy the relation.

Â So we pick a value for a such that it lies strictly between 1 and p- 1.

Â We evaluate a raised to the p- 1 and see if the result is congruent to 1.

Â If is not, then we have established that p is a composite number and

Â the value a is known as a Fermat witness to that fact.

Â But if the result is congruent to 1, then we have two possibilities.

Â Either p really is prime which is what we're hoping for, or p is actually

Â composite and this particular choice of a for the base failed to detect it.

Â When this happens, p is known as a Fermat pseudoprime to the base a,

Â or just a pseudoprime to the base a, and

Â the value a is known as a Fermat liar for this value of p.

Â For a concrete example, let's say that we randomly pick p = 15.

Â And for the moment, let's assume that this value is too large for

Â us to even attempt to factor, but we want to see if it is prime.

Â So we randomly choose a value of a that's equal to 4 and

Â calculate 4 to the 14 (mod 15) = 1.

Â We discover that it is indeed congruent to 1, so 15 might be prime.

Â But since we know that it might not be, we hedge our bets and

Â pick another value of a and choose 2.

Â 2 to the 14th power (mod 15) is congruent to 4.

Â So this proves that 15 is composite and 2 is a Fermat witness for 15.

Â But since it passed the test for a for a base of 4,

Â we call 15 a Fermat pseudoprime to the base 4 and 4 is a Fermat liar for 15.

Â In general, the more bases we choose to test,

Â the more likely we are to find a Fermat witness should p not be prime.

Â But this isn't guaranteed, and in fact, It's actually possible to find a number

Â that is pseudoprime for every possible choice of a.

Â For these numbers, we could exhaustively test every possible base and

Â conclude that the number almost has to be prime.

Â These numbers are called Carmichael numbers and

Â the smallest such number is 561.

Â While there are infinitely many Carmichael numbers,

Â they're actually pretty rare in comparison to the non-Carmichael pseudoprimes.

Â Hence the odds are well in our favor that if we test a number against

Â a lot of bases and we do not find a Fermat witness, that the number is prime.

Â Because the Fermat test is simple,

Â it is often done as the first in a suite of tests.

Â The idea to quickly rule out most selections as being not prime and

Â then carrying out better, and usually slower, tests on the survivors

Â to further increase the confidence in the primality of the number.

Â But this isn't always the case and there are some mainstream cryptographic

Â protocols that rely on Fermat's primality test alone to choose prime numbers.

Â 5:47

Even when this is the case,

Â however, the Fermat test usually isn't the first screening that is performed.

Â Recall that the expected density of prime numbers around the value n

Â is about 1 over the natural log of n.

Â So for a 500-bit prime,

Â we have about a 1 in 350 chance that a randomly selected number is prime.

Â But if we pick a prime number and discard it if it is even and

Â keep doing this until we have an odd number,

Â then we now have about a 1 in 175 chance of this number being prime.

Â If we then check to see if the number is divisible by 3, we only made it

Â a third of the remaining numbers, leaving us with two-thirds of the prior half of

Â the numbers we might choose, which gets us down to a chance of about 1 in 120.

Â We can keep screening our numbers using successfully larger primes and

Â improve our odds at each step.

Â But at some point, fairly quickly, we reach a point of diminishing returns.

Â Since performing trial division by a small handful of prime numbers is relatively

Â cheap, we might choose to check the first 15 primes,

Â which are the prime numbers less than 50.

Â This will improve our chances to about 1 in 50.

Â It probably isn't worth going much further than this.

Â For instance, if we screen against the 95 prime numbers less than 500,

Â we only further improve our odds to about 1 in 30.

Â One technique that is sometime used to improve our overall performance is to

Â use a number sieve on a segment of the number line,

Â starting with the random number that we chose.

Â Imagine picking a random 500-bit number and

Â then setting up an array having, say, 35,000 entries.

Â Each entry only needs to hold the single bit that tells us

Â that whether the corresponding number is composite or not.

Â The first element corresponds to our chosen number and

Â the next element to the next number after, and so on.

Â We expect there to be about 100 prime numbers within this range.

Â We then walk through the range marking off every nth number for

Â the first prime numbers, being sure to start at an appropriate place

Â based on the residue of our chosen number modulo each prime.

Â This is a very fast and efficient algorithm for

Â limiting a significant fraction of the potential values.

Â After we have sieved the multiples of the first k primes,

Â where perhaps k is several hundred, we then perform a preset

Â number of Fermat primarily test on each unmarked entry until we find one that

Â fails to produce any Fermat witnesses for that preset number of tests.

Â We don't need to pick our bases randomly either.

Â We can, but

Â it's not uncommon to just walk up the prime numbers up to some maximum number.

Â And frequently, we only test half a dozen or so, before we reach a point

Â where we're comfortable saying, we think this number's prime.

Â If it weren't for the existence of the Carmichael numbers,

Â it's highly likely that nearly every protocol would rely on on Fermat's

Â primality test to choose large prime numbers.

Â Unfortunately, they do exist.

Â And this prevents us from making strong statements about the probability that our

Â random number is prime, based on how thoroughly we tested it.

Â To achieve this,

Â we perform further testing, using different algorithms that allow us to

Â place strong probabilistic limits on the likelihood that our number is prime.

Â The first of these tests is the Miller-Rabin test,

Â which we'll talk about in the next lesson.

Â