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

dkrenn · 2011-10-18T09:36:43Z

We have

sage: from sage.rings.finite_rings.finite_field_givaro import FiniteField_givaro
sage: F9 = FiniteField_givaro(9)
sage: F81 = FiniteField_givaro(81)
sage: F81(F9.gen())
Traceback (most recent call last):
...
NotImplementedError

so one should implement this. Incidentally I did that, patch follows.

Apply

attachment: trac_11938-5.11.beta1.patch

Depends on #13214

CC: @rbeezer @dimpase @jpflori @pjbruin @defeo

Component: finite rings

Keywords: finite field, givaro, Conway polynomial, conversion, coercion sd51

Author: Daniel Krenn

Reviewer: Jean-Pierre Flori

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

The text was updated successfully, but these errors were encountered:

dkrenn · 2011-10-18T09:45:55Z

comment:1

Attachment: trac_11938_conversion_gf_conway.patch.gz

Here comes the patch ;) Conversion is possible in both directions (up and down), see example below.

sage: from sage.rings.finite_rings.finite_field_givaro import FiniteField_givaro
sage: F4 = FiniteField_givaro(4,'b')
sage: F16 = FiniteField_givaro(16,'c')
sage: z = F4.gen() + F16.gen(); z
c^2
sage: z.parent()
Finite Field in c of size 2^4
sage: F4(z)
Traceback (most recent call last):
...
ValueError: c^2 is not a sub-field element            
sage: F4(z+F16.gen())
b

dkrenn · 2011-11-04T17:30:42Z

Author: Daniel Krenn

loefflerd · 2012-03-25T21:24:42Z

comment:3

I'm afraid this doesn't apply to the current Sage beta (see patchbot logs). I suspect it conflicts with #12084 (merged in 5.0.beta0).

loefflerd · 2012-03-25T21:24:42Z

Work Issues: needs rebase

dkrenn · 2012-04-15T12:48:56Z

Attachment: trac_11938_conversion_gf_conway.2.patch.gz

dkrenn · 2012-04-15T12:49:58Z

Changed work issues from needs rebase to none

dkrenn · 2012-04-15T12:51:45Z

Dependencies: #12084

dkrenn · 2012-04-15T12:51:45Z

comment:6

trac_11938_conversion_gf_conway.2.patch is on sage-5.0.beta13

ppurka · 2012-06-04T05:38:34Z

comment:7

This ticket actually fixes a nasty bug in the coding theory part.

sage: R = ReedSolomonCode(15,3,GF(16,'a'))
sage: R.minimum_distance()                
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/home/punarbasu/Installations/sage-5.1beta1.trac/devel/sage-main/<ipython console> in <module>()

/home/punarbasu/Installations/sage-5.1beta1.trac/local/lib/python2.7/site-packages/sage/misc/decorators.pyc in wrapper(*args, **kwds)
    685                     kwds[new_name] = kwds[old_name]
    686                     del kwds[old_name]
--> 687             return func(*args, **kwds)
    688 
    689         return wrapper

/home/punarbasu/Installations/sage-5.1beta1.trac/local/lib/python2.7/site-packages/sage/coding/linear_code.pyc in minimum_distance(self, algorithm)
   1890             return ZZ(d)
   1891         Gstr = "%s*Z(%s)^0"%(gapG, q)
-> 1892         return hamming_weight(min_wt_vec_gap(Gstr,n,k,F))
   1893 
   1894     def module_composition_factors(self, gp):

/home/punarbasu/Installations/sage-5.1beta1.trac/local/lib/python2.7/site-packages/sage/misc/decorators.pyc in wrapper(*args, **kwds)
    685                     kwds[new_name] = kwds[old_name]
    686                     del kwds[old_name]
--> 687             return func(*args, **kwds)
    688 
    689         return wrapper

/home/punarbasu/Installations/sage-5.1beta1.trac/local/lib/python2.7/site-packages/sage/coding/linear_code.pyc in min_wt_vec_gap(Gmat, n, k, F, algorithm)
    391         #print v,m,dist

    392         #print [gap.eval("v["+str(i+1)+"]") for i in range(n)]

--> 393         all.append([v._matrix_(F),m._matrix_(F),int(dist)])
    394     ans = all[0]
    395     for x in all:

/home/punarbasu/Installations/sage-5.1beta1.trac/local/lib/python2.7/site-packages/sage/interfaces/gap.pyc in _matrix_(self, R)
    859         from sage.matrix.matrix_space import MatrixSpace
    860         M = MatrixSpace(R, n, m)
--> 861         entries = [[R(self[r,c]) for c in range(1,m+1)] for r in range(1,n+1)]
    862         return M(entries)
    863 

/home/punarbasu/Installations/sage-5.1beta1.trac/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:8009)()

/home/punarbasu/Installations/sage-5.1beta1.trac/local/lib/python2.7/site-packages/sage/structure/coerce_maps.so in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3411)()

/home/punarbasu/Installations/sage-5.1beta1.trac/local/lib/python2.7/site-packages/sage/structure/coerce_maps.so in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3314)()

/home/punarbasu/Installations/sage-5.1beta1.trac/local/lib/python2.7/site-packages/sage/rings/finite_rings/finite_field_givaro.pyc in _element_constructor_(self, e)
    331             TypeError: unable to coerce from a finite field other than the prime subfield
    332         """
--> 333         return self._cache.element_from_data(e)
    334 
    335     def _coerce_map_from_(self, R):

/home/punarbasu/Installations/sage-5.1beta1.trac/local/lib/python2.7/site-packages/sage/rings/finite_rings/element_givaro.so in sage.rings.finite_rings.element_givaro.Cache_givaro.element_from_data (sage/rings/finite_rings/element_givaro.cpp:5957)()

/home/punarbasu/Installations/sage-5.1beta1.trac/local/lib/python2.7/site-packages/sage/rings/finite_rings/element_givaro.so in sage.rings.finite_rings.element_givaro.Cache_givaro.element_from_data (sage/rings/finite_rings/element_givaro.cpp:5458)()

/home/punarbasu/Installations/sage-5.1beta1.trac/local/lib/python2.7/site-packages/sage/interfaces/gap.pyc in gfq_gap_to_sage(x, F)
   1438     else:
   1439         g = K.multiplicative_generator()
-> 1440     return F(K(g**e))
   1441 
   1442 def intmod_gap_to_sage(x):

/home/punarbasu/Installations/sage-5.1beta1.trac/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:7974)()

/home/punarbasu/Installations/sage-5.1beta1.trac/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.convert_map_from (sage/structure/parent.c:15419)()

/home/punarbasu/Installations/sage-5.1beta1.trac/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.discover_convert_map_from (sage/structure/parent.c:15570)()

/home/punarbasu/Installations/sage-5.1beta1.trac/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.coerce_map_from (sage/structure/parent.c:14194)()

/home/punarbasu/Installations/sage-5.1beta1.trac/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.discover_coerce_map_from (sage/structure/parent.c:14589)()

/home/punarbasu/Installations/sage-5.1beta1.trac/local/lib/python2.7/site-packages/sage/structure/parent_old.so in sage.structure.parent_old.Parent._coerce_map_from_ (sage/structure/parent_old.c:6122)()

/home/punarbasu/Installations/sage-5.1beta1.trac/local/lib/python2.7/site-packages/sage/rings/finite_rings/finite_field_givaro.pyc in _coerce_map_from_(self, R)
    366                     # This is where we *would* do coercion from one nontrivial finite field to another...

    367                     # We use this error message for backward compatibility until #8335 is finished

--> 368                     raise TypeError, "unable to coerce from a finite field other than the prime subfield"
    369 
    370     def gen(self, n=0):

TypeError: unable to coerce from a finite field other than the prime subfield
sage:

After this patch:

sage: R = ReedSolomonCode(15,3,GF(16,'a'))
sage: R.minimum_distance()                
13

Perhaps someone more knowledgeable about conway polynomials and the finite field givaro code can properly review it.

I have just minor comments to make. It will be nice to have statements like

raise TypeError, "unable to convert from a finite field with different characteristic"

instead written as

raise TypeError("unable to convert from a finite field with different characteristic")

This will increase the compatibility with python3 (when Sage moves to python3 in the future).

ppurka · 2012-11-17T19:50:19Z

comment:10

Is it normal that the patch is failing it's own doctest? The current answer is negative of the previous answer. From the patchbot:

    sage: F81(F9.gen())
Expected:
    a^3 + a^2 + 2
Got:
    2*a^3 + 2*a^2 + 1

jpflori · 2013-01-04T10:37:53Z

comment:11

I think you might be interested in #8335 which should definitely get in as well and might even superseed what is done here (no time to look at the patches now, so sorry if that's wrong).

ppurka · 2013-01-04T10:46:03Z

comment:12

Replying to @jpflori:

I think you might be interested in #8335 which should definitely get in as well and might even superseed what is done here (no time to look at the patches now, so sorry if that's wrong).

Thanks for bringing this to our attention. All these nice patches are bitrotting while the functionality remains missing in Sage. I don't know much about the theory behind conway polynomials (or pseudo-conway polynomials that is being used in #8335), otherwise I might have tried to fix this.

jpflori · 2013-06-04T09:18:45Z

comment:13

Some of the stuff here might be more efficient for Givaro than what is provided in #8335, and you also give the opportunity to go down, i.e. from a field to a subfield which is not the case in #8335.

Nonetheless, I think both of these should be handled after #8335 gets merged.
First a general ticket to allow going down, and another one to provide optimized implementations for Givaro finite fields.

jpflori · 2013-06-20T14:03:46Z

Reviewed patch, rebased on top of #8335.

jpflori · 2013-06-20T14:05:05Z

Reviewer: Jean-Pierre Flori

jpflori · 2013-06-20T14:05:05Z

comment:15

Attachment: trac_11938-5.11.beta1.patch.gz

Rebased the patch on top of #8335, some fixes.
When #8335 gets in, this should as well.

jpflori · 2013-06-20T14:05:05Z

Changed dependencies from #12084 to #12084, #8335

pjbruin · 2013-07-13T21:08:41Z

Changed keywords from finite field, givaro, Conway polynomial, conversion to finite field, givaro, Conway polynomial, conversion, coercion sd51

pjbruin · 2013-08-05T15:40:38Z

comment:19

In the meantime, #8335 changed a lot and this patch does not apply anymore. On the other hand, after #8335, one can now do

sage: F9=GF(9,conway=True,prefix='z')      
sage: F81=GF(81,conway=True,prefix='z')    
sage: F81(F9.gen())                    
2*z4^3 + 2*z4^2 + 1

I want to advocate the viewpoint that this feature should only be enabled when a compatible system of finite fields is expressly requested, either using the conway=True syntax from #8335 or in the future using an algebraic closure (see #14990).

The fact that elements from F81 that are actually in F9 cannot yet be coerced down into F9 is not addressed by #8335, though. I guess this ticket is the place to solve that problem.

It is probably better to put this in FiniteField_base.pyx, since the feature is in principle implementation-independent.

One thing to think about: in the current patch, the down-conversion involves taking roots in the finite field. This might be the best way for finite fields that are implemented using Givaro, because it represents elements as powers of a generator of the multiplicative group. For general finite fields, it could be more efficient to write down the inclusion map as an F_p-linear map and to find the unique solution of the corresponding linear system.

pjbruin · 2013-08-13T09:21:45Z

Changed dependencies from #12084, #8335 to #13214

pjbruin · 2013-08-13T09:21:45Z

comment:20

I just finished reviewing (and slightly extending) #13214. It seems to me that the problem of mapping finite field elements into subfields is now solved in a more systematic way by #13214.

This is due to the following fact: if you have a coercion map K -> L and a section of this map, and if b is in L, typing K(b) will try to apply the section to b. Indeed, extending the example in comment:19, one can now type

sage: F9=GF(9, conway=True, prefix='z')      
sage: F81=GF(81, conway=True, prefix='z')    
sage: F81(F9.gen())                    
2*z4^3 + 2*z4^2 + 1
sage: F9(F81.gen()^10)
z2

Am I correct that #13214 (if positively reviewed) supersedes this ticket?

ppurka · 2013-08-13T09:27:25Z

comment:21

Indeed it looks like #13214 will supercede this.

jpflori · 2013-12-31T12:02:18Z

comment:23

I agree that this should be closed as wontfix.
The going stuff should be in the base class and not depend on the actual implementation.

dkrenn added this to the sage-5.11 milestone Oct 18, 2011

dkrenn added c: finite rings labels Oct 18, 2011

dkrenn assigned ClementPernet Oct 18, 2011

dkrenn added the s: needs review label Oct 18, 2011

loefflerd mannequin added s: needs work and removed s: needs review labels Mar 25, 2012

This comment has been minimized.

Sign in to view

dkrenn added s: needs review and removed s: needs work labels Apr 15, 2012

This comment has been minimized.

Sign in to view

ppurka added s: needs info and removed s: needs review labels Jan 4, 2013

This comment has been minimized.

Sign in to view

jpflori added s: needs review and removed s: needs info labels Jun 20, 2013

pjbruin removed the c: coercion label Jul 13, 2013

pjbruin added s: needs work and removed s: needs review labels Aug 5, 2013

pjbruin changed the title ~~FiniteField_givaro defined by Conway polynomials: conversion of elements from F_{p^n} to F_{p^m}~~ Finite fields defined by Conway polynomials: conversion of elements into subfields Aug 5, 2013

pjbruin added s: needs info and removed s: needs work labels Aug 13, 2013

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

jpflori added s: positive review and removed s: needs info labels Dec 31, 2013

jpflori removed this from the sage-6.1 milestone Dec 31, 2013

vbraun added r: wontfix and removed p: major / 3 labels Jan 4, 2014

vbraun closed this as completed Jan 4, 2014

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

dkrenn commented Oct 18, 2011

dkrenn commented Oct 18, 2011

dkrenn commented Nov 4, 2011

loefflerd mannequin commented Mar 25, 2012

loefflerd mannequin commented Mar 25, 2012

dkrenn commented Apr 15, 2012

This comment has been minimized.

dkrenn commented Apr 15, 2012

dkrenn commented Apr 15, 2012

dkrenn commented Apr 15, 2012

ppurka commented Jun 4, 2012

This comment has been minimized.

ppurka commented Nov 17, 2012

jpflori commented Jan 4, 2013

ppurka commented Jan 4, 2013

This comment has been minimized.

jpflori commented Jun 4, 2013

jpflori commented Jun 20, 2013

This comment has been minimized.

jpflori commented Jun 20, 2013

jpflori commented Jun 20, 2013

jpflori commented Jun 20, 2013

pjbruin commented Jul 13, 2013

pjbruin commented Aug 5, 2013

pjbruin commented Aug 13, 2013

pjbruin commented Aug 13, 2013

ppurka commented Aug 13, 2013

jpflori commented Dec 31, 2013

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

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

Comments

dkrenn commented Oct 18, 2011

dkrenn commented Oct 18, 2011

dkrenn commented Nov 4, 2011

loefflerd mannequin commented Mar 25, 2012

loefflerd mannequin commented Mar 25, 2012

dkrenn commented Apr 15, 2012

This comment has been minimized.

dkrenn commented Apr 15, 2012

dkrenn commented Apr 15, 2012

dkrenn commented Apr 15, 2012

ppurka commented Jun 4, 2012

This comment has been minimized.

ppurka commented Nov 17, 2012

jpflori commented Jan 4, 2013

ppurka commented Jan 4, 2013

This comment has been minimized.

jpflori commented Jun 4, 2013

jpflori commented Jun 20, 2013

This comment has been minimized.

jpflori commented Jun 20, 2013

jpflori commented Jun 20, 2013

jpflori commented Jun 20, 2013

pjbruin commented Jul 13, 2013

pjbruin commented Aug 5, 2013

pjbruin commented Aug 13, 2013

pjbruin commented Aug 13, 2013

ppurka commented Aug 13, 2013

jpflori commented Dec 31, 2013