Opened 13 years ago

Closed 13 years ago

#3634 closed defect (fixed)

[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: Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

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 (2)

3634-gf2e-minpoly.patch (6.0 KB) - added by robertwb 13 years ago.
sage-3634-referee.patch (2.0 KB) - added by was 13 years ago.
add fast charpoly

Download all attachments as: .zip

Change History (7)

Changed 13 years ago by robertwb

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

Changed 13 years ago by was

add fast charpoly

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.