10-c DMC: Bezout's identity. An "almost" formula for the GCD.

Foundations of Computer Science, Rensselaer Fall 2020. Professor Malik Magdon-Ismail talks about number theory, the foundations cryptography which enables secure communication, email, banking, social media, .... We start from basic divisibility and the greatest common divisor and cover Bezout's identity and the application to Die Hard: With A Vengence. We then switch gears to modular arithmetic and congruences, the cornerstone of modern public key cryptography (for example RSA). We end by illustrating how modular exponentiation is fundamental to RSA. This is the tenth lecture in a "theory" course focusing on discrete math and the foundations of computing: what can we compute and what can't we compute. Level of the course: Sophomore Computer Science or related major. Material is from Chapter 10 of "Discrete Mathematics and Computing", dmc-book.com.