Opened 7 years ago

Closed 5 years ago

#11938 closed enhancement (wontfix)

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

Reported by: dkrenn Owned by: cpernet
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: finite rings Keywords: finite field, givaro, Conway polynomial, conversion, coercion sd51
Cc: rbeezer, dimpase, jpflori, pbruin, defeo Merged in:
Authors: Daniel Krenn Reviewers: Jean-Pierre Flori
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #13214 Stopgaps:

Description (last modified by jpflori)

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

Attachments (3)

trac_11938_conversion_gf_conway.patch (5.4 KB) - added by dkrenn 7 years ago.
trac_11938_conversion_gf_conway.2.patch (6.3 KB) - added by dkrenn 7 years ago.
trac_11938-5.11.beta1.patch (6.4 KB) - added by jpflori 5 years ago.
Reviewed patch, rebased on top of #8335.

Download all attachments as: .zip

Change History (28)

Changed 7 years ago by dkrenn

comment:1 Changed 7 years ago by dkrenn

  • Status changed from new to needs_review

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

comment:2 Changed 7 years ago by dkrenn

  • Authors set to Daniel Krenn

comment:3 Changed 7 years ago by davidloeffler

  • Status changed from needs_review to needs_work
  • Work issues set to needs rebase

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

comment:4 Changed 7 years ago by rbeezer

  • Cc rbeezer added

Changed 7 years ago by dkrenn

comment:5 Changed 7 years ago by dkrenn

  • Description modified (diff)
  • Status changed from needs_work to needs_review
  • Work issues needs rebase deleted

comment:6 Changed 7 years ago by dkrenn

  • Dependencies set to #12084

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

comment:7 Changed 6 years ago by ppurka

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

comment:8 Changed 6 years ago by ppurka

  • Cc dimpase added

comment:9 Changed 6 years ago by dimpase

  • Description modified (diff)

comment:10 Changed 6 years ago by ppurka

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

comment:11 follow-up: Changed 6 years ago by 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).

comment:12 in reply to: ↑ 11 Changed 6 years ago by ppurka

  • Description modified (diff)
  • Status changed from needs_review to needs_info

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.

comment:13 Changed 5 years ago by jpflori

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.

comment:14 Changed 5 years ago by jpflori

  • Cc jpflori added

Changed 5 years ago by jpflori

Reviewed patch, rebased on top of #8335.

comment:15 Changed 5 years ago by jpflori

  • Dependencies changed from #12084 to #12084, #8335
  • Description modified (diff)
  • Reviewers set to Jean-Pierre Flori
  • Status changed from needs_info to needs_review

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

comment:16 Changed 5 years ago by pbruin

  • Cc pbruin added

comment:17 Changed 5 years ago by defeo

  • Cc defeo added

comment:18 Changed 5 years ago by pbruin

  • Keywords sd51 added

comment:19 Changed 5 years ago by pbruin

  • Status changed from needs_review to needs_work
  • Summary changed from FiniteField_givaro defined by Conway polynomials: conversion of elements from F_{p^n} to F_{p^m} to Finite fields defined by Conway polynomials: conversion of elements into subfields

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 Fp-linear map and to find the unique solution of the corresponding linear system.

comment:20 Changed 5 years ago by pbruin

  • Dependencies changed from #12084, #8335 to #13214
  • Status changed from needs_work to needs_info

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?

Last edited 5 years ago by pbruin (previous) (diff)

comment:21 Changed 5 years ago by ppurka

Indeed it looks like #13214 will supercede this.

comment:22 Changed 5 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:23 Changed 5 years ago by jpflori

  • Status changed from needs_info to positive_review

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.

comment:24 Changed 5 years ago by jpflori

  • Milestone changed from sage-6.1 to sage-duplicate/invalid/wontfix

comment:25 Changed 5 years ago by vbraun

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