V6c: Algorithmic Number Theory (Applied Cryptography 101)

Video lectures for Alfred Menezes's introductory course on the fundamental building blocks used in cryptography. Topics covered: Fundamental theorem of arithmetic, algorithm, input size, polynomial-time algorithm, integer addition, subtraction, multiplication, division, greatest common divisor, Euclidean algorithm, modular operations, extended Euclidean algorithm, repeated square-and-multiply algorithm Lecture playlist: https://www.youtube.com/playlist?list=PLA1qgQLL41SRsHMtsb4up5fTytDeHV_yJ Course web page: https://cryptography101.ca/crypto101-building-blocks/ The slides are available on the course web page. "Public-key cryptography" chapter from "Textbook of Applied Cryptography": https://drive.google.com/file/d/1egfsGDamcT96_mS8qBoHBI0nzEhHtwK-/view Other cryptography courses: https://cryptography101.ca Slides 00:00 Introduction 00:17 Slide 239: Fundamental theorem of arithmetic 03:42 Slide 240: Basic concepts from complexity theory 05:29 Slide 241: Basic concepts from complexity theory (2) 07:14 Slide 242: Basic integer operations 13:53 Slide 243: Basic modular operations 16:43 Slide 244: Modular exponentation 19:08 Slide 245: Modular exponentation (2) 21:56 Slide 246: Example: modular exponentation 22:13 Maple example 25:21 Coming up