3 | 12 and 12 | 3.
- 3 | 12 is true; 12 | 3 is false.
Number Theory and Cryptography
Divisibility, primes and the Fundamental Theorem of Arithmetic, GCD and LCM, the division algorithm, mod and congruences, then classical ciphers (Caesar, shift, affine), public-key cryptography with RSA, and the Diffie–Hellman key exchange.
How to read this page
Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.
All 84 slides
- 1 Slide 1
- 2 4.1 Divisibility and Modular Arithmetic
- 3 The Integers & Division
- 4 Divisors Examples
- 5 Divisors Examples
- 6 Facts: The Divides Relation
- 7 Composite & Prime Numbers
- 8 Fundamental Theorem of Arithmetic
- 9 Theorem
- 10 Prime Factorization Technique
- 11 Prime Factorization Examples
- 12 Slide 12
- 13 Primary Testing Example
- 14 Greatest Common Division (GCD)
- 15 2 Ways to find GCD
- 16 Slide 16
- 17 Slide 17
- 18 Greatest Common Division
- 19 Slide 19
- 20 Greatest Common Division Relatively Prime
- 21 Greatest Common Division Relatively Prime
- 22 Least Common Multiple
- 23 Slide 23
- 24 Division
- 25 The Division “Algorithm”
- 26 Examples
- 27 Solutions
- 28 mod Function Start Here
- 29 mod Function
- 30 Question
- 31 Question
- 32 Modular Congruence
- 33 Examples
- 34 Useful Congruence Theorems
- 35 Ex.:
- 36 Slide 36
- 37 Section Summary
- 38 Why Cryptography
- 39 Slide 39
- 40 Symmetric Encryption
- 41 Symmetric Encryption
- 42 Caesar Cipher
- 43 Caesar cipher
- 44 Caesar Cipher
- 45 Caesar Cipher
- 46 Shift Cipher
- 47 Shift Cipher
- 48 Shift Cipher
- 49 Shift Cipher
- 50 Affine Ciphers
- 51 Cryptanalysis of Affine Ciphers
- 52 Cryptosystems
- 53 Cryptosystems
- 54 Slide 54
- 55 Public Key Cryptography
- 56 Clifford Cocks
- 57 The RSA Cryptosystem
- 58 Slide 58
- 59 Slide 59
- 60 The RSA Cryptosystem
- 61 RSA algorithm explanation -step by step example
- 62 Continue...
- 63 Continue...
- 64 Example
- 65 RSA Encryption
- 66 RSA Encryption- example
- 67 RSA Decryption
- 68 RSA Decryption- example
- 69 Slide 69
- 70 Slide 70
- 71 Slide 71
- 72 Slide 72
- 73 Slide 73
- 74 Slide 74
- 75 Diffie-Hellman
- 76 Diffie Helman Step by Step
- 77 Diffie Helman Step by Step- Cont
- 78 Slide 78
- 79 Slide 79
- 80 Slide 80
- 81 Slide 81
- 82 Cryptographic Protocols: Key Exchange
- 83 Cryptographic Protocols: Digital Signatures
- 84 Cryptographic Protocols: Digital Signatures
Slide 1
4.1 Divisibility and Modular Arithmetic
The Integers & Division
Exam angle
Divisors Examples
Divisors Examples
Facts: The Divides Relation
Notes
If a | b and a | c then a | (b + c); if a | b then a | bc; if a | b and b | c then a | c.
Composite & Prime Numbers
Notes
Prime: integer > 1 whose only positive divisors are 1 and itself. 1 is NOT prime.
Fundamental Theorem of Arithmetic
Theorem
Exam angle
To show 101 is prime it is enough to test divisibility by primes up to:
- √101 ≈ 10.05: try 2, 3, 5, 7.
Prime Factorization Technique
Prime Factorization Examples
Slide 12
Primary Testing Example
Greatest Common Division (GCD)
Notes
gcd(a, b): largest integer dividing both. Relatively prime when gcd = 1.
2 Ways to find GCD
Notes
gcd via prime factorizations: take the MIN power of each prime. lcm: take the MAX power.
gcd(a, b)·lcm(a, b) = a·b.
Exam angle
gcd(120, 500) =
- 2³·3·5 and 2²·5³ → 2²·5.
If gcd(a, b) = 6 and ab = 360, lcm(a, b) =
- 360 / 6.
Slide 16
Slide 17
Greatest Common Division
Slide 19
Greatest Common Division Relatively Prime
Notes
Pairwise relatively prime: every pair has gcd 1.
Greatest Common Division Relatively Prime
Least Common Multiple
Slide 23
Division
The Division “Algorithm”
Notes
Division algorithm: a = dq + r with 0 ≤ r < d; q = a div d, r = a mod d.
Trap The remainder is never negative: −11 div 3 = −4, −11 mod 3 = 1 (−11 = 3·(−4) + 1).
Exam angle
−11 mod 3 =
Examples
Solutions
mod Function Start Here
mod Function
Question
Question
Modular Congruence
Notes
a ≡ b (mod m) when m | (a − b), i.e. a mod m = b mod m.
Exam angle
17 ≡ 5 (mod 6).
- 6 | 12.
Examples
Useful Congruence Theorems
Notes
If a ≡ b and c ≡ d (mod m) then a + c ≡ b + d and ac ≡ bd (mod m).
Ex.:
Slide 36
Section Summary
Why Cryptography
Slide 39
Symmetric Encryption
Symmetric Encryption
Caesar Cipher
Exam angle
Caesar (shift 3) encrypts "HI" as:
- H(7)+3 = K, I(8)+3 = L.
Caesar cipher
Caesar Cipher
Caesar Cipher
Shift Cipher
Shift Cipher
Shift Cipher
Shift Cipher
Affine Ciphers
Exam angle
In an affine cipher f(p) = (ap + b) mod 26, a must satisfy:
Cryptanalysis of Affine Ciphers
Cryptosystems
Cryptosystems
Slide 54
Public Key Cryptography
Clifford Cocks
The RSA Cryptosystem
Notes
RSA: n = pq, choose e with gcd(e, (p−1)(q−1)) = 1, d = e⁻¹ mod (p−1)(q−1).
Slide 58
Slide 59
The RSA Cryptosystem
RSA algorithm explanation -step by step example
Continue...
Continue...
Example
RSA Encryption
RSA Encryption- example
RSA Decryption
Exam angle
RSA with p = 3, q = 11, e = 3. Find n, φ, and d.
Compare with the model answer
n = 33, φ = (p−1)(q−1) = 20. d is the inverse of 3 mod 20: 3·7 = 21 ≡ 1, so d = 7.
In RSA, which key is kept secret?
- (e, n) is public.
RSA Decryption- example
Slide 69
Slide 70
Slide 71
Slide 72
Slide 73
Slide 74
Diffie-Hellman
Notes
Diffie–Hellman: agree on prime p and base g; Alice sends gᵃ mod p, Bob sends gᵇ mod p; both compute the shared key gᵃᵇ mod p.
Exam angle
p = 23, g = 5, a = 6, b = 15. Alice sends:
Diffie Helman Step by Step
Diffie Helman Step by Step- Cont
Slide 78
Slide 79
Slide 80
Slide 81
Cryptographic Protocols: Key Exchange
Cryptographic Protocols: Digital Signatures
Cryptographic Protocols: Digital Signatures
