Opened 10 years ago
Closed 8 years ago
#13379 closed enhancement (fixed)
Add a splitting field function for polynomials over a finite field
Reported by: | abrochard | Owned by: | davidloeffler |
---|---|---|---|
Priority: | major | Milestone: | sage-6.1 |
Component: | algebra | Keywords: | |
Cc: | mmasdeu, jdemeyer | Merged in: | |
Authors: | Adrien Brochard, Peter Bruin | Reviewers: | Jeroen Demeyer |
Report Upstream: | N/A | Work issues: | |
Branch: | u/pbruin/13379-splitting_field (Commits, GitHub, GitLab) | Commit: | cc3e50824cce699ba698408e024db20ce54a9b44 |
Dependencies: | #8335, #2217 | Stopgaps: |
Description (last modified by )
The purpose of this patch is to add the splitting_field() function to polynomial elements with coefficients in a finite field.
See also #2217, the number field analogue of this ticket.
Attachments (2)
Change History (23)
Changed 10 years ago by
comment:1 Changed 10 years ago by
- Cc jdemeyer added; jason removed
comment:2 Changed 10 years ago by
comment:3 Changed 10 years ago by
- Status changed from new to needs_review
comment:4 Changed 10 years ago by
I haven't taken a look, but I'll just note that there are some whitespace issues: you added a TAB character in polynomial_element.pyx and there's trailing whitespace as well. See the report from the patchbot.
comment:5 follow-up: ↓ 6 Changed 9 years ago by
For p a prime and q = pn, the field Fq is Galois over Fp, i.e. it is the splitting field of any irreducible polynomial of degree n over Fp. Moreover, the field with pn elements contains the one with pm elements if and only if m divides n. Thus, starting from a polynomial over Fp, the splitting field is simply given by taking the lcm of the degrees of the factors. This would be quicker than what you are doing. If you start with a polynomial over Fq, a simple modification of what I've said would work too.
comment:6 in reply to: ↑ 5 ; follow-up: ↓ 7 Changed 9 years ago by
I think that the whole point is to return an embedding of Fq into its splitting field. For that, one has to be careful when constructing the extensions: either choosing the given polynomial (or a factor of it) to define the extension, or using some root finding algorithm.
Also, the patch fails in the last couple of Sage releases...
Replying to robharron:
For p a prime and q = pn, the field Fq is Galois over Fp, i.e. it is the splitting field of any irreducible polynomial of degree n over Fp. Moreover, the field with pn elements contains the one with pm elements if and only if m divides n. Thus, starting from a polynomial over Fp, the splitting field is simply given by taking the lcm of the degrees of the factors. This would be quicker than what you are doing. If you start with a polynomial over Fq, a simple modification of what I've said would work too.
comment:7 in reply to: ↑ 6 ; follow-up: ↓ 8 Changed 9 years ago by
But have you looked at the code? It doesn't do anything special with regards to the embedding. (Do you see something I don't?) In the end it simply says F.Hom(K)[0] (for instance, I think the code only runs when the polynomial is defined over a prime field, in which case the embedding returned is simply the canonical one sending 1 to 1). I just quickly wrote a function that does what I suggested and it works just fine and is quite quick.
Replying to mmasdeu:
I think that the whole point is to return an embedding of Fq into its splitting field. For that, one has to be careful when constructing the extensions: either choosing the given polynomial (or a factor of it) to define the extension, or using some root finding algorithm.
Also, the patch fails in the last couple of Sage releases...
Replying to robharron:
For p a prime and q = pn, the field Fq is Galois over Fp, i.e. it is the splitting field of any irreducible polynomial of degree n over Fp. Moreover, the field with pn elements contains the one with pm elements if and only if m divides n. Thus, starting from a polynomial over Fp, the splitting field is simply given by taking the lcm of the degrees of the factors. This would be quicker than what you are doing. If you start with a polynomial over Fq, a simple modification of what I've said would work too.
comment:8 in reply to: ↑ 7 ; follow-up: ↓ 9 Changed 9 years ago by
Yes, I agree that for polynomials defined over Fp the function should be simplified. As for Fq one definitely needs to fix the code, since that calling of Hom won't work...
Replying to robharron:
But have you looked at the code? It doesn't do anything special with regards to the embedding. (Do you see something I don't?) In the end it simply says F.Hom(K)[0] (for instance, I think the code only runs when the polynomial is defined over a prime field, in which case the embedding returned is simply the canonical one sending 1 to 1). I just quickly wrote a function that does what I suggested and it works just fine and is quite quick.
Replying to mmasdeu:
I think that the whole point is to return an embedding of Fq into its splitting field. For that, one has to be careful when constructing the extensions: either choosing the given polynomial (or a factor of it) to define the extension, or using some root finding algorithm.
Also, the patch fails in the last couple of Sage releases...
Replying to robharron:
For p a prime and q = pn, the field Fq is Galois over Fp, i.e. it is the splitting field of any irreducible polynomial of degree n over Fp. Moreover, the field with pn elements contains the one with pm elements if and only if m divides n. Thus, starting from a polynomial over Fp, the splitting field is simply given by taking the lcm of the degrees of the factors. This would be quicker than what you are doing. If you start with a polynomial over Fq, a simple modification of what I've said would work too.
comment:9 in reply to: ↑ 8 Changed 9 years ago by
No, for Fq the calling of Hom works:
sage: F = GF(3^4, 'z') sage: K = GF(3^12, 'zz') sage: F.Hom(K) Set of field embeddings from Finite Field in z of size 3^4 to Finite Field in zz of size 3^12 sage: F.Hom(K)[0] Ring morphism: From: Finite Field in z of size 3^4 To: Finite Field in zz of size 3^12 Defn: z |--> 2*zz^10 + zz^8 + 2*zz^7 + zz^6 + 2*zz^5 + zz^4 + 2*zz^3 + 2*zz^2 + zz + 2
The problem over Fq is elsewhere: some coercion problem when calling poly.change_ring().
Replying to mmasdeu:
Yes, I agree that for polynomials defined over Fp the function should be simplified. As for Fq one definitely needs to fix the code, since that calling of Hom won't work...
Replying to robharron:
But have you looked at the code? It doesn't do anything special with regards to the embedding. (Do you see something I don't?) In the end it simply says F.Hom(K)[0] (for instance, I think the code only runs when the polynomial is defined over a prime field, in which case the embedding returned is simply the canonical one sending 1 to 1). I just quickly wrote a function that does what I suggested and it works just fine and is quite quick.
comment:10 Changed 9 years ago by
- Cc pbruin added
comment:11 Changed 9 years ago by
- Cc pbruin removed
- Component changed from number fields to algebra
- Dependencies set to #8335
- Description modified (diff)
I was going to review this, but ended up wanting to change almost everything, so here is a new version. The doctests are the same as in the original, up to cosmetic changes.
The new implementation of this function is very short, as suggested by the above comments. It just computes the degree of the splitting field over the base field, and then calls the FiniteField_base.extension()
method implemented by #8335.
The map
flag from the original patch is currently not understood, but for more flexibility, any additional arguments are now passed to FiniteField_base.extension()
, which would be the right place to implement the map
parameter.
The currently unused parameters have been removed; this ticket will probably be merged before #2217, and that one might change dramatically for all we know.
comment:12 Changed 9 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:13 Changed 8 years ago by
- Status changed from needs_review to needs_work
Conflicts with #2217.
comment:14 Changed 8 years ago by
- Branch set to u/pbruin/13379-splitting_field
- Created changed from 08/18/12 17:43:29 to 08/18/12 17:43:29
- Modified changed from 01/06/14 10:16:36 to 01/06/14 10:16:36
comment:15 Changed 8 years ago by
- Commit set to 3058ab2e60973cec10b411cb98567fae21784e79
- Dependencies changed from #8335 to #8335, #2217
- Description modified (diff)
- Status changed from needs_work to needs_review
The map
option now also works for finite fields, based on a new method FiniteFieldHomset._an_element_()
.
New commits:
3058ab2 | Trac 13379: splitting field function for polynomials over finite fields
|
comment:16 Changed 8 years ago by
You should add doctests for the map
parameter in extension
.
comment:17 Changed 8 years ago by
- Status changed from needs_review to needs_work
comment:18 Changed 8 years ago by
- Commit changed from 3058ab2e60973cec10b411cb98567fae21784e79 to cc3e50824cce699ba698408e024db20ce54a9b44
Branch pushed to git repo; I updated commit sha1. New commits:
cc3e508 | document "map" flag of FiniteField.extension()
|
comment:19 Changed 8 years ago by
- Modified changed from 01/07/14 22:50:08 to 01/07/14 22:50:08
- Status changed from needs_work to needs_review
comment:20 Changed 8 years ago by
- Reviewers set to Jeroen Demeyer
- Status changed from needs_review to positive_review
comment:21 Changed 8 years ago by
- Resolution set to fixed
- Status changed from positive_review to closed
Is this waiting on something, or should it be marked as needs review?