Finite field linear function to polynomial

[870a0b74-843c-423e-a737-fef34761f72a]

Adding a method which converts a linear function over a finite field in the form of a matrix into a polynomial over that finite field. This method uses dual bases to perform this calculation in milliseconds over fields such as GF(3^8), whereas a naive Lagrange interpolation calculation can take several minutes to get the same result.

Depends on #18714

CC: @rbeezer @malb @simon-king-jena

Component: finite rings

Keywords: finite field, polynomial

Author: Thomas Gagne

Branch/Commit: u/tgagne/finite_field_matrix_to_polynomial @ 1608ecb

Reviewer: Vincent Delecroix

Issue created by migration from https://trac.sagemath.org/ticket/18935

[870a0b74-843c-423e-a737-fef34761f72a]

Branch: u/tgagne/finite_field_matrix_to_polynomial

[870a0b74-843c-423e-a737-fef34761f72a]

Commit: 1608ecb

[870a0b74-843c-423e-a737-fef34761f72a]

Dependencies: 3a14bb2edd87281873d4f2b49d1c5d210c4a4a3c

[870a0b74-843c-423e-a737-fef34761f72a]

Author: Thomas Gagne

[jdemeyer]

comment:2

The dependency should be a trac ticket, not a commit. Do you have a ticket for your dependency? If yes, write the ticket number there. If no, just remove the dependency.

[870a0b74-843c-423e-a737-fef34761f72a]

Changed dependencies from 3a14bb2edd87281873d4f2b49d1c5d210c4a4a3c to #18714

[870a0b74-843c-423e-a737-fef34761f72a]

comment:4

Replying to @jdemeyer:

The dependency should be a trac ticket, not a commit. Do you have a ticket for your dependency? If yes, write the ticket number there. If no, just remove the dependency.

Whoops! Thanks for pointing that out!

[videlec]

Reviewer: Vincent Delecroix

[videlec]

comment:5

Why base_matrix_to_polynomial and not simply matrix_to_polynomial?

poly(el) is simpler than poly.subs(x=el)

This test is really bad

not all([matrix[i,j] in self.base_ring() for i in range(n) for j in range(n)])

You have several better options

• matrix.base_ring() == self
• matrix = matrix.change_ring(self) (this might make an unneeded copy)

If var is already an element of a polynomial ring then you should not recreate another one. In particular, I might want to work over QQ[x,y] and obtain a polynomial in the variable x in this specific ring. I would simply do

if isinstance(var, str):
    from sage.rings.polynomial.polynomial_ring import polygen
    var = polygen(self)

If the matrix is sparse you are doing a lot of unwanted computations. I would actually separate

if matrix.is_sparse():
    entries = matrix.nonzero_positions()
else:
    entries = ((i,j) for i in range(n) for j in range(n))

for i,j in entries:
    # do the looping

And add a test with a huge matrix with very few coefficients like

sage: M = matrix(GF(3,4), 1000, sparse=True)
sage: M[0,3] = 1

The operation gen**i is actually very fast. So I would avoid computing the list basis and replace basis[i] with gen**i

You should not compute a list and then make a sum of elements. Do everything at once

s = 0
for i in range(10):
    s += 1

is much better than

l = []
for i in range(10):
    l.append(i)
s = sum(l)