Opened 14 years ago

Closed 14 years ago

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

Reported by: Owned by: robertwb tbd blocker sage-3.0.4 algebra

```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.
```

### comment:1 Changed 14 years ago by was

• Milestone set to sage-3.0.5

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

### comment:2 Changed 14 years ago by was

• Description modified (diff)
• Summary changed from minpoly slow for finte fields to minpoly absurdly slow for elements of finte fields

### comment:3 Changed 14 years ago by mhansen

• Description modified (diff)

### comment:4 Changed 14 years ago by mhansen

• Description modified (diff)

### comment:5 Changed 14 years ago by was

• Milestone changed from sage-3.0.5 to sage-3.0.4
• Priority changed from major to blocker

### comment:6 Changed 14 years ago by 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(2n). :-(

### comment:7 Changed 14 years ago by 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
```

### comment:8 Changed 14 years ago by was

• Summary changed from minpoly absurdly slow for elements of finte fields to [with patch; needs review] minpoly absurdly slow for elements of finte fields

### comment:9 Changed 14 years ago by was

1. dmharvey -- i have no clue what the point of your remark is above.
1. the point of my patch, by the way, is just to be a first tiny step.

### comment:10 Changed 14 years ago by mhansen

• Summary changed from [with patch; needs review] minpoly absurdly slow for elements of finte fields to [with patch; positive review] minpoly absurdly slow for elements of finte fields

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

### comment:11 Changed 14 years ago by dmharvey

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

### comment:12 Changed 14 years ago by mabshoff

• Resolution set to fixed
• Status changed from new to closed

Merged in Sage 3.0.4.rc3

### comment:13 Changed 14 years ago by robertwb

• Resolution fixed deleted
• Status changed from closed to reopened

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).

### comment:14 Changed 14 years ago by 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

### comment:15 Changed 14 years ago by mabshoff

• Resolution set to fixed
• Status changed from reopened to closed
Note: See TracTickets for help on using tickets.