NT01_L05 - HackMD

--- title: NT01_L05 tags: Number Theory, NT01 description: Primality Test type: slide slideOptions: theme: sky --- ###### tags: `Number Theory` `NT01` # L05 Primality Test --- ## Last Week - Problem with Private Keys - Public-Key Cryptography - Python for Basic Diffie-Hellman --- This week - Fermat's Little Theorem - Miller-Rabin Primality test - Python Implementation of Miller-Rabin Test --- # 1.1 Fermat's Little Theorem (FLT) This week we are starting on a harder challenge, to test whether a number is a prime. This is a unsolved task that many mathematisians are still working on it. But we have collected some good ideas! * ***Fermat's Little Theorem***: Let p be a prime. If an integer a is coprime with p, then $a^{p-1} \cong 1\ mod\ p$. Also for all a, $a^p \cong a\ mod\ p$ ***Proof: (optional)*** As gcd(a, p) = 1, a is invertible in $\ Z_p^*$, thus a: $\ Z_p^* ↦ Z_p^*$ is injective, so bijective as both domain and image have finite and identical cardinality. So we have $$a ⋅ 2a\cdot \dots \cdot (p-1)a ≅ (p-1)!\ mod\ p$$ $$\implies (p-1)! \cdot a^{p-1} \cong (p-1)!\ mod\ p$$ $$\implies a^{p-1} \cong 1\ mod\ p$$, As $gcd((p-1)!, p) = 1$. The second statement follows for all a. $\blacksquare$ ---- 1.2 Human Language Please! The Fermat's Little Theorem would be more meaningful if we focus one those numbers smaller than p. Which means, if we choose a prime p, for any number smaller than it, if we multiply this number itself p-1 time, it will back to 1 in mod p, and it will back to itself if we do one more such multiplication. ---- 1.3 But Be Careful about the wording here! 1. Given big integer n, randomly choose a number g smaller than it, try to get gcd(g, n). 2. If gcd(g,n) > 1, then n is not prime; else if gcd(g, n) = 1, we move to next step; 3. Check if $g^{n-1} ≅ 1\ mod\ n$, if not, We say n is not prime. As you can see from the process above, the Fermat's Little Theorem can only ensure us a number "**Is not prime**" if the number voliate the Theorem. But it cannot give us certainty on those numbers who follow the condition but is composite!! What? is that True?! ---- 1.4 Carmichael numbers There exist composite numbers n, called ***Carmichael numbers***, with the property that agree with all the condition in FLT. > An example of such a Carmichael number is n = 561, which is composite (561 = 3 · 11 · 17) And, $25^{560} \cong 1\ mod\ 561$ (We will check thi with python later) So we might mistakenly believe that 561 is a prime, if we only use FLT! --- # 2.1 A story of Detection One risk of FLT test is that we only checked two condition under primality, i.e. 1). gcd(g, n) = 1; 2). $g^{n-1} ≅ 1\ mod\ n$. It is like a detective collected some clue and feature about the criminal, like, 1. it was him; 2. 180cm height; Can we say that all male with 180cm height are criminals? Well, Carmichael number would be such a unlucky and innoncent guy if we judge like that. ---- # 2.2 More Clues needed The common logic under this situation is to find out more condition/features for the 'real primes', the more features(clues) we tested, we are more likely to indentify these real ones, and reduce the chance of arrest innocent guys. So what feature we can add here and also closed to our knowledge from FLT? * FLT tells us that $g^{n-1} ≅ 1\ mod\ n$, if n is prime. But 1 is so special in the multiplicative group. As from the entire group of modular n, only 1 and -1, who multiply themselves, can get to 1! Indeed, 1*1 = 1 and $-1 \cdot -1 = 1$. (Note: The proof of this statement is optional, will be provided in Week10's Math Story.) * So if one innocent guy accidently fit our guess at $g^{n-1} ≅ 1\ mod\ n$, how about $g ^{\frac{n-1}{2}} \cong 1\ or\ -1$? So we are not just test (n-1) power, but many steps of squre root, if n is indeed a prime, at least one of those square root should be -1! Otherwise, if none of them $\cong -1\ mod\ n$, they must be composite! ---- # 2.3 More Cool thing about this new idea * One more cool thing, for any big prime, it must be odd! then this big prime can be writen as a form $p = 2^k\cdot o + 1$, So $2^k$ is a even power, o is whatever odd number! * So rather than test $g^{n-1}$, we write $n-1=2^k \cdot o$, so we test $g^{2^k \cdot o}$, $g^{2^{k-1} \cdot o}$, $g^{2^{k-2} \cdot o}, \dots g^{o}$. To satisfy primality, at least one of this $≅ -1\ mod\ n$, otherwise, composite. Have you seen the cool part? > we do not need to do too many "power raising" Calculation, we only need $a_1 = g^o$, then $a_2 = a_1^2, a_3 = a_2^2$, $\dots$