Any exploitable structure for modular multiplicative inverses

finite-fieldsmodular arithmetic

In order to speed up some Reed Solomon codecs, I'm investigating parallel algorithms for multiplicative inverses in $GF(929)$ and $GF(113)$. What I've understood as an non-mathematician is that e.g. for $GF(2^8)$ there exists a composite field, in which the multiplicative inverse can be calculated using merely operations on $GF(2^4)$ coupled with affine transformations back and forth the original field and the composite field.

From numerological perspective it seems possible, that the fields used for those particular prime fields are carefully chosen by non-engineers to allow some computation to happen on smaller relative primes, maybe in a residue system — $929 – 1 = 2^5 * 29$, $113 – 1 = 2^4 * 7$. This begs the question if likewise the $GF(2^{2m})$ cases, the multiplicative inverses in $GF(929)$ and $GF(113)$ could be calculated by most work done on smaller fields.

If not, I'm likely to use parallel modular exponentiation or scalar binary extended gcd.

EDIT

As described in the first answer, the points 2 and 5 do help in reducing the lookup table, both by a factor of 2.

$a^{-1} = N-(N-a)^{-1}$ leads to necessity to store only 50% of the coefficients. Furthermore $(2a)^{-1} = 2^{-1}a{-1}$ meaning that one only needs to store the odd table entries at the cost of one (constant) modular multiplication.

This last point may be practically extended to cover multiples of 3, meaning that for every a mod 6, one needs to store the values for the remainders 1 and 5, saving 66% of the LUT entries and suffer the cost of some additional calculations.

For the case of $GF(929)$ it might be lucrative to try to compress the table by including multiples of 5 as well, reducing the table of inverses to slightly less than 128.

Best Answer

tons of structure:

  1. The multiplicative inverse of the additive inverse, is the additive inverse of the multiplicative inverse.
  2. The multiplicative inverse of a number, is the product of multiplicative inverses of it's factors.
  3. for composite moduli, the multiplicative inverse of a remainder, is its multiplicative inverse of all the modulus' prime power factors put together with CRT.
  4. the additive inverse of the multiplicative inverse of the modulus, modulo the remainder times the modulus, plus 1 will be divisible by the remainder giving the multiplicative inverse.
  5. By Euler's totient theorem raising the remainder to the $\phi (n)-1$ exponent, is congruent to the multiplicative inverse. $$\vdots$$

just to review a few.

Related Question