AllPowers - hernandez.ku.edu

1 Course Digest for MATH 601 Spring 2022. Date Tuesday, March 8. Tasks Watch Lecture 13. Read , , in HSP. Practice Problem , (a), replacing the k there with the one furnished by Diffie-Hellman, as in lecture. Synopsis We started today's lecture with some remarks on Team Project 2, and on the recent Short Quiz 3. After this, we recalled the basics of the Diffie-Hellman Key Exchange, and the ElGamal cryptosystem. Note that there are many ways to tweak the ElGamal cryptosystem scheme that we presented in class, and this might be what you run across if you investigate it online, or in HSP. We went over some numerical examples, and then turned our attention to the Discrete Logarithm problem. We started by proving a simple theorem Let g be a primitive roots modulo an odd prime p, and suppose that x = a is a solution to the equation g x = A mod p, where A is nonzero modulo p. (1) x = a is even if and only if A(p 1)/2 1 mod p. (2) x = a is odd if and only if A(p 1)/2 1 mod p.

2 For this theorem to even make sense, we recalled with A(p 1)/2 must be either 1 or 1 modulo p, and then we went over the short proof. After this, we presented the Baby Step Giant Step algorithm for solving the Discrete Logarithm Problem, which is much faster than the naive, brute force method, but still, not good enough. We will start next lecture by recalling this algorithm, and discussing its correctness. We will also introduce RSA next time. Date Thursday, March 3. Tasks Explore Check out the Wikipedia pages for the discrete logarithm problem, Diffie-Mellman, and ElGamal. Watch Lecture 12. Read Skim Section , read Section , , , Skim and in HSP. Practice Problem , , Synopsis We started with Short Quiz 3, and after that, we returned, and briefly discussed, Team Project 1. After this, we recalled the definition of a primitive root modulo a prime, and the definition of the discrete logarithm function associated to such a primitive root. We also discussed the so-called discrete logarithm problem, highlighted a naive algorithm, and stated (but did not prove) that this problem is largely intractible.

3 After this, we started a general discussion of cryptography and cryptosystems/cryptoschemes, and went over a number of examples, including the Ceasar cipher (which many of you might have used as kids), and substitution/permutation ciphers ( , as in cryptoquote puzzles). We discussed the concept of a key, and after this, presented the Diffie-Hellman Key Exchange/ Key Generation method. After this, we discussed how to use the same ideas to describe the ElGamal cryptosystem. As we mentioned in class, the security of these processes are based on the fact that raising to powers/discrete logarithm is a trap-door process. Date Tuesday, March 1. Tasks Watch Lecture 11. Read HSP , , Practice Problem in HSP. For more practice, use the code that we displayed today in lecture to verify that b = 541 is a primitive root modulo the prime p = 997. Then use some version of the AllPowers function that we wrote today to find the discrete logarithm, with base b, of 858 modulo p.

4 That is, find x such that bx = 858. Synopsis After some announcements, including a description of the new team project, we introduced the notion of the order of a unit modulo n. Recall that if a is a unit modulo n, then the order of a is the smallest positive integer e such that ae 1 mod n. We discussed why this definition makes sense (Euler' s theorem ), and why it involves only units. We then used SageMathCell to compute some definitions of order, and based on these computations, we formulated the following Conjecture: If a is a unit modulo n, and then the order of a modulo n divides (n). This conjecture is, in fact, true, and we provided a proof. After this, we did some more numerical computations to illustrate this. After this, we defined what it means for an integer a that is nonzero modulo a prime p to be a primitive root modulo p. Recall that this is the case when the order of a is as large as possible, namely, p 1. We explained why this means that, if a is a primitive root modulo p, then every integer that is nonzero modulo p must be congruent to some power of a.

5 We then returned to our computations to produce lists of primitive roots modulo various primes, and stated (but unfortunately, will not prove) that primitive roots must exist modulo every prime. Using this, we introduced the notion of a discrete logarithm, and computed a small example. Date Thursday, February 24. Tasks Watch Lecture 10. Read HSP , , Practice Use a computer to answer, and check your answers to, the following. (1) Note that p = 83 satisfies p 3 mod 4. Determine whether a 17 or a 66. has square roots modulo p, and list these square roots. (2) Note that p = 2027 satisfies p 3 mod 4. Determine whether a 1234 or a 793 has square roots modulo p, and list these square roots. (3) Consider p = 311 and q = 211 are distinct primes, each congruent to 3 modulo 4. Set n = pq = 65621. The integer 55632 has 4 square roots modulo n, and they are of the form a and b for some a and b. Apply the CRT, and our technique for finding square roots modulo p and q, to solve for a and b.

6 Synopsis We started off the class by talking abut the teammate evaluation form. After this, we recalled the basics of square roots modulo special primes. We started by proving the following result, which we rushed at the end of our last lecture before Midterm 1. Lemma: If p 3 mod 4, then 1 has no square root modulo p. Building on this, we proved the following theorem : If p 3 mod 4, and a is an integer that is nonzero modulo p, then either a or a has square roots modulo p, but not both. In fact, whichever of a or a has p+1. square roots, the square roots must be y, where y = a 4 . We then went over a number of examples that explained how to use this theorem to calculate square roots modulo large-ish primes. After this, we discussed how to use the CRT, along with our understanding of square roots modulo primes congruent to 3 modulo 4, to construct square roots modulo integers of the form pq, where p and q are each prime, p 6= q, and both congruent to 3 modulo 4.

7 As an example, we calculated that the square roots of 71 modulo 77 are exactly 15 and 29. Date Tuesday, February 22. Tasks Watch Relax Read Relax Practice Relax Synopsis Today was Midterm 1. Date Tuesday, February 15. Tasks Watch Lecture 9. Read Section of Trappe-Washington Practice Start working on your team project. (1) Simplify 3104 mod 14. Hint: Apply Euler' s theorem . (2) Simplify 5454 mod 151 Hint: 151 is prime, so apply fermat 's Little theorem . Synopsis We started today's lecture with another standard quiz, and then presented a lengthy overview of the first group project, including giving a demonstration of the basics of Sage, conducted on SageMathCloud. See the course webpage for more information on all of this, or ask your classmates. For the math part of the lecture, we started by recalling Euler' s theorem , and then going over examples. We also presented an example of the main idea behind the proof of Euler' s theorem . After that, we transition to discussing square roots modulo p, and again examined the situation when p = 5 and p = 7.

8 After contrasting these situations, based on what we observed when p = 7, we produced the following Conjecture: If p is a prime that is congruent to 3 modulo 7, then the following hold.. (1) 1 has no square root modulo p, , 1 does not exist modulo p. (2) For every a that is nonzero modulo p, either a or a has a square root, but not both! We proved the first part of this conjecture, and will tackle the second part next time. Date Thursday, February 10. Tasks Explore For fun, skim the Wikipedia article on Euler's Totient Function. Watch Lecture 8. Read Read Section of Trappe-Washington, which starts on page 86 of that book, and which covers some basics of square roots modulo. Practice . (1) Apply CRT twice to solve the system x 5 mod 5, x 2 mod 6, x 4 mod 7. (2) Prove that if a is a unit modulo m, and ax = ay mod m, then x y mod m. Show that this can be false if a is not a unit modulo m. Hint: For the second part, we gave an example of this in our proof of Euler' s theorem .

9 (3) Verify that (14) = 6, and so there are six units modulo 14. Write these down, and label them u1 , .. , u6 in order. Note that a = 3 is a unit modulo 14, so it must be one of the ui . Compute the values of au1 , au2 , .. , au6 modulo 14, and verify that you get a re-arranging of the original list u1 , .. , u6 . Note: This is the key idea in the proof of Euler' s theorem . (4) Verify that Euler' s theorem is true for each of the elements in Z/14Z. That is, verify that x6 1 for each x that is a unit modulo 14. Synopsis We started off discussing how to iteratively apply the Chinese Remainder Theo- rem to solve simple systems of congruences, provided that the moduli were relatively prime. After this, we discussed how to apply CRT to solve for square roots modulo m. For example, we saw how to use CRT to find the 4 square roots of 1 modulo 15. After this, we introduced Euler's Function, which is also often called Euler's Totient Function, or more simply, Euler's Phi Function.

10 The definition was simple. Definition: If n is a positive integer, then (n). is the number of units modulo n, that is, the number of integers 1 a n 1 such that gcd(a, n) = 1. We went over lots of examples of this function, and also saw observed how erratic its graph looks like. We proved that (p) = p 1 when p is prime, and that if p, q are distinct primes, then (pq) = (p 1)(q 1). You will explore a generalization of this in the first group assignment. We concluded the lecture by proving Euler' s theorem : If a is a unit modulo n, then a (n) 1 mod n. Date Tuesday, February 8. Tasks Watch Lecture 7. Read Section in HSP. Practice Note that the CRT does not appear until later in HSP. (1) Solve the system x = 4 mod 5 and x = 6 mod 17. Note: It is easy to check your solution, so please do so. (2) Solve the system x = 38 mod 60 and x = 7 mod 11. Note: It is easy to check your solution, so please do so. (3) Challenge: If m, n, l are positive integers that are pairwise relatively prime ( , any two of them are relatively prime), then can you solve a system of the form x = a mod m, x = b mod n, x = c mod l for any choices of a, b, c?