[with patch; positive review] minpoly absurdly slow for elements of finte fields

[robertwb]

It goes via pari calls, rather than invoking ntl directly. 

e.g., computing the minpoly of a random element in GF(2^300)
takes about  a minute in sage and a second in Magma.  It's slow
because PARI is really really slow.  Just getting the matrix and
asking for its charpoly is vastly vaster in sage already, so doing
that would be a good first step. 

[was]

But note, we may want to use our own implementation since minpoly and charpoly of *matrices* over finite fields in sage is so fast.

[was]

Here is an example that illustrates the difference:

sage: k.<a> = GF(2^100)
sage: time g = k.random_element().charpoly()
CPU times: user 1.17 s, sys: 0.02 s, total: 1.18 s
Wall time: 1.36 s
sage: magma.eval('time f := CharacteristicPolynomial(Random(GF(2^100)));')
'Time: 0.000'

Here's the sage code that does the charpoly computation:

sage: a.charpoly??
        from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
        R = PolynomialRing(self.parent().prime_subfield(), var)
        return R(self._pari_().charpoly('x').lift())

It turns out that pari is just totally abysmal at computing charpolys of Mod's.

sage: f = k.random_element()._pari_()
sage: time g = f.charpoly('x')
CPU times: user 1.13 s, sys: 0.01 s, total: 1.14 s
Wall time: 1.26 s
sage: f.type()
't_POLMOD'

Fortunately Sage matrices aren't quite as bad, though of course this is still vastly slower than Magma:

sage: time g = k.random_element().matrix().charpoly()
CPU times: user 0.36 s, sys: 0.00 s, total: 0.36 s
Wall time: 0.37 s

Asymptotically though this is still vastly better than the current situation:

age: k.<a> = GF(2^200)
sage: time g = k.random_element().matrix().charpoly()
CPU times: user 2.21 s, sys: 0.03 s, total: 2.24 s
Wall time: 2.24 s
sage: time g = k.random_element().charpoly()
CPU times: user 14.14 s, sys: 0.08 s, total: 14.22 s
Wall time: 14.27 s

But still this sucks compared to magma

sage: magma.eval('time f := CharacteristicPolynomial(Random(GF(2^200)));')
'Time: 0.000'
sage: magma.eval('time f := CharacteristicPolynomial(Random(GF(2^200)));')
'Time: 0.000'
sage: magma.eval('time f := CharacteristicPolynomial(Random(GF(2^300)));')
'Time: 0.000'
sage: magma.eval('time f := CharacteristicPolynomial(Random(GF(2^400)));')
'Time: 0.010'
sage: magma.eval('time f := CharacteristicPolynomial(Random(GF(2^600)));')
'Time: 0.010'
sage: magma.eval('time f := CharacteristicPolynomial(Random(GF(2^1000)));')
'Time: 0.030'

I looked at NTL seems to have no functions at all for charpoly or minpoly of elements of GF(2^{n). :-(}

 http://www.shoup.net/ntl/doc/GF2E.txt

[dmharvey]

also note:

sage: k.<a> = GF(2^500)
sage: time g = k.random_element()
CPU times: user 0.06 s, sys: 0.00 s, total: 0.06 s
Wall time: 0.06 s
sage: time m = g.matrix()
CPU times: user 11.59 s, sys: 0.82 s, total: 12.41 s
Wall time: 12.41 s
sage: time f = m.charpoly()
CPU times: user 20.51 s, sys: 0.01 s, total: 20.52 s
Wall time: 20.51 s

[was]

1. dmharvey -- i have no clue what the point of your remark is above.

2. the point of my patch, by the way, is just to be a first tiny step.

[mhansen]

Looks good to me. Should there be another ticket for improving this further.

[dmharvey]

My point is just that computing the matrix and computing its charpoly both take non-negligble time.

[mabshoff]

Merged in Sage 3.0.4.rc3

[robertwb]

It looks like NTL does have minimal polynomial computations, though provided in  http://www.shoup.net/ntl/doc/GF2X.txt rather than  http://www.shoup.net/ntl/doc/GF2E.txt . We should probably use the proof flag to decide the algorithm. Trace could be wrapped as well.

Also, the computation of matrix() is using the completely generic code, which has got to be sub-optimal for manipulating elements of GF(2).

[mabshoff]

Robert,

I see no reason to reason to reopen this ticket since what you describe seems to be an improvement/additional change. Please open another ticket since the attached patch has been merged in Sage 3.0.4.

Cheers,

Michael