Path: blob/main/foundations/01-modular-arithmetic-groups/README.md
483 views
unlisted
Module 01: Modular Arithmetic and Groups
From clock arithmetic to the algebraic structures that underpin all of cryptography.
Prerequisites
No prior modules needed. This is the starting point.
Learning Objectives
After completing this module you will:
Understand modular arithmetic as a system, not just a calculation trick
Recognize group structure in Z_n and Z_n*
Compute generators and orders of cyclic groups
Apply Lagrange's theorem to reason about subgroup structure
Two Ways to Run
Every notebook has two versions. Choose whichever works for you.
| Python (browser) | SageMath | |
|---|---|---|
| Setup | Zero install, runs in JupyterLite | Needs local install or Codespaces |
| Launch time | ~5 seconds | ~1 minute (Codespaces) or 10+ min (Binder) |
| Best for | Quick exploration, mobile, first-timers | Full algebra system, research-grade computations |
Explore
Work through these notebooks in order:
| # | Notebook | Python | SageMath |
|---|---|---|---|
| a | Integers and Division | python | sage |
| b | Modular Arithmetic | python | sage |
| c | Groups: First Look | python | sage |
| d | Cyclic Groups and Generators | python | sage |
| e | Subgroups and Lagrange | python | sage |
| f | Group Visualization | python | sage |
Implement (Rust)
Build these from scratch in rust/src/lib.rs:
| # | Function | Description |
|---|---|---|
| 1 | mod_exp | Modular exponentiation via repeated squaring |
| 2 | gcd | Greatest common divisor (Euclidean algorithm) |
| 3 | is_generator | Test whether an element generates the full group |
| 4 | element_order | Compute the multiplicative order of an element |
| 5 | find_all_generators | Enumerate every generator of Z_n* |
Run: cargo test -p mod-arith-groups