Opened 13 years ago

Closed 13 years ago

# [with patch, positive review] minpoly still slow for elements of finte fields

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

### Description

The improvement at #3620 is significant, but 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:1 Changed 13 years ago by robertwb

• Summary changed from minpoly still slow for elements of finte fields to [with patch, needs review] minpoly still slow for elements of finte fields
```sage: sage: k.<a> = GF(2^500)

sage: sage: time g = k.random_element()
CPU times: user 0.07 s, sys: 0.00 s, total: 0.07 s
Wall time: 0.07 s

sage: time f = g.minpoly()
CPU times: user 0.00 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.00 s

sage: f(g)
0
sage: timeit("g.minpoly()")
125 loops, best of 3: 4.03 ms per loop
```

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

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

Great work Robert!

I added a patch that adds a fast charpoly method by the way.

Apply both of them.

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

Charpoly method is good too. Apply both patches.

### comment:4 Changed 13 years ago by mabshoff

• Milestone changed from sage-3.0.6 to sage-3.0.5

This is one of the few patches that will be merged in 3.0.5 :)

Cheers,

Michael

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

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