Opened 9 years ago

Closed 9 years ago

#14832 closed enhancement (fixed)

Unified construction of irreducible polynomials over finite fields

Reported by: Peter Bruin Owned by: Clément Pernet
Priority: major Milestone: sage-5.12
Component: finite rings Keywords: polynomials
Cc: Xavier Caruso Merged in: sage-5.12.beta1
Authors: Peter Bruin Reviewers: Jean-Pierre Flori
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #14817, #14818 Stopgaps:

Status badges

Description (last modified by Peter Bruin)

Currently, every finite field implementation (integers mod p, Givaro, NTL, PARI) has its own code for constructing an irreducible polynomial when given a string as the modulus keyword. This ticket does the following:

  • implement a new class PolynomialRing_dense_finite_field
  • create methods PolynomialRing_dense_{finite_field,mod_p}.irreducible_element(n, algorithm=None).

In a separate ticket (#14833), the FiniteField constructor is adapted to call the new function.

The default choice is now deterministic: Conway polynomials if available, otherwise lexicographically first (via NTL/GF2E) in characteristic 2, Adleman-Lenstra (via PARI) in characteristic > 2.

Since it uses PARI's ffinit, this depends on #14818.

Apply:

Attachments (5)

trac_14832_make_irreducible_polynomial.patch (10.0 KB) - added by Peter Bruin 9 years ago.
based on 5.11.beta3
trac_14832-PolynomialRing_dense_finite_field.patch (4.9 KB) - added by Peter Bruin 9 years ago.
new class for polynomial rings over finite fields
trac_14832-irreducible_polynomial.patch (8.5 KB) - added by Peter Bruin 9 years ago.
method irreducible_element()
trac_14832-reviewer.patch (2.1 KB) - added by Jean-Pierre Flori 9 years ago.
Reviewer patch.
trac_14832-doctest.patch (1.3 KB) - added by Peter Bruin 9 years ago.
add doctest

Download all attachments as: .zip

Change History (22)

Changed 9 years ago by Peter Bruin

based on 5.11.beta3

comment:1 Changed 9 years ago by Peter Bruin

Description: modified (diff)
Status: newneeds_review

comment:2 Changed 9 years ago by Peter Bruin

Description: modified (diff)

comment:3 Changed 9 years ago by Xavier Caruso

Cc: Xavier Caruso added

comment:4 Changed 9 years ago by Peter Bruin

Description: modified (diff)

Moved finite field-specific code from PolynomialRing_field.__init__() to PolynomialRing_dense_finite_field.__init__().

Changed 9 years ago by Peter Bruin

new class for polynomial rings over finite fields

Changed 9 years ago by Peter Bruin

method irreducible_element()

comment:5 Changed 9 years ago by Jean-Pierre Flori

Is there any reason for removing the implementation arg to the PR_field constructor? I agree it's not used, but maybe at some point :)

And why not test in the PR_field constructor if the field is finite and call the new constructor in that case?

By the way, I'm not sure using is_FiniteField is the right way to check for finite fields. Using the category framework and doing something like "R in FiniteFields?()" is surely better unless you really rely on implementation details of the FiniteField? class and subclasses.

comment:6 Changed 9 years ago by Jean-Pierre Flori

(The same category stuff would be true for IntegerModRing? and so on... but I'm not asking you to fix the old code, just not to introduce new "bad" stuff.)

comment:7 Changed 9 years ago by Jean-Pierre Flori

Reviewers: Jean-Pierre Flori
Status: needs_reviewneeds_work
Work issues: double colons, check for finite fields

You also need to use two consecutive colons to introduce examples:

EXAMPLES::

    sage: 1+1
    2

or

EXAMPLES:

We check that 1+1 is equal to 2::

    sage: 1+1
    2

comment:8 in reply to:  5 ; Changed 9 years ago by Peter Bruin

Replying to jpflori:

Is there any reason for removing the implementation arg to the PR_field constructor? I agree it's not used, but maybe at some point :)

And why not test in the PR_field constructor if the field is finite and call the new constructor in that case?

I think it is better to be conservative with the implementation parameter: allow it for the generic PolynomialRing constructor and pass it to subclasses that actually have different implementations, but do not add (or keep) the flag in subclasses where it does not do anything.

By the way, I'm not sure using is_FiniteField is the right way to check for finite fields. Using the category framework and doing something like "R in FiniteFields?()" is surely better unless you really rely on implementation details of the FiniteField? class and subclasses.

I did not introduce this way of checking for finite fields; I just moved it to a more specific __init__ method. Having said that, I wouldn't agree that using the category framework here is a good thing.

First, a finite field might be in different categories (e.g. FiniteFields or the future category of subfields of an algebraic closure of Fp that we were discussing at #8335); probably the polynomial ring constructor shouldn't have to care about that.

Second, one reason to have different implementations of PolynomialRing is so that we can take advantage of implementation details of (subclasses of) FiniteField. There already is an implementation for polynomials over NTL finite fields; similarly, for PARI finite fields it would be desirable to have an implementation for polynomials over those fields. (I have some code that is much slower than necessary because it uses PARI finite field elements but NTL polynomials over the same finite fields.)

comment:9 in reply to:  8 Changed 9 years ago by Jean-Pierre Flori

Replying to pbruin:

I did not introduce this way of checking for finite fields; I just moved it to a more specific __init__ method. Having said that, I wouldn't agree that using the category framework here is a good thing.

First, a finite field might be in different categories (e.g. FiniteFields or the future category of subfields of an algebraic closure of Fp that we were discussing at #8335); probably the polynomial ring constructor shouldn't have to care about that.

I'd say that a subfield of an algebraic closure would be in the category of finite fields and the new one, just as it is as well in that of integral domains.

Second, one reason to have different implementations of PolynomialRing is so that we can take advantage of implementation details of (subclasses of) FiniteField. There already is an implementation for polynomials over NTL finite fields; similarly, for PARI finite fields it would be desirable to have an implementation for polynomials over those fields. (I have some code that is much slower than necessary because it uses PARI finite field elements but NTL polynomials over the same finite fields.)

I agree, but I don't think the test performed by is_FiniteField is to ensure implementations details, but really the fact that the robject represents a finite field.

Anyway, as you pointed out you just moved the test so let's keep this for later.

If you fix the doc, I'll happily positive review that.

Changed 9 years ago by Jean-Pierre Flori

Attachment: trac_14832-reviewer.patch added

Reviewer patch.

comment:10 Changed 9 years ago by Jean-Pierre Flori

Description: modified (diff)
Status: needs_workpositive_review
Work issues: double colons, check for finite fields

comment:12 Changed 9 years ago by Peter Bruin

The patchbot doesn't get it:

Apply trac_14832-PolynomialRing_dense_finite_field.patch, trac_14832-irreducible_polynomial.patch, trac_14832-reviewer.patch

comment:13 Changed 9 years ago by Peter Bruin

Dependencies: #14817#14817, #14818
Description: modified (diff)

comment:14 Changed 9 years ago by Peter Bruin

Apply trac_14832-PolynomialRing_dense_finite_field.patch, trac_14832-irreducible_polynomial.patch, trac_14832-reviewer.patch

Changed 9 years ago by Peter Bruin

Attachment: trac_14832-doctest.patch added

add doctest

comment:15 Changed 9 years ago by Peter Bruin

Description: modified (diff)

comment:16 Changed 9 years ago by Jean-Pierre Flori

Just want to confirm that Peter's patch solves the patchbot rant and is correct.

comment:17 Changed 9 years ago by Jeroen Demeyer

Merged in: sage-5.12.beta1
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.