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