Finite field homomorphisms and Frobenius endomorphisms #13214

xcaruso · 2012-07-09T08:26:03Z

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: attachment: trac_13214-folded.patch

Depends on #8335

CC: @sagetrac-tfeulner @xcaruso @darijgr @jpflori @pjbruin @defeo @sagetrac-JCooley @sagetrac-dfesti

Component: finite rings

Keywords: frobenius finite fields sd51

Author: Xavier Caruso, Peter Bruin

Reviewer: Paul Zimmermann, Peter Bruin, Volker Braun

Merged: sage-5.13.beta2

Issue created by migration from https://trac.sagemath.org/ticket/13214

sagetrac-tfeulner · 2012-07-25T07:28:08Z

comment:2

I guess your patch should also contain some *.pxd files since I receive the following error message.

Building modified file sage/rings/finite_rings/hom_finite_field.pyx.
Traceback (most recent call last):
  File "setup.py", line 829, in <module>
    queue = compile_command_list(ext_modules, deps)
  File "setup.py", line 789, in compile_command_list
    dep_file, dep_time = deps.newest_dep(f,m)
  File "setup.py", line 696, in newest_dep
    for f in self.all_deps(filename, ext_module):
  File "setup.py", line 677, in all_deps
    for f in self.immediate_deps(filename, ext_module):
  File "setup.py", line 659, in immediate_deps
    self._deps[filename] = self.parse_deps(filename, ext_module)
  File "setup.py", line 647, in parse_deps
    raise IOError, msg
IOError: could not find dependency sage/rings/finite_rings/hom_finite_field.pxd included in sage/rings/finite_rings/hom_prime_finite_field.pyx.
Error installing modified sage library code.

zimmermann6 · 2012-07-25T16:32:58Z

comment:4

Xavier, if I define an element of GF(q²) 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

xcaruso · 2012-07-25T22:09:43Z

comment:5

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

jdemeyer · 2012-07-27T20:39:17Z

comment:7

Please fill in your real name as Author.

xcaruso · 2012-07-28T07:42:04Z

Author: Xavier Caruso

zimmermann6 · 2012-07-31T12:20:40Z

comment:9

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

zimmermann6 · 2012-08-01T06:27:19Z

comment:10

please discard my last comment, I downloaded the patch in html form...

Paul

zimmermann6 · 2012-08-01T11:14:50Z

Work Issues: failing doctests

zimmermann6 · 2012-08-01T11:14:50Z

Reviewer: Paul Zimmermann

zimmermann6 · 2012-08-01T11:14:50Z

comment:11

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

xcaruso · 2012-08-09T20:07:05Z

comment:12

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.

sagetrac-tfeulner · 2012-10-15T07:09:34Z

comment:13

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.

sagetrac-tfeulner · 2012-10-16T11:58:58Z

Attachment: trac_13214_hom_finite_field.2.patch.gz

sagetrac-tfeulner · 2012-10-16T12:00:37Z

comment:14

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.

xcaruso · 2012-10-22T13:40:46Z

comment:15

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!

xcaruso · 2012-10-22T13:40:46Z

Dependencies: #13184

xcaruso · 2012-10-22T13:41:30Z

Changed work issues from failing doctests to none

fchapoton · 2013-03-20T16:56:25Z

comment:17

for the bot:

Apply trac_13214_hom_finite_field.2.patch

pjbruin · 2013-08-13T08:55:11Z

Changed dependencies from #13184 to #8335

pjbruin · 2013-08-13T08:55:11Z

Changed author from Xavier Caruso to Xavier Caruso, Peter Bruin

pjbruin · 2013-08-13T08:55:11Z

comment:34

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 attachment: trac_13214-reviewer.patch:

Do not add inverse() method to Section; 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() to CombinatorialFreeModule to fix a doctest failure in modules_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 from RingHomomorphism_im_gens as suggested above.
Replace the existing FiniteFieldHomomorphism_im_gens by the new FiniteFieldHomomorphism_generic.
Better integration of the new code into the existing finite field code.
Remove the _repr_() method of FiniteFieldHomomorphism_generic, so that the output is the same as for the old FiniteFieldHomomorphism_im_gens.
Do not automatically generate a section for every finite field homomorphism.
Numerous whitespace edits and some other typographical changes.

pjbruin · 2013-08-13T08:58:29Z

Attachment: trac_13214-folded.patch.gz

for convenience: unified patch combining trac_13214_hom_finite_field.patch and trac_13214-reviewer.patch

fchapoton · 2013-08-21T08:45:46Z

comment:36

apply only trac_13214-folded.patch

jpflori · 2013-09-24T13:45:36Z

comment:38

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?

defeo · 2013-09-24T13:47:52Z

comment:39

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 :)

pjbruin · 2013-09-24T14:15:06Z

comment:40

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

vbraun · 2013-10-23T09:25:02Z

comment:41

patchbot: only

Apply trac_13214-folded.patch

vbraun · 2013-10-25T11:46:28Z

Changed reviewer from Paul Zimmermann, Peter Bruin to Paul Zimmermann, Peter Bruin, Volker Braun

vbraun · 2013-10-25T11:46:28Z

comment:42

The review patch looks good to me.

jdemeyer · 2013-10-31T19:16:00Z

Merged: sage-5.13.beta2

xcaruso added this to the sage-5.11 milestone Jul 9, 2012

xcaruso added c: basic arithmetic labels Jul 9, 2012

xcaruso assigned aghitza Jul 9, 2012

xcaruso added the s: needs review label Jul 9, 2012

zimmermann6 added s: needs work and removed s: needs review labels Aug 1, 2012

This comment has been minimized.

Sign in to view

sagetrac-tfeulner mannequin added s: needs review and removed s: needs work labels Oct 16, 2012

This comment has been minimized.

Sign in to view

pjbruin added c: finite rings and removed c: basic arithmetic labels Aug 13, 2013

pjbruin changed the title ~~Frobenius endomorphism over finite fields~~ Finite field homomorphisms and Frobenius endomorphisms Aug 13, 2013

jdemeyer modified the milestones: sage-5.11, sage-5.12 Aug 13, 2013

This comment has been minimized.

Sign in to view

pjbruin modified the milestones: sage-5.12, sage-5.13 Sep 6, 2013

vbraun added s: positive review and removed s: needs review labels Oct 25, 2013

jdemeyer removed the s: positive review label Oct 31, 2013

jdemeyer closed this as completed Oct 31, 2013

dkrenn mentioned this issue Jan 4, 2014

Finite fields defined by Conway polynomials: conversion of elements into subfields #11938

Closed

xcaruso mentioned this issue Oct 22, 2012

Skew polynomials #13215

Closed

pjbruin mentioned this issue Jan 15, 2018

Implement algebraic closures of finite fields #14990

Closed

darijgr mentioned this issue Dec 29, 2022

values() method for lazy families #15349

Open

defeo mentioned this issue Nov 29, 2017

Morphism.is_identity() ignores base ring endomorphisms #15478

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Finite field homomorphisms and Frobenius endomorphisms #13214

Finite field homomorphisms and Frobenius endomorphisms #13214

xcaruso commented Jul 9, 2012

sagetrac-tfeulner mannequin commented Jul 25, 2012

zimmermann6 commented Jul 25, 2012

xcaruso commented Jul 25, 2012

jdemeyer commented Jul 27, 2012

xcaruso commented Jul 28, 2012

zimmermann6 commented Jul 31, 2012

zimmermann6 commented Aug 1, 2012

zimmermann6 commented Aug 1, 2012

zimmermann6 commented Aug 1, 2012

zimmermann6 commented Aug 1, 2012

xcaruso commented Aug 9, 2012

sagetrac-tfeulner mannequin commented Oct 15, 2012

sagetrac-tfeulner mannequin commented Oct 16, 2012

This comment has been minimized.

sagetrac-tfeulner mannequin commented Oct 16, 2012

This comment has been minimized.

xcaruso commented Oct 22, 2012

xcaruso commented Oct 22, 2012

xcaruso commented Oct 22, 2012

fchapoton commented Mar 20, 2013

pjbruin commented Aug 13, 2013

This comment has been minimized.

pjbruin commented Aug 13, 2013

pjbruin commented Aug 13, 2013

pjbruin commented Aug 13, 2013

fchapoton commented Aug 21, 2013

This comment has been minimized.

jpflori commented Sep 24, 2013

defeo commented Sep 24, 2013

pjbruin commented Sep 24, 2013

vbraun commented Oct 23, 2013

vbraun commented Oct 25, 2013

vbraun commented Oct 25, 2013

jdemeyer commented Oct 31, 2013

Finite field homomorphisms and Frobenius endomorphisms #13214

Finite field homomorphisms and Frobenius endomorphisms #13214

Comments

xcaruso commented Jul 9, 2012

sagetrac-tfeulner mannequin commented Jul 25, 2012

zimmermann6 commented Jul 25, 2012

xcaruso commented Jul 25, 2012

jdemeyer commented Jul 27, 2012

xcaruso commented Jul 28, 2012

zimmermann6 commented Jul 31, 2012

zimmermann6 commented Aug 1, 2012

zimmermann6 commented Aug 1, 2012

zimmermann6 commented Aug 1, 2012

zimmermann6 commented Aug 1, 2012

xcaruso commented Aug 9, 2012

sagetrac-tfeulner mannequin commented Oct 15, 2012

sagetrac-tfeulner mannequin commented Oct 16, 2012

This comment has been minimized.

sagetrac-tfeulner mannequin commented Oct 16, 2012

This comment has been minimized.

xcaruso commented Oct 22, 2012

xcaruso commented Oct 22, 2012

xcaruso commented Oct 22, 2012

fchapoton commented Mar 20, 2013

pjbruin commented Aug 13, 2013

This comment has been minimized.

pjbruin commented Aug 13, 2013

pjbruin commented Aug 13, 2013

pjbruin commented Aug 13, 2013

fchapoton commented Aug 21, 2013

This comment has been minimized.

jpflori commented Sep 24, 2013

defeo commented Sep 24, 2013

pjbruin commented Sep 24, 2013

vbraun commented Oct 23, 2013

vbraun commented Oct 25, 2013

vbraun commented Oct 25, 2013

jdemeyer commented Oct 31, 2013