Opened 8 years ago

Closed 8 years ago

#14832 closed enhancement (fixed)

Unified construction of irreducible polynomials over finite fields

Reported by: pbruin Owned by: cpernet
Priority: major Milestone: sage-5.12
Component: finite rings Keywords: polynomials
Cc: 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 pbruin)

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 pbruin 8 years ago.
based on 5.11.beta3
trac_14832-PolynomialRing_dense_finite_field.patch (4.9 KB) - added by pbruin 8 years ago.
new class for polynomial rings over finite fields
trac_14832-irreducible_polynomial.patch (8.5 KB) - added by pbruin 8 years ago.
method irreducible_element()
trac_14832-reviewer.patch (2.1 KB) - added by jpflori 8 years ago.
Reviewer patch.
trac_14832-doctest.patch (1.3 KB) - added by pbruin 8 years ago.
add doctest

Download all attachments as: .zip

Change History (22)

Changed 8 years ago by pbruin

based on 5.11.beta3

comment:1 Changed 8 years ago by pbruin

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 8 years ago by pbruin

  • Description modified (diff)

comment:3 Changed 8 years ago by caruso

  • Cc caruso added

comment:4 Changed 8 years ago by pbruin

  • Description modified (diff)

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

Changed 8 years ago by pbruin

new class for polynomial rings over finite fields

Changed 8 years ago by pbruin

method irreducible_element()

comment:5 follow-up: Changed 8 years ago by 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?

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 8 years ago by jpflori

(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 8 years ago by jpflori

  • Reviewers set to Jean-Pierre Flori
  • Status changed from needs_review to needs_work
  • Work issues set to 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 ; follow-up: Changed 8 years ago by pbruin

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 8 years ago by jpflori

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 8 years ago by jpflori

Reviewer patch.

comment:10 Changed 8 years ago by jpflori

  • Description modified (diff)
  • Status changed from needs_work to positive_review
  • Work issues double colons, check for finite fields deleted

comment:12 Changed 8 years ago by pbruin

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 8 years ago by pbruin

  • Dependencies changed from #14817 to #14817, #14818
  • Description modified (diff)

comment:14 Changed 8 years ago by pbruin

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

Changed 8 years ago by pbruin

add doctest

comment:15 Changed 8 years ago by pbruin

  • Description modified (diff)

comment:16 Changed 8 years ago by jpflori

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

comment:17 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.12.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.