C code for GF(2q) for q <64
This file provides and tests code for GF(2q) for 0<q<64.
The irreducible polynomials for each q are tabulated in the array irrp.
2q+irrp[q] is that polynomial for 0<q<64.
The values in irrp were provided by the 3 lines of Scheme code (in this context) at the end of the program.
- pmul(L a, L b)
- is the polynomial multiplication routine that is ignorant of the irp (irreducible polynomial).
- fmul(L a, L b)
- is the multiplication in GF(2q), i.e. the product modulo the irp.
In this routine we deduct the irp after each multiplication step.
- High(n)
- is merely a routine to locate the most significant bit.
- PR pqr(L n, L d)
- is synthetic division in the polynomial ring.
- PR ge(L a, L b)
- is the recursive extended Euclidean Algorithm for GF(2q).
ge(a, b) returns (PR){x, y} such that ax+by = gcd(a, b).
- rn()
- returns a q bit random number.
- finv(L x)
- returns the multiplicative inverse in GF(2q).