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: |
Description (last modified by )
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)
Change History (22)
Changed 8 years ago by
comment:1 Changed 8 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
- Description modified (diff)
comment:3 Changed 8 years ago by
- Cc caruso added
comment:4 Changed 8 years ago by
- Description modified (diff)
Moved finite field-specific code from PolynomialRing_field.__init__()
to PolynomialRing_dense_finite_field.__init__()
.
comment:5 follow-up: ↓ 8 Changed 8 years ago by
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
(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
- 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: ↓ 9 Changed 8 years ago by
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 F_{p} 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
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 F_{p} 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.
comment:10 Changed 8 years ago by
- Description modified (diff)
- Status changed from needs_work to positive_review
- Work issues double colons, check for finite fields deleted
comment:11 Changed 8 years ago by
For the patchbot, apply only:
comment:12 Changed 8 years ago by
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
- Dependencies changed from #14817 to #14817, #14818
- Description modified (diff)
comment:14 Changed 8 years ago by
Apply trac_14832-PolynomialRing_dense_finite_field.patch, trac_14832-irreducible_polynomial.patch, trac_14832-reviewer.patch
comment:15 Changed 8 years ago by
- Description modified (diff)
comment:16 Changed 8 years ago by
Just want to confirm that Peter's patch solves the patchbot rant and is correct.
comment:17 Changed 8 years ago by
- Merged in set to sage-5.12.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
based on 5.11.beta3