Number Theory Il 3.3 Fermat's Theorem A remaining challenge in using Turing s code is that decryption requires the inverse of the secret key k. But how can we find an inverse of k? One approach is to rely on Fermats Theorem which is much easier than his famous last theorem - and more useful Theorem 6(Fermat's Theorem). Suppose p is a prime and k is not a multiple of p. Then Imo Proof. We reason as follows 1·2·3…(p-1)≡( k rem p)·(2 e ren p).(3 k rem p)…(P-1) k rem p)(modp) ≡k·2k·3k…(p-1)k(modp) k lod The expressions on the first line are actually equal, by Corollary 5, so they are certainly congruent modulo p. The second step uses part 1 of Lemma 2. In the third step, we rearrange terms in the product Now (p-1)! can not be a multiple of p, because the prime factorizations of 1, 2, ..,(p 1)contain only primes smaller than p. Therefore, we can cancel (p-1)! from the first expression and the last by lemma 4, which proves the claim Here is how we can find inverses using Fermat's Theorem Suppose p is a prime and k is not a multiple of p. Then, by Fermat's Theorem, we know that kP2·k≡1(modp) Therefore, kp- must be a multiplicative inverse of k For example, suppose that we want the multiplicative inverse of 6 modulo 17. Then we need to compute 6 rem 17, which we can do by successive squaring. All the congruences below hold modulo 17 62≡36≡2 64≡(62)2=22=4 615≡68.64.62.6≡16.4.2.6≡3 Therefore, 6 5 rem 17=3. Sure enough, 3 is the multiplicative inverse of 6 modulo 17, 3.6≡1(mod17) e In general, i we were working modulo a prime p, finding a multiplicative inverse by ng every value between 1 and p-l would require about p operations. However, the approach above requires only about log p operations, which is far better when p is largeNumber Theory II 9 3.3 Fermat’s Theorem A remaining challenge in using Turing’s code is that decryption requires the inverse of the secret key k. But how can we find an inverse of k? One approach is to rely on Fermat’s Theorem, which is much easier than his famous Last Theorem— and more useful. Theorem 6 (Fermat’s Theorem). Suppose p is a prime and k is not a multiple of p. Then: kp−1 ≡ 1 (mod p) Proof. We reason as follows: 1 2 3 · · · · ·(p − 1) ≡ (k rem p) · (2k rem p) · (3k rem p)· · ·((p − 1)k rem p) (mod p) ≡ k · 2k · 3k · · ·(p − 1)k (mod p) ≡ (p − 1)! kp−1 · (mod p) The expressions on the first line are actually equal, by Corollary 5, so they are certainly congruent modulo p. The second step uses part 1 of Lemma 2. In the third step, we rearrange terms in the product. Now (p−1)! can not be a multiple of p, because the prime factorizations of 1, 2, . . . ,(p− 1) contain only primes smaller than p. Therefore, we can cancel (p − 1)! from the first expression and the last by Lemma 4, which proves the claim. Here is how we can find inverses using Fermat’s Theorem. Suppose p is a prime and k is not a multiple of p. Then, by Fermat’s Theorem, we know that: kp−2 · k ≡ 1 (mod p) Therefore, kp−2 must be a multiplicative inverse of k. For example, suppose that we want the multiplicative inverse of 6 modulo 17. Then we need to compute 615 rem 17, which we can do by successive squaring. All the congruences below hold modulo 17. 62 ≡ 36 ≡ 2 64 ≡ (62 ) 2 ≡ 22 ≡ 4 68 ≡ (64 ) 2 ≡ 42 ≡ 16 615 ≡ 68 64 62 · · · · · 6 ≡ 16 · 4 2 6 ≡ 3 Therefore, 615 rem 17 = 3. Sure enough, 3 is the multiplicative inverse of 6 modulo 17, since: 3 6 · ≡ 1 (mod 17) In general, if we were working modulo a prime p, finding a multiplicative inverse by trying every value between 1 and p − 1 would require about p operations. However, the approach above requires only about log p operations, which is far better when p is large