Part IX · Number Theory, Combinatorics and Algebra
53. Modular Arithmetic and Cryptographic Number Theory
7 lessons•29 topics•Intermediate / Expert
0 of 7 lessons published
53.01Outline
Modular foundations
- Congruence
- Normalized remainder
- Modular addition/subtraction
- Modular multiplication
- Overflow-safe operations
53.02Outline
Exponentiation
- Binary exponentiation
- Modular powers
- Exponent reduction
- Fast repeated squaring
53.03Outline
Modular inverses
- Extended Euclid inverse
- Fermat little theorem inverse
- Inverse arrays
- Conditions for invertibility
53.04Outline
Chinese remainder theorem
- Pairwise coprime CRT
- Generalized CRT
- Combine congruences
- Garner's algorithm overview
53.05Outline
Modular combinatorics
- Factorials modulo p
- nCr modulo p
- Lucas theorem
- Factor exponent in n!
53.06Outline
Discrete mathematics connections
- Fermat's theorem
- Euler's theorem
- Euler totient
- Multiplicative order
- Primitive roots overview
53.07Outline
Discrete logarithms
- Baby-step giant-step
- Pohlig-Hellman overview
- Modular square roots Tonelli-Shanks overview