Opened 9 years ago
Closed 7 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 )
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)
Change History (28)
Changed 9 years ago by
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
- 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 9 years ago by
- Cc rbeezer added
Changed 9 years ago by
comment:5 Changed 9 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
- Work issues needs rebase deleted
comment:6 Changed 9 years ago by
- Dependencies set to #12084
trac_11938_conversion_gf_conway.2.patch is on sage-5.0.beta13
comment:7 Changed 9 years ago by
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 8 years ago by
- Cc dimpase added
comment:9 Changed 8 years ago by
- Description modified (diff)
comment:10 Changed 8 years ago by
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: ↓ 12 Changed 8 years ago by
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 8 years ago by
- 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 8 years ago by
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 8 years ago by
- Cc jpflori added
comment:15 Changed 8 years ago by
- Dependencies changed from #12084 to #12084, #8335
- Description modified (diff)
- Reviewers set to Jean-Pierre Flori
- Status changed from needs_info to needs_review
comment:16 Changed 8 years ago by
- Cc pbruin added
comment:17 Changed 8 years ago by
- Cc defeo added
comment:18 Changed 8 years ago by
- Keywords sd51 added
comment:19 Changed 8 years ago by
- 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 F_{p}-linear map and to find the unique solution of the corresponding linear system.
comment:20 Changed 8 years ago by
- 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?
comment:21 Changed 8 years ago by
Indeed it looks like #13214 will supercede this.
comment:22 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:23 Changed 7 years ago by
- 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 7 years ago by
- Milestone changed from sage-6.1 to sage-duplicate/invalid/wontfix
comment:25 Changed 7 years ago by
- Resolution set to wontfix
- Status changed from positive_review to closed
Here comes the patch ;) Conversion is possible in both directions (up and down), see example below.