We have a Galois field GF (2 409 ) , and an irreducible polynomial over a field:

f (x) = x 409 + x 15 + x 6 + x + 1
// Coefficients with powers of only 0 or 1

Let me have some polynomial a (x) in this field. Question: How can I find the inverse of "a (x)", relative to f (x) element, using the Euclidean algorithm , and not raising the element "a (x)" to the power of 2,409 -2.

// I search the inverse element search algorithm in Python using a polynomial basis, and exponentiation on it works too long // Problems arise when introducing a division operation on polynomials

  • what is your difficulty? Want to speed up existing code? Do you want to implement the gcd-like algorithm on Python with your hands? Or use the ready library, for example GF.invert in sympy - jfs
  • The difficulty is that exponentiation 2 ^ 409 - 2 works too long. Euclidean algorithm is much faster. I do not want to use the finished library as I am doing this purely for educational purposes. - Romanov Roman
  • if there is a question about performance, provide the code that gets the correct result (let it be slow) and indicate how much you want to speed it up ( 2**409 should not take a considerable amount of time). You can see how sympy implements gf_gcd (for education, I don’t think this is a particularly effective option). "Coefficients with powers of only 0 or 1" hints that polynomials can be effectively represented by integers. - jfs

1 answer 1

2 409 -2 is a number containing 409 set bits and one reset (the last but one). This means that for the rapid construction of the element a (x) to this power, 408 squaring operations and 408 multiplication operations on the 409th order polynomial modulo f (x) are required.

For multiplication of polynomials, 409 * 410/2 multiplications are needed, the order of the product will be 818. To bring it to the f (x) module using the angle method, 409 * 4 subtractions are required, which practically does not affect performance.

Total: 2 * 408 * 409 * 410/2 = 68,417,520 multiplications.

The real problem is data capacity, because each time a polynomial is squared, the sum of its coefficients (equal to the value of the polynomial at x = 1 ) is also squared, which increases the original bit depth by 409 log 2 a (1) bits and eventually weights the algorithm is at least 2 orders of magnitude.

The rest is implementation details.