Polynomial Rings over a Finite Field

• Polynomial.Field supports addition, multiplication, division/modulus and inverse of a polynomial ring over a finite field. These operations do not support Complex, BigComplex, BigDecimal, or BigRational types.

  • What this effectively means in less-technical terms is that the polynomial arithmetic is performed in the usual way, but the result is then taken modulus two things:
    • Modulo an integer: All coefficients are reduced modulo an integer.
    • Modulo a polynomial: The whole polynomial is reduced modulo another, smaller, polynomial. This notion works much the same as regular modulus; The modulus polynomial, let's call it g, is declared to be equivalent to zero, and so every multiple of g is reduced to zero. You can think of it this way (although this is not how it's actually carried out): From a large polynomial, g is repeatedly subtracted from that polynomial until it can't subtract g anymore without crossing zero. The result is a polynomial that lies between 0 and g. Just like regular modulus, the result is always less than your modulus, or zero if the polynomial was a multiple of the modulus.
    • Effectively forms a quotient ring

• You can instantiate a polynomial in various ways:

  • From a string
    • This is the most massively-useful way and is the quickest way to start working with a particular polynomial you had in mind.
  • From its roots (Not all types supported)
    • Build a polynomial that has, as its roots, all of the numbers in the supplied array. If you want multiplicity of roots, include that number in the array multiple times.
  • From the base-m expansion of a number
    • Given a large number and a radix (base), call it m, a polynomial will be generated that is that number represented in the number base m.

• Other methods of interest that are related to, but not necessarily performed on a polynomial (Not all types supported):

  • Euler's Criterion
  • Legendre Symbol and Legendre Symbol Search
  • Tonelli-Shanks
  • Chinese Remainder Theorem
  • Polynomial evaluation by assigning to the invariant (X in this case) a value.