A prime field is a finite field whose elements are the integers modulo a prime p. Counting wraps back to 0, like a clock, while 0 and 1 provide the identities needed for addition and multiplication. Every element also has a modular inverse, enabling division. section 2.1
Prime-field arithmetic is implemented through a small set of modular routines:
- Add, subtract, and multiply elements modulo p. section 2.7
- Compute inverses and divide by multiplying by an inverse. section 2.1 section 2.7
- Use quadratic-residue routines when square roots are required. section 2.7
A field with p = 43
Represent the field as a clock numbered 0 through 42. After 42, counting returns to 0. A tiny implementation initializes the prime to 43, finds an irreducible polynomial for later extension work, and prepares polynomial multiplication. section 2.1 section 13.3.1
Figure 2.2 Finite field over prime numbers viewed as a clock (\(p=43\))
Use the clock diagram to visualize modular wraparound and the elements of the prime field. section 2.1
