Opened 9 years ago
Closed 7 years ago
#13214 closed enhancement (fixed)
Finite field homomorphisms and Frobenius endomorphisms
Reported by: | caruso | Owned by: | AlexGhitza |
---|---|---|---|
Priority: | major | Milestone: | sage-5.13 |
Component: | finite rings | Keywords: | frobenius finite fields sd51 |
Cc: | tfeulner, caruso, darij, jpflori, pbruin, defeo, JCooley, dfesti | Merged in: | sage-5.13.beta2 |
Authors: | Xavier Caruso, Peter Bruin | Reviewers: | Paul Zimmermann, Peter Bruin, Volker Braun |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #8335 | Stopgaps: |
Description (last modified by )
Here is a patch implementing:
- Frobenius endomorphisms over finite fields (generic implementation, plus special implementations for prime finite fields and givaro finite fields)
- embeddings between finite fields (with again a special implementation for givaro finite fields)
- hashing and rich comparisons for general morphisms
Apply: trac_13214-folded.patch
Attachments (4)
Change History (47)
comment:1 Changed 9 years ago by
- Status changed from new to needs_review
comment:2 Changed 9 years ago by
comment:3 Changed 9 years ago by
- Cc tfeulner added
comment:4 Changed 9 years ago by
Xavier, if I define an element of GF(q^{2}) which is in fact an element of GF(q), will this patch enable to convert it efficiently to the smaller field? If so, please can you tell me how?
Paul
comment:5 Changed 9 years ago by
Oh sorry, I forgot *.pxd files. Thanks!
Paul, the answer to your question is probably yes... at least if q is small enough so that you can work with givaro fields (otherwise, it won't be so efficient).
Actually, I have not implemented automatic coercions between finite fields (essentially because embeddings between finite fields are not canonical). As a consequence it's not so easy to create embeddings. Nevertheless, here is what you can do:
sage: K.<x> = GF(5^3) sage: L.<y> = GF(5^6) sage: from sage.rings.finite_rings.hom_finite_field_givaro import FiniteFieldEmbedding_givaro sage: f = FiniteFieldEmbedding_givaro(K,L); f Embedding of Finite Field in x of size 5^3 into Finite Field in y of size 5^6 sage: g = f.section(); g Section of Embedding of Finite Field in x of size 5^3 into Finite Field in y of size 5^6 sage: g(y^126) 3*x^2 + 1 sage: g(y) Traceback (most recent call last): ... ValueError: y is not in the image of Embedding of Finite Field in x of size 5^3 into Finite Field in y of size 5^6
If you are sure that you won't never use another embedding of K into L, you can even define f as a coerce map as follows:
sage: K._unset_coercions_used() sage: K._populate_coercion_lists_(embedding=f)
Then the following will work:
sage: L(x) 2*y^5 + 3*y^4 + 3*y^2 + y + 2 sage: z = x*y; z 3*y^5 + 3*y^4 + 4*y^2 + 2*y + 1 sage: K(z/y) x sage: K(y) Traceback (most recent call last): ... ValueError: y is not in the image of Embedding of Finite Field in x of size 5^3 into Finite Field in y of size 5^6
comment:6 Changed 9 years ago by
- Cc caruso added
comment:7 Changed 9 years ago by
Please fill in your real name as Author.
comment:8 Changed 9 years ago by
comment:9 Changed 9 years ago by
Xavier, I tried to apply the patch on top of Sage 5.1 but got:
sage: hg_sage.import_patch("trac_13214_hom_finite_field.patch") cd "/usr/local/sage-5.1-linux-64bit-ubuntu_12.04_lts-x86_64-Linux/devel/sage" && sage --hg import "/tmp/trac_13214_hom_finite_field.patch" applying /tmp/trac_13214_hom_finite_field.patch ** unknown exception encountered, please report by visiting ** http://mercurial.selenic.com/wiki/BugTracker ** Python 2.7.3 (default, Jul 9 2012, 15:05:17) [GCC 4.6.3] ** Mercurial Distributed SCM (version 1.8.4) ** Extensions loaded: color, mq, pager, rebase, relink Traceback (most recent call last): File "/usr/local/sage-5.1-linux-64bit-ubuntu_12.04_lts-x86_64-Linux/local/bin/hg", line 38, in <module> mercurial.dispatch.run() File "/usr/local/sage-5.1-linux-64bit-ubuntu_12.04_lts-x86_64-Linux/local/lib/python/mercurial/dispatch.py", line 16, in run sys.exit(dispatch(sys.argv[1:])) File "/usr/local/sage-5.1-linux-64bit-ubuntu_12.04_lts-x86_64-Linux/local/lib/python/mercurial/dispatch.py", line 36, in dispatch return _runcatch(u, args) ... File "/usr/local/sage-5.1-linux-64bit-ubuntu_12.04_lts-x86_64-Linux/local/lib/python/mercurial/patch.py", line 339, in readgitpatch gp.setmode(int(line[-6:], 8)) ValueError: invalid literal for int() with base 8: '</pre>'
Should I apply it on top of Sage 5.2 or later?
Paul
comment:10 Changed 9 years ago by
please discard my last comment, I downloaded the patch in html form...
Paul
comment:11 Changed 9 years ago by
- Reviewers set to Paul Zimmermann
- Status changed from needs_review to needs_work
- Work issues set to failing doctests
on top of Sage 5.1 I get the following failures with this patch:
sage -t devel/sage-13214/sage/categories/modules_with_basis.py # 3 doctests failed sage -t devel/sage-13214/sage/rings/finite_rings/finite_field_base.pyx # 2 doctests failed sage -t devel/sage-13214/sage/rings/finite_rings/finite_field_givaro.py # 2 doctests failed sage -t devel/sage-13214/sage/rings/finite_rings/hom_finite_field.pyx # 2 doctests failed
Paul
comment:12 follow-up: ↓ 13 Changed 9 years ago by
Dear Paul,
I cannot reproduce the three last failures on my computer[*]. Could you please give me the complete output of 'sage -t'?
[*] I'm currently working with sage 5.1.rc0; it's probably the reason.
comment:13 in reply to: ↑ 12 Changed 9 years ago by
These are the failures Paul observed (here on Sage 5.3) with this patch:
sage -t "devel/sage-codecan/sage/categories/modules_with_basis.py" ********************************************************************** File "devel/sage-codecan/sage/categories/modules_with_basis.py", line 1149: sage: TestSuite(phi).run() # known issue Expected: Failure in _test_category: ... The following tests failed: _test_category Got: Failure in _test_category: Traceback (most recent call last): File "local/lib/python/site-packages/sage/misc/sage_unittest.py", line 275, in run test_method(tester = tester) File "element.pyx", line 499, in sage.structure.element.Element._test_category (sage/structure/element.c:4702) File "local/lib/python2.7/unittest/case.py", line 420, in assertTrue raise self.failureException(msg) AssertionError: False is not true ------------------------------------------------------------ Failure in _test_eq: Traceback (most recent call last): File "local/lib/python/site-packages/sage/misc/sage_unittest.py", line 275, in run test_method(tester = tester) File "element.pyx", line 545, in sage.structure.element.Element._test_eq (sage/structure/element.c:4907) File "morphism.pyx", line 214, in sage.categories.morphism.Morphism.__richcmp__ (sage/categories/morphism.c:3398) File "element.pyx", line 876, in sage.structure.element.Element._richcmp (sage/structure/element.c:8370) File "element.pyx", line 923, in sage.structure.element.Element._richcmp_c_impl (sage/structure/element.c:8671) File "morphism.pyx", line 228, in sage.categories.morphism.Morphism._cmp_c_impl (sage/categories/morphism.c:3708) NotImplementedError ------------------------------------------------------------ The following tests failed: _test_category, _test_eq ********************************************************************** File "devel/sage-codecan/sage/categories/modules_with_basis.py", line 1384: sage: TestSuite(phi).run() # known issue; see ModuleMorphism above Expected: Failure in _test_category: ... The following tests failed: _test_category Got: Failure in _test_category: Traceback (most recent call last): File "local/lib/python/site-packages/sage/misc/sage_unittest.py", line 275, in run test_method(tester = tester) File "element.pyx", line 499, in sage.structure.element.Element._test_category (sage/structure/element.c:4702) File "local/lib/python2.7/unittest/case.py", line 420, in assertTrue raise self.failureException(msg) AssertionError: False is not true ------------------------------------------------------------ Failure in _test_eq: Traceback (most recent call last): File "local/lib/python/site-packages/sage/misc/sage_unittest.py", line 275, in run test_method(tester = tester) File "element.pyx", line 545, in sage.structure.element.Element._test_eq (sage/structure/element.c:4907) File "morphism.pyx", line 214, in sage.categories.morphism.Morphism.__richcmp__ (sage/categories/morphism.c:3398) File "element.pyx", line 876, in sage.structure.element.Element._richcmp (sage/structure/element.c:8370) File "element.pyx", line 923, in sage.structure.element.Element._richcmp_c_impl (sage/structure/element.c:8671) File "morphism.pyx", line 228, in sage.categories.morphism.Morphism._cmp_c_impl (sage/categories/morphism.c:3708) NotImplementedError ------------------------------------------------------------ The following tests failed: _test_category, _test_eq ********************************************************************** File "devel/sage-codecan/sage/categories/modules_with_basis.py", line 1762: sage: TestSuite(phi).run() # known issue; see ModuleMorphismByLinearity.__init__ Expected: Failure in _test_category: ... The following tests failed: _test_category Got: Failure in _test_category: Traceback (most recent call last): File "local/lib/python/site-packages/sage/misc/sage_unittest.py", line 275, in run test_method(tester = tester) File "element.pyx", line 499, in sage.structure.element.Element._test_category (sage/structure/element.c:4702) File "local/lib/python2.7/unittest/case.py", line 420, in assertTrue raise self.failureException(msg) AssertionError: False is not true ------------------------------------------------------------ Failure in _test_eq: Traceback (most recent call last): File "local/lib/python/site-packages/sage/misc/sage_unittest.py", line 275, in run test_method(tester = tester) File "element.pyx", line 545, in sage.structure.element.Element._test_eq (sage/structure/element.c:4907) File "morphism.pyx", line 214, in sage.categories.morphism.Morphism.__richcmp__ (sage/categories/morphism.c:3398) File "element.pyx", line 876, in sage.structure.element.Element._richcmp (sage/structure/element.c:8370) File "element.pyx", line 923, in sage.structure.element.Element._richcmp_c_impl (sage/structure/element.c:8671) File "morphism.pyx", line 228, in sage.categories.morphism.Morphism._cmp_c_impl (sage/categories/morphism.c:3708) NotImplementedError ------------------------------------------------------------ The following tests failed: _test_category, _test_eq ********************************************************************** 3 items had failures: 1 of 8 in __main__.example_40 1 of 9 in __main__.example_45 1 of 9 in __main__.example_55 ***Test Failed*** 3 failures.
sage -t "devel/sage-codecan/sage/rings/finite_rings/finite_field_base.pyx" ********************************************************************** File "devel/sage-codecan/sage/rings/finite_rings/finite_field_base.pyx", line 793: sage: k.frobenius_endomorphism(6) == Frob Expected: True Got: False ********************************************************************** File "devel/sage-codecan/sage/rings/finite_rings/finite_field_base.pyx", line 796: sage: k.frobenius_endomorphism(5) == IdentityMorphism(k) Expected: True Got: False ********************************************************************** 1 items had failures: 2 of 13 in __main__.example_38
sage -t "devel/sage-codecan/sage/rings/finite_rings/finite_field_givaro.py" ********************************************************************** File "devel/sage-codecan/sage/rings/finite_rings/finite_field_givaro.py", line 651: sage: k.frobenius_endomorphism(6) == Frob Expected: True Got: False ********************************************************************** File "devel/sage-codecan/sage/rings/finite_rings/finite_field_givaro.py", line 654: sage: k.frobenius_endomorphism(5) == IdentityMorphism(k) Expected: True Got: False ********************************************************************** 1 items had failures: 2 of 13 in __main__.example_21 ***Test Failed*** 2 failures.
sage -t "devel/sage-codecan/sage/rings/finite_rings/hom_finite_field.pyx" ********************************************************************** File "devel/sage-codecan/sage/rings/finite_rings/hom_finite_field.pyx", line 74: sage: Frob == Frob^15 Expected: True Got: False ********************************************************************** File "devel/sage-codecan/sage/rings/finite_rings/hom_finite_field.pyx", line 76: sage: Frob^14 == Hom(k,k).identity() Expected: True Got: False ********************************************************************** 1 items had failures: 2 of 26 in __main__.example_0 ***Test Failed*** 2 failures.
Changed 8 years ago by
comment:14 Changed 8 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
I changed the coercion in sage/rings/finite_rings/homset.py. Now, this patch passes all doctests except for the one documented in sage/categories/modules_with_basis.py. I did not change the error messages there, because I wanted to discuss the failure first.
comment:15 Changed 8 years ago by
- Dependencies set to #13184
- Description modified (diff)
Thanks for catching this!
I now understand why I didn't see this failure: it's just because this patch actually depends on #13184 and that the corresponding patch was applied on my computer. Sorry for this!
I also attach a new version of my patch fixing the problem in modules_with_basis.py; I'm not really happy with my solution (but it has the advantage to be very short). Please let me now if you have some comment!
comment:16 Changed 8 years ago by
- Work issues failing doctests deleted
comment:17 Changed 8 years ago by
for the bot:
Apply trac_13214_hom_finite_field.2.patch
comment:18 Changed 8 years ago by
- Dependencies #13184 deleted
let me remove the dependency to #13184 from the ticket description and see what happens (waiting for the bot to run)
comment:19 Changed 8 years ago by
- Dependencies set to #13184
- Description modified (diff)
let us now try with dependency to #13184 put back
for the bot:
apply trac_13214_hom_finite_field.patch
comment:20 Changed 8 years ago by
- Status changed from needs_review to needs_work
- Work issues set to does not build
please provide a patch that applies, builds and pass all tests
comment:21 Changed 8 years ago by
- Cc darij added
comment:22 Changed 8 years ago by
- Cc jpflori added
Not sure how this relates to #8335, but it might be worth having a look there.
Changed 8 years ago by
comment:23 Changed 8 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
I've just posted a patch that should apply on sage-5.10 (let's wait and see).
Jean-Pierre, I was actually not aware about your work with David Roe on lattices of finite fields. I had a quick look at what you have implemented. Unfortunately, it seems to me that our philosophy is a bit different: if I understand correctly, you are trying to make all finite fields canonical whereas my idea was to ask explicitely to the user which embeddings (between finite fields) are canonical and which ones are not.
But, you're right. We should definitely understand precisely how our respective patches relate and merge them if necessary (or discard one of them, i.e. mine).
Note: Actually, my main motivation for this patch was to implement Frobenius endomorphisms. I think you patch does not provide this functionality. Is that correct?
comment:24 Changed 8 years ago by
I agree that the purposes of both patches are quite orthogonal: the point of our patch is a first step toward having compatible embeddings in lattices of finite fields automatically, i.e. mimic what Magma does where the user does not have to pay attention to such things and it just works.
And I feel we should merge both patches if possible, even if at some later point it could make sense to refactor some pieces of code.
comment:25 follow-up: ↓ 29 Changed 8 years ago by
- Cc pbruin added
This looks interesting. One question at the moment: it does not appear to relate to the basic functionality that currently exists (in sage/rings/finite_rings/homset.py
). Is that intentional? I can already type, for example,
sage: F9.<a>=GF(3^2) sage: F81.<b>=GF(3^4) sage: f=F9.hom((b^10,)) sage: f Ring morphism: From: Finite Field in a of size 3^2 To: Finite Field in b of size 3^4 Defn: a |--> 2*b^3 + 2*b^2 + 1 sage: f(a^2+a) b^3 + b^2 sage: type(f) <class 'sage.rings.finite_rings.homset.FiniteFieldHomomorphism_im_gens'>
comment:26 follow-up: ↓ 27 Changed 8 years ago by
As for the differing purposes of the two approaches, there should probably be two categories into which a finite field can be put:
- the category of all finite fields. In this category, between any two objects there are either several morphisms or none at all, but no canonical one.
- the category of finite subfields of a given algebraic closure of F_{p}. In this category there is at most one morphism beteen any two objects, namely the inclusion qua subfields of the given algebraic closure.
comment:27 in reply to: ↑ 26 ; follow-up: ↓ 28 Changed 8 years ago by
Replying to pbruin:
As for the differing purposes of the two approaches, there should probably be two categories into which a finite field can be put:
- the category of all finite fields. In this category, between any two objects there are either several morphisms or none at all, but no canonical one.
Which is basically what we currently have and also what this ticket does.
- the category of finite subfields of a given algebraic closure of F_{p}. In this category there is at most one morphism beteen any two objects, namely the inclusion qua subfields of the given algebraic closure.
I would like this to be the default at some point, just like in Magma, not because I want to replicate Magma but for usual computations it seems a more practical choice. #8335 provides such an imlementation, though it not really practical for large fields and there is no proper categorical framework as you suggest.
This framework could be implemented in an independent ticket (and should if we want to be able to merge some tickets in a finite amount of time).
comment:28 in reply to: ↑ 27 Changed 8 years ago by
Replying to jpflori:
Which is basically what we currently have and also what this ticket does.
Yes, and precisely for this reason I think it is important to have a clear picture of what belongs in the "category of all finite fields" framework, what belongs in the future "finite subfields of a given algebraic closure" framework, and what is independent of the framework. Among the category-independent things would certainly be the various classes implementing the interfaces to FLINT, Givaro, NTL and PARI, and to a large extent the FiniteField
base class itself.
- the category of finite subfields of a given algebraic closure of F_{p}. In this category there is at most one morphism beteen any two objects, namely the inclusion qua subfields of the given algebraic closure.
I would like this to be the default at some point, just like in Magma, not because I want to replicate Magma but for usual computations it seems a more practical choice.
That probably depends strongly on the application. Often one just needs to work with a single finite field. In such cases it would be nicer if creating this field would give you a sparse polynomial for efficiency, not one that has been constructed to fit in an algebraic closure that you are unlikely to use.
Of course it would be best if one could do both at the same time, like Magma (see references at #8751), by having an implementation that allows using sparse polynomials while still being able to put the fields in a compatible system/algebraic closure. However, that should probably be done on top of the distinction between the two categories mentioned above, not by muddling this distinction.
comment:29 in reply to: ↑ 25 Changed 8 years ago by
Replying to pbruin:
This looks interesting. One question at the moment: it does not appear to relate to the basic functionality that currently exists (in
sage/rings/finite_rings/homset.py
). Is that intentional?
Yes, more or less.
Actually, my first motivation was to implement Frobenius endomorphism and, according to me, FrobeniusEndomorphism? should not derive from RingHomomorphism_im_gens. Indeed, defining Frobenius endomorphisms by giving its value on the generator is not really appropriate for many operations we would like to perform (i.e. evaluation if the field has a small characteristic and a big size, composition, computation of the order or of the subfield of fixed points).
On the other hand, I agree that it makes sense to derive the various classes of embeddings from FiniteFieldHomomorphism_im_gens. I can actually change this if you think that it is better.
As for the differing purposes of the two approaches, there should probably be two categories into which a finite field can be put:
- the category of all finite fields. In this category, between any two objects there are either several morphisms or none at all, but no canonical one.
- the category of finite subfields of a given algebraic closure of F_{p}. In this category there is at most one morphism beteen any two objects, namely the inclusion qua subfields of the given algebraic closure.
This sounds good. And the second category should be a subcategory of the first one, right (a finite subfield of a given algebraic closure of F_{p} is in particular a finite field)? If so, all category-independant functions should go to the first category (even if the second one is the default, as suggested by Jean-Pierre). This is the case in particular for Frobenius endomorphisms.
comment:30 Changed 8 years ago by
- Cc defeo added
comment:31 Changed 8 years ago by
- Keywords sd51 added
- Work issues does not build deleted
This might be a good target for Sage Days 51 (22-26 July, http://wiki.sagemath.org/sagedaysleiden). For now I just checked that the patch applies to 5.11.beta3 (with some fuzz) and passes doctests. I got one failure (a different embedding than expected is generated), probably because I am working under #14888.
comment:32 Changed 8 years ago by
Apply trac_13214_hom_finite_field.patch
(for patchbot)
comment:33 Changed 8 years ago by
for the bot:
apply only trac_13214_hom_finite_field.patch
comment:34 Changed 8 years ago by
- Cc JCooley dfesti added
- Component changed from basic arithmetic to finite rings
- Dependencies changed from #13184 to #8335
- Description modified (diff)
- Reviewers changed from Paul Zimmermann to Paul Zimmermann, Peter Bruin
- Summary changed from Frobenius endomorphism over finite fields to Finite field homomorphisms and Frobenius endomorphisms
In principle I am giving this a positive review, but since the reviewer patch I just uploaded contains some non-trivial changes, I think it is best if someone else reviews those changes first.
Summary of changes in trac_13214-reviewer.patch:
- Do not add
inverse()
method toSection
; it is currently not used and does not seem to be the best name, since its return value (the original map) is only a one-sided inverse. - Add method
gens()
toCombinatorialFreeModule
to fix a doctest failure inmodules_with_basis.py
. I guess this is the same failure discussed in comment:14 above. - Rename
[Section]FiniteFieldEmbedding_*
to[Section]FiniteFieldHomomorphism_*
; even though finite field homomorphisms are automatically injective, I think "homomorphism" fits better with existing code. Furthermore, to me "embedding" makes it sound too much like finite field homomorphisms are canonical. - Derive
FiniteFieldHomomorphism_generic
fromRingHomomorphism_im_gens
as suggested above. - Replace the existing
FiniteFieldHomomorphism_im_gens
by the newFiniteFieldHomomorphism_generic
. - Better integration of the new code into the existing finite field code.
- Remove the
_repr_()
method ofFiniteFieldHomomorphism_generic
, so that the output is the same as for the oldFiniteFieldHomomorphism_im_gens
. - Do not automatically generate a section for every finite field homomorphism.
- Numerous whitespace edits and some other typographical changes.
Changed 8 years ago by
for convenience: unified patch combining trac_13214_hom_finite_field.patch and trac_13214-reviewer.patch
comment:35 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:37 Changed 8 years ago by
- Milestone changed from sage-5.12 to sage-5.13
comment:38 follow-ups: ↓ 39 ↓ 40 Changed 8 years ago by
I'm currently at Sage Days 53 and could spare some time on this one... unless Luca is nearing completion of his review?
If I understand correctly, what needs to be done is to check Peter's changes as he already went over what Xavier did?
comment:39 in reply to: ↑ 38 Changed 8 years ago by
Replying to jpflori:
I'm currently at Sage Days 53 and could spare some time on this one... unless Luca is nearing completion of his review?
I'm rather nearing completion of the new class I'm starting next week... so feel free to go ahead :)
comment:40 in reply to: ↑ 38 Changed 8 years ago by
Replying to jpflori:
I'm currently at Sage Days 53 and could spare some time on this one... unless Luca is nearing completion of his review?
If I understand correctly, what needs to be done is to check Peter's changes as he already went over what Xavier did?
Yes, it would be nice if you could take a look either at my reviewer patch or at the combined one (the combined patch is only a little larger and probably easier to review).
comment:41 Changed 7 years ago by
patchbot: only
Apply trac_13214-folded.patch
comment:42 Changed 7 years ago by
- Reviewers changed from Paul Zimmermann, Peter Bruin to Paul Zimmermann, Peter Bruin, Volker Braun
- Status changed from needs_review to positive_review
The review patch looks good to me.
comment:43 Changed 7 years ago by
- Merged in set to sage-5.13.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
I guess your patch should also contain some *.pxd files since I receive the following error message.