Ticket #3634 (closed defect: fixed)

Opened 3 months ago

Last modified 3 months ago

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

Reported by: robertwb Assigned to: tbd
Priority: blocker Milestone: sage-3.0.5
Component: algebra Keywords:
Cc:

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

Attachments

3634-gf2e-minpoly.patch (6.0 kB) - added by robertwb on 07/10/2008 11:05:09 AM.
sage-3634-referee.patch (2.0 kB) - added by was on 07/10/2008 04:21:26 PM.
add fast charpoly

Change History

07/10/2008 11:05:09 AM changed by robertwb

  • attachment 3634-gf2e-minpoly.patch added.

07/10/2008 11:07:41 AM changed 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

07/10/2008 04:21:26 PM changed by was

  • attachment sage-3634-referee.patch added.

add fast charpoly

07/10/2008 04:22:06 PM changed 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.

07/11/2008 10:43:08 AM changed by robertwb

Charpoly method is good too. Apply both patches.

07/11/2008 10:46:26 AM changed 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

07/11/2008 11:09:48 AM changed by was

  • status changed from new to closed.
  • resolution set to fixed.