Opened 15 years ago

Closed 15 years ago

#3020 closed enhancement (fixed)

[With another additional patch, positive review] Finite Fields of characteristic 2 slow to construct

Reported by: John Cremona Owned by: John Cremona
Priority: major Milestone: sage-3.0.2
Component: algebra Keywords: finite fields
Cc: Martin Albrecht, Carl Witty Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Martin Albrecht)

Construction of GF(2n) is very slow for n>=16 (out of the givaro range), owing to slow search for suitable defining irreducible polynomials over GF(2). Also the polynomials produced are dense.

A new function GF2X_sparse_irreducible() has been added, using a precomputed lookup table for degrees up to 2048 (taken from NTL's source code) and otherwise looking for tri- and pentanomials first.

Patch attached, based on 3.0.

Attachments (4)

9606.patch (29.6 KB) - added by John Cremona 15 years ago.
9607.patch (50.3 KB) - added by John Cremona 15 years ago.
9608.patch (696 bytes) - added by John Cremona 15 years ago.
apply after both the preceding patches
GF2X_sparse_poly.patch (6.0 KB) - added by Martin Albrecht 15 years ago.
updated patch which fixes the typo

Download all attachments as: .zip

Change History (19)

Changed 15 years ago by John Cremona

Attachment: 9606.patch added

comment:1 Changed 15 years ago by John Cremona

Cc: Martin Albrecht added
Summary: Finite Fields of characteristic 2 slow to construct[With patch, needs review] Finite Fields of characteristic 2 slow to construct

comment:2 Changed 15 years ago by Martin Albrecht

Type: defectenhancement

The patch looks good, some comments though:

  • I'd prefer to have the table in a different file rather than finite_field.py, say gf2x_irred_table.py?
  • This is table from NTL? Can't we just read in the NTL table automatically?
  • Did you check if each entry is irreducible? I assume so, I just want to make it formally sure.

comment:3 Changed 15 years ago by Michael Abshoff

Milestone: sage-3.0.1
Owner: changed from tbd to John Cremona

comment:4 in reply to:  2 Changed 15 years ago by John Cremona

Replying to malb:

The patch looks good, some comments though:

  • I'd prefer to have the table in a different file rather than finite_field.py, say gf2x_irred_table.py?

Ok, I can do that. If I then put

   import gf2x_irred_table

at the appropriate point in finite_field.py, it would only read it in if the function is called, right?

  • This is table from NTL? Can't we just read in the NTL table automatically?

This was intended to be a quick fix. A better fix (as I originally posted) is to change the NTL wrapping code to use NTL's own function, when creating the field. At the same time we could just wrap NTL's BuildSparseIrred() function.

  • Did you check if each entry is irreducible? I assume so, I just want to make it formally sure.

I checked for k<1000 and was intending to do the rest (as you say, to be formally sure), but it takes quite a long time.

Changed 15 years ago by John Cremona

Attachment: 9607.patch added

comment:5 Changed 15 years ago by John Cremona

Summary: [With patch, needs review] Finite Fields of characteristic 2 slow to construct[With additional patch, needs review] Finite Fields of characteristic 2 slow to construct

The second patch moves the table to a separate file as recommended. Apply *both* patches!

comment:6 Changed 15 years ago by John Cremona

I have now checked that all 2048 polynomials in the table are irreducible, using Sage's .is_irreducible() function. This took a _very_ long time (more than 36 hours to do the last thousand) indicating that some improvement might be possible. But it's done.

Changed 15 years ago by John Cremona

Attachment: 9608.patch added

apply after both the preceding patches

comment:7 Changed 15 years ago by John Cremona

Summary: [With additional patch, needs review] Finite Fields of characteristic 2 slow to construct[With another additional patch, needs review] Finite Fields of characteristic 2 slow to construct

Trivial fix to previous, correcting a very stupid Python indentation howler -- which meant that for all n for which the tabulated irreducib;e was a trinomial, it did not return the table poly but searched for one.

comment:8 Changed 15 years ago by Martin Albrecht

Description: modified (diff)

comment:9 Changed 15 years ago by Martin Albrecht

Cc: Carl Witty added

I've attached an alternative implementation which uses NTL directly rather than re-implementing its behaviour in Sage.

@John: I hope you don't mind, i.e. I don't step on your toes with that, but since you stated that your patch was a quick fix and we should switch to use NTL eventually, I figured it would be a good idea to do it know. Could you review the patch, i.e. check if it does what you want?

@Carl: Somehow the NTL random polynomial generation doesn't obey your randgen framework, any idea why?

comment:10 Changed 15 years ago by John Cremona

No problem, I am delighted that someone has done this properly, and only wish that it had been me to do that. I am off to look at what you have done and test it now...

Comments:

# typo in line 147 (spare -> sparse)

# l.203-4: I wondered why you call BuildSparseIrred first. But I see that NTL's BuildRandomIrred takes a monic irreducible as input and returns another of the same degree, which is rather bizarre, so I guess you had no choice.

I checked the logic of the new code and am happy with it. The patch applies cleanly to 3.0.1, and all doctests in sage/rings pass.

Verdict: positive review! apart from the typo this patch (just the last one from malb) is good to go.

comment:11 Changed 15 years ago by John Cremona

Summary: [With another additional patch, needs review] Finite Fields of characteristic 2 slow to construct[With another additional patch, 99% positive review] Finite Fields of characteristic 2 slow to construct

Sorry forgot to change the summary

Changed 15 years ago by Martin Albrecht

Attachment: GF2X_sparse_poly.patch added

updated patch which fixes the typo

comment:12 Changed 15 years ago by Martin Albrecht

Summary: [With another additional patch, 99% positive review] Finite Fields of characteristic 2 slow to construct[With another additional patch, positive review] Finite Fields of characteristic 2 slow to construct

# typo in line 147 (spare -> sparse)

Fixed in updated patch (same patch, overwritten)

# l.203-4: I wondered why you call BuildSparseIrred? first. But I see that NTL's BuildRandomIrred? takes a monic irreducible as input and returns another of the same degree, which is rather bizarre, so I guess you had no choice.

exactly, but I'm not an NTL expert.

comment:13 Changed 15 years ago by Michael Abshoff

Hi,

it is my understand now to only apply GF2X_sparse_poly.patch. What is the status of the concern regarding the random state? Was that just a general observation since Carl only covered so many randomness sources by his framework?

Cheers,

Michael

comment:14 in reply to:  13 Changed 15 years ago by Martin Albrecht

Replying to mabshoff:

it is my understand now to only apply GF2X_sparse_poly.patch.

correct.

What is the status of the concern regarding the random state? Was that just a general observation since Carl only covered so many randomness sources by his framework?

My guess is that he covers NTL, but we can always open another ticket and address the issue there.

comment:15 Changed 15 years ago by Michael Abshoff

Resolution: fixed
Status: newclosed

Merged GF2X_sparse_poly.patch in Sage 3.0.2.alpha0

Note: See TracTickets for help on using tickets.