Module fast_inverse 

Fast inversion for GF(2^128) using Itoh-Tsujii with nibble tables

This implements efficient field inversion using precomputed tables of frobenius powers. The algorithm reduces from ~127 multiplications to ~9 multiplications + table lookups.

Algorithm

Uses the identity: x^(-1) = x^(2^128 - 2)

The exponent 2^128 - 2 is computed using addition chains:

• 2^128 - 2 = 2 * (2^127 - 1)
• 2^127 - 1 has binary representation of 127 ones

By using the linearity of frobenius in characteristic 2, we can decompose computations by nibbles and use table lookups.

References

• Itoh-Tsujii: “A fast algorithm for computing multiplicative inverses in GF(2^m)”
• Binius implementation: https://github.com/IrreducibleOSS/binius
• GF2t Java library: https://github.com/reyzin/GF2t

Functions

batch_invert_gf128

Batch invert multiple field elements using Montgomery’s trick

batch_invert_gf128_in_place

Batch invert in-place (more memory efficient)

invert_gf128

Invert a field element in GF(2^128)