Ticket #3634 (closed defect: fixed)

Opened 2 years ago

Last modified 2 years ago

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

Reported by: robertwb Owned by: tbd
Priority: blocker Milestone: sage-3.0.5
Component: algebra Keywords:
Cc: Author(s):
Report Upstream: Reviewer(s):
Merged in: Work issues:

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 Download (6.0 KB) - added by robertwb 2 years ago.
sage-3634-referee.patch Download (2.0 KB) - added by was 2 years ago.
add fast charpoly

Change History

Changed 2 years ago by robertwb

Changed 2 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

Changed 2 years ago by was

add fast charpoly

Changed 2 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.

Changed 2 years ago by robertwb

Charpoly method is good too. Apply both patches.

Changed 2 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

Changed 2 years ago by was

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