Basics of Number Theory
To effectively understand and implement ZKP protocols, a solid grasp of number theory concepts is essential. Topics such as rings, groups, fields, modular arithmetic, polynomials, elliptic curves, and pairings are foundational to these protocols.
In this tutorial, we’ll cover these fundamental ideas, highlight their key properties, and demonstrate their implementation from scratch in Rust. 🦀 Whether you're new to these concepts or looking for a refresher, this section will help you build a strong foundation. If you're already an expert, feel free to skip ahead! 🚀
🧠 Key Concepts You Will Learn
- ✨ Computational Rules: Associative and Commutative Properties
- 🧮 Integer Arithmetic: Modular Operations, Euler’s Totient Function, and Fermat’s Little Theorem
- 🔗 Groups, Rings, and Fields: Semigroups, Subgroups, Cyclic Groups, Galois Fields, and Field Extensions
- 🖋️ Polynomials: Basic Operations, Lagrange Interpolation, and Schwartz–Zippel Lemma
- 🕊️ Elliptic Curves: Basic Operations, Hasse–Weil Theorem, Zeros and Poles of Functions, and Divisors of Functions
- ♾️ Pairings: Weil Pairing, Ate Pairing, and Miller’s Algorithm
- 🔑 Assumptions: Discrete Logarithm Problem and Knowledge of Exponent Assumption