Finite fields in Nemo

[Bill Hart]

I've added finite fields to the flint interpreter Nemo:

https://github.com/wbhart/nemo

http://www.flintlib.org/nemo.pdf

I didn't specialise polynomials over finite fields to use flint's fq_poly, but the generic polynomial code is already exceptionally fast, as the following example shows:

julia> R, x = FiniteField(7, 11, "x")

(Finite field of degree 11 over F_7,x)

julia> S, y = PolynomialRing(R, "y")

(Univariate polynomial ring in y over Finite field of degree 11 over F_7,y)

julia> T = ResidueRing(S, y^3 + 3x*y + 1)

Residue ring of Univariate polynomial ring in y over Finite field of degree 11 over F_7 modulo y^3+(3*x)*y+1 (constructor with 5 methods)

julia> U, z = PolynomialRing(T, "z")

(Univariate polynomial ring in z over Residue ring of Univariate polynomial ring in y over Finite field of degree 11 over F_7 modulo y^3+(3*x)*y+1,z)

julia> f = (3y^2 + y + x)*z^2 + ((x + 2)*y^2 + x + 1)*z + 4x*y + 3

(3*y^2+y+(x))*z^2+((x+2)*y^2+(x+1))*z+((4*x)*y+3)

julia> g = (7y^2 - y + 2x + 7)*z^2 + (3y^2 + 4x + 1)*z + (2x + 1)*y + 1

(6*-y+(2*x))*z^2+(3*y^2+(4*x+1))*z+((2*x+1)*y+1)

julia> s = f^12;

julia> t = (s + g)^12;

julia> @time r = resultant(s, t);

elapsed time: 4.956234525 seconds (207789656 bytes allocated)

I tried the same computation in Sage, but gave up after there was no answer after half an hour!!

Magma does this computation in 1s, but it surely uses a more compact representation.

It's amazing, given how generic this is, that it comes so close to the Magma time. It does get the right answer too.

It's equally impressive that Magma does so well for such a generic computation. It's unlikely Magma uses Zech logs here as the field is quite large. 

I tried switching to a more compact representation of the field (the fq_nmod representation). But this made no difference to the times. My guess is Magma uses a very efficient representation for such a field.

It's telling that if you change the characteristic to 17, Magma takes 86s for the same computation. Nemo still only takes 5.5s.

Bill.

[Bill Hart]

I finished specialising polynomials over finite fields to use the flint fq_poly module in Nemo.

For the one benchmark I had, this slowed things down 10-15% because for whatever reason, flint is slower than the generic code in Nemo. 

But for large polynomials, things ought to be faster.

Bill.

On 22 August 2014 07:20, Bill Hart <goodwi...@googlemail.com> wrote: