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:  sage6.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/13379splitting_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 followup: ↓ 6 Changed 9 years ago by
For p a prime and q = p^{n}, the field F_{q} is Galois over F_{p}, i.e. it is the splitting field of any irreducible polynomial of degree n over F_{p}. Moreover, the field with p^{n} elements contains the one with p^{m} elements if and only if m divides n. Thus, starting from a polynomial over F_{p}, 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 F_{q}, a simple modification of what I've said would work too.
comment:6 in reply to: ↑ 5 ; followup: ↓ 7 Changed 9 years ago by
I think that the whole point is to return an embedding of F_{q} 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 = p^{n}, the field F_{q} is Galois over F_{p}, i.e. it is the splitting field of any irreducible polynomial of degree n over F_{p}. Moreover, the field with p^{n} elements contains the one with p^{m} elements if and only if m divides n. Thus, starting from a polynomial over F_{p}, 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 F_{q}, a simple modification of what I've said would work too.
comment:7 in reply to: ↑ 6 ; followup: ↓ 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 F_{q} 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 = p^{n}, the field F_{q} is Galois over F_{p}, i.e. it is the splitting field of any irreducible polynomial of degree n over F_{p}. Moreover, the field with p^{n} elements contains the one with p^{m} elements if and only if m divides n. Thus, starting from a polynomial over F_{p}, 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 F_{q}, a simple modification of what I've said would work too.
comment:8 in reply to: ↑ 7 ; followup: ↓ 9 Changed 9 years ago by
Yes, I agree that for polynomials defined over F_{p} the function should be simplified. As for F_{q} 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 F_{q} 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 = p^{n}, the field F_{q} is Galois over F_{p}, i.e. it is the splitting field of any irreducible polynomial of degree n over F_{p}. Moreover, the field with p^{n} elements contains the one with p^{m} elements if and only if m divides n. Thus, starting from a polynomial over F_{p}, 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 F_{q}, a simple modification of what I've said would work too.
comment:9 in reply to: ↑ 8 Changed 9 years ago by
No, for F_{q} 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 F_{q} is elsewhere: some coercion problem when calling poly.change_ring().
Replying to mmasdeu:
Yes, I agree that for polynomials defined over F_{p} the function should be simplified. As for F_{q} 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 sage5.11 to sage5.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/13379splitting_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?