Welcome to Mathematical Foundations for Cryptology. This is the second course in the undergraduate introduction to applied cryptology specialization. Modern cryptographic systems, particularly public key systems based on asymmetric cryptographic algorithms, rely heavily on certain topics from the field of discrete mathematics. That allow us to design problems that are efficiently solvable if you have a small amount of critical information, but astronomically difficult to solve if you don't. The purpose of this course is to provide you with sufficient grounding in integer and modular arithmetic so that you can understand and work with these algorithms. The main topics we will be covering include the basic notion of divisibility in prime numbers, as well as what the greatest common divisor is and how to find it using the Euclidean Algorithm. We'll see that while division is not defined in modular arithmetic, multiplicative inverses are. But they have some non-intuitive properties and don't always exist. When they do exist, we'll learn how to use the Extended Euclidean Algorithm to find them. We'll explore the extremely important topic of Modular Exponentiation and see how the totient of the modulus is critical being able to work efficiently with exponents, which live in a different modular world. Will also learn about discrete logarithms and the Chinese Remainder Theorem. Finally, we'll consider the difficulty of factoring large integers in determining whether a large number is prime. So let's look at how these are broken up into the four modules that make up this course. In the first module, we'll cover the core concepts of discrete math. We'll first look at key integer concepts, such as divisibility and prime numbers, and learn how to use the Euclidean Algorithm to find the greatest common divisor of two integers. We'll then learn about the principles of modular arithmetic, and with that in hand, turn to the notion of multiplicative inverses in modular arithmetic world. And see that we can extend the Euclidean Algorithm to find these inverses. In the second module, we'll explore modular exponentiation, and discover that exponential expressions that might take thousands of years to calculate, if done directly, can often times be done very efficiently, even by hand, in a matter of minutes. Along the way, we'll also discover that exponents do not live in the same modular world and the rest of the expression. A fact that actually forms the basis from many of the cryptographic algorithms that protect our most sensitive secrets. Well then learn how the modulus of exponent is related to the totient of the expression modulus, and how to calculate that torsion. We'll finish this module by looking at discrete logarithms and see how they behave very differently from the ordinary logarithms we're familiar with. The third module will let us explore a very powerful tool known as the Chinese Remainder Theorem or CRT, which lets us work with unimaginably large numbers quite efficiently, even with just pen and paper. We'll learn how to represent integers via the Chinese Remainder Theorem and how to convert back. We'll then look at what things we can do easily with CRT represented numbers as well as some of the things that we can't. The final module will explore prime numbers in more depth, including the difficulty of factoring large numbers. And of testing numbers to see if they are prime in efficient ways. We'll look at a couple of methods that can give us a high degree of confidence, but not a certainty, that a number is prime. And also touch on methods that can absolutely prove whether a number is prime and consider why they are seldom used in practice. Once you complete this course, you should be in a reasonable position to appreciate and handle most of the math in the remaining courses in this specialization.
