Opened 5 years ago
Closed 5 years ago
#23153 closed defect (fixed)
Bug in finite field element GAPtoSage conversion when explicit field is specified
Reported by:  dimpase  Owned by:  ibookstein 

Priority:  critical  Milestone:  sage8.1 
Component:  group theory  Keywords:  
Cc:  vbraun  Merged in:  
Authors:  Itay Bookstein  Reviewers:  Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  117599e (Commits, GitHub, GitLab)  Commit:  117599e0987414baec6169a1b7dd337b7e681b23 
Dependencies:  Stopgaps: 
Description (last modified by )
As reported on sagedevel
S = GF(2^4, 'a') a = S.gen() G = SL(2, S) g1 = G([a**2, a**3 + a**2 + a, a + 1, 0]) g2 = G([a, 0, 0, a**3 + 1]) # prints True True print g1 in G, g2 in G # Throws a ValueError print g1 * g2
Specifically, one gets
ValueError: the given finite field has incompatible size
The actual underlying bug is the fact that the GapElement_FiniteField.sage
method malfunctions when an explicit ring
argument is specified and the element lies in a subfield of the field passed in that argument (note that GAP performs such reductions automatically).
One would reasonably expect this to work, but a ValueError
is thrown on the last line:
sage: n = libgap.eval('Z(2^4)^2 + Z(2^4)^1 + Z(2^4)^0') sage: n Z(2^2)^2 sage: n.sage(ring=GF(2^4)) ValueError: the given finite field has incompatible size
Change History (26)
comment:1 Changed 5 years ago by
comment:2 Changed 5 years ago by
 Cc vbraun added
Indeed, different entries of a matrix might belong to different subfields of the field of definition; this test is simply wrong here (there is an element from the order 4 subfield in one of these matrices).
comment:3 Changed 5 years ago by
Amending this to reflect the real underlying bug: When an explicit ring (field) argument is specified to the GapElement_FiniteField.sage method, and the finite field element lies in a subfield of that field, the conversion as it currently works fails because GAP reduces the representation to that of the subfield.
comment:4 Changed 5 years ago by
 Description modified (diff)
 Owner changed from (none) to ibookstein
comment:5 Changed 5 years ago by
 Description modified (diff)
 Summary changed from bug in SL(2,GF(q)) multiplication to Bug in finite field element GAPtoSage conversion when explicit field is specified
comment:6 Changed 5 years ago by
 Branch set to u/ibookstein/gap_to_sage_ffe_conversion_bugfix
comment:7 Changed 5 years ago by
 Commit set to c522ced2719d9e701a85825f0662e73a1185145a
Branch pushed to git repo; I updated commit sha1. New commits:
comment:8 Changed 5 years ago by
 Commit changed from c522ced2719d9e701a85825f0662e73a1185145a to e1f598c44b47c6408d632570910e952a009f0543
Branch pushed to git repo; I updated commit sha1. New commits:
e1f598c  Implemented a fix to the bug, added some doctests

comment:9 Changed 5 years ago by
This fix looks as if it might lead to a huge slowdown. Would it be possible to avoid this test and creation of a field completely?
comment:10 Changed 5 years ago by
I also do not understand how libGAP handles finite fields obtained by specifying an explicit irreducible polynomial, e.g.
gap> poly:=RandomPrimitivePolynomial(GF(2),20); x_1^20+x_1^17+x_1^16+x_1^12+x_1^9+x_1^6+Z(2)^0 gap> f220:=GF(GF(2),poly); <algebrawithone of dimension 20 over GF(2)>
comment:11 Changed 5 years ago by
 Commit changed from e1f598c44b47c6408d632570910e952a009f0543 to 4ee98ae1a8b30a63a1918d22956d25a2fb88cf65
Branch pushed to git repo; I updated commit sha1. New commits:
4ee98ae  Added validations for explicit ring argument, added tests

comment:12 Changed 5 years ago by
 Description modified (diff)
 Status changed from new to needs_review
comment:13 Changed 5 years ago by
 Description modified (diff)
comment:14 Changed 5 years ago by
Sorry, missed your comments before I wrapped it all up and submitted it for review, assumed such comments would be part of the review.
 Should I revert the ticket's status?
 Regarding the slowdown resulting from the test and creation of a field:
 What test are you referring to? The modulus?
 I'm not sure what to replace the field creation with and what's considered cheap/expensive in Sage/GAP. What would you recommend? We could cut straight to the
PrimitiveRoot
for example by using GAP'sZ(...)
and plugging in the desired field's size, but I know nothing about GAP's implementation details and whether it creates the parent field anyway.
 Regarding the finite fields with nondefault (nonConway) modulus polynomial:
 I actually looked into this as a separate issue/bug as part of researching a fix for this ticket, but I haven't submitted anything yet.
 The
_gap_init_()
string for Sage fields completely ignores the modulus polynomial  the conversion is lossy, and you getF.<x> = GF(2)['x']; libgap(GF(2^18, 'x')) == libgap(GF(2^18, 'x', modulus=x**18 + x**16 + x**11 + x**4 + 1))
printingTrue
comment:15 Changed 5 years ago by
 Reviewers set to Dima Pasechnik
A comment about your code; you create a lot of temporary variables without a reason; one does not need compatible
, gap_field_obj
, and gap_field
, right?
Could you get rid of them?
Otherwise, your patch looks good; I now realise that because we deal with only "standard" finite fields here, for them PrimitiveRoot
is instant.
(this would not be true for extensions specified by arbitrary primitive polynomials).
Regarding the latter (finite fields with nondefault (nonConway) modulus polynomial); so you think they are not handled in libGAP? If so, could you please open a ticket to deal with this?
comment:16 Changed 5 years ago by
No problem getting rid of them, just thought they make the code more readable (are these temporaries a performance concern?).
I mean, in principal one could inline the entire second else
clause to a huge oneliner, but that would be rather unreadable :)
I was under the impression that the field creation within GAP might be performance issue, not the PrimitiveRoot
lookup (which, by the way, was there before the patch).
We could also cut straight to root = make_GapElement_FiniteField(self.parent(), gap_eval(ring.multiplicative_generator()._gap_init_()))
, but it may be worse.
Regarding the finite fields with nondefault (nonConway) modulus polynomials, see src/sage/rings/finite_rings/finite_field_base.pyx
, method FiniteField._gap_init_
.
Adding such support would be lengthier, as we may need to audit all SagefinitefieldtoGAPfinitefield bridges and make sure they make no assumptions about the modulus being nondefault, e.g. src/sage/rings/finite_rings/element_ntl_gf2e.pyx
method FiniteField_ntl_gf2eElement._gap_init_
(where it is explicitly blocked).
comment:17 Changed 5 years ago by
 Commit changed from 4ee98ae1a8b30a63a1918d22956d25a2fb88cf65 to 117599e0987414baec6169a1b7dd337b7e681b23
Branch pushed to git repo; I updated commit sha1. New commits:
117599e  Inlined some temporaries

comment:18 Changed 5 years ago by
 Status changed from needs_review to positive_review
OK, this looks good enough.
Regarding the nonConway irreducible polynomials for GFs, I have opened #23452.
comment:19 Changed 5 years ago by
Should we also open tickets about the following two enhancements?
 Adding support for GAP fields whose size is larger than
2^16
in both conversion directions? I actually tried hacking in a GAPtoSage conversion for this case (undermake_any_gap_element
'slibGAP_T_POSOBJ
case ifresult.IsFFE()
is true) and found out that the current GAPtosage conversion after my editing is extremely slow because of theLogFFE
call (it's slow when GAP doesn't use the efficient internal representation, which happens precisely when the size is over2^16
).  Adding support for algebraic extensions of nonprime fields via GAP's functionality? Maybe that's a bit much, I don't know.
comment:20 Changed 5 years ago by
IMHO Sage's support for GF(q) with large q is much better than in GAP  in particular for q=2^{k}, where gf2x
is used.
Anyhow, why does one even need to call LogFFE()
? Both GAP and Sage represent finite field elements as polynomials in the primitive element, can't one just rewrite these polynomials?
comment:21 Changed 5 years ago by
Regarding the GF(p^n)
support  yes, but when I want to use a matrix group over a large field (SL(2, 2^32)
, for instance, I'm completely unable to do that within Sage because Sage uses GAP for matrix group implementations and the SageGAP bridge doesn't support large fields.
Perhaps this warrants abandoning GAP's matrix group implementations and having Sage implementations, I don't know.
Regarding the LogFFE()
call  I was wondering about that myself. Doing the conversion based on the polynomial representation should be pretty simple to implement. I guess the exponentiation implementation was easier and shorter to implement (see src/sage/rings/finite_rings/element_givaro.pyx
, method FiniteField_givaroElement._gap_init_
for example, where to do the conversion you just format the field's size and the exponent into a string).
comment:22 Changed 5 years ago by
Unless I miss something, for sufficiently big q GF(q) in Sage is implemented using NTL.
comment:23 Changed 5 years ago by
They are, but once you try doing things in e.g. SL(2, F)
the field elements are coerced back and forth (GAPtoNTL and vice versa):
sage: G = SL(2, 2**24) sage: G.generators() ... TypeError: sage() takes no keyword arguments
This is because the objects being coerced are deduced as generic GapElement
s instead of FFEs.
Perhaps I should move this discussion to sagedevel.
comment:24 followup: ↓ 25 Changed 5 years ago by
I'm not very well acquainted with the development cycle (and didn't see anything about it on the developer guide), am I supposed to merge it to develop or is that on one of the admins?
comment:25 in reply to: ↑ 24 Changed 5 years ago by
 Milestone changed from sage8.0 to sage8.1
Replying to ibookstein:
I'm not very well acquainted with the development cycle (and didn't see anything about it on the developer guide), am I supposed to merge it to develop or is that on one of the admins?
the rest is normally done by the release manager, no need to do anything at this point on your side.
comment:26 Changed 5 years ago by
 Branch changed from u/ibookstein/gap_to_sage_ffe_conversion_bugfix to 117599e0987414baec6169a1b7dd337b7e681b23
 Resolution set to fixed
 Status changed from positive_review to closed
namely
and in this case one has
field.Size().sage() = 4
andring.cardinality() = 16