Opened 10 years ago

Closed 8 years ago

Add a splitting field function for polynomials over a finite field

Reported by: Owned by: abrochard davidloeffler major sage-6.1 algebra mmasdeu, jdemeyer Adrien Brochard, Peter Bruin Jeroen Demeyer N/A u/pbruin/13379-splitting_field cc3e50824cce699ba698408e024db20ce54a9b44 #8335, #2217

The purpose of this patch is to add the splitting_field() function to polynomial elements with coefficients in a finite field.

comment:1 Changed 10 years ago by abrochard

• Cc jdemeyer added; jason removed

comment:2 Changed 10 years ago by roed

Is this waiting on something, or should it be marked as needs review?

comment:3 Changed 10 years ago by abrochard

• Status changed from new to needs_review

comment:4 Changed 10 years ago by roed

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 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:6 in reply to: ↑ 5 ; follow-up: ↓ 7 Changed 9 years ago by 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...

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 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.

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...

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 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...

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.

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...

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 robharron

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().

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...

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.

Changed 9 years ago by pbruin

rewritten, based on 5.11.rc0 + #8335

comment:11 Changed 9 years ago by pbruin

• Authors set to Adrien Brochard, Peter Bruin
• 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 jdemeyer

• Milestone changed from sage-5.11 to sage-5.12

comment:13 Changed 8 years ago by jdemeyer

• Status changed from needs_review to needs_work

Conflicts with #2217.

comment:14 Changed 8 years ago by pbruin

• 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 pbruin

• 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 jdemeyer

You should add doctests for the `map` parameter in `extension`.

comment:17 Changed 8 years ago by jdemeyer

• Status changed from needs_review to needs_work

comment:18 Changed 8 years ago by git

• 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 pbruin

• 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 jdemeyer

• Reviewers set to Jeroen Demeyer
• Status changed from needs_review to positive_review

comment:21 Changed 8 years ago by vbraun

• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.