Bug in finite field element GAP-to-Sage conversion when explicit field is specified

dimpase commented 7 years ago

As reported on sage-devel

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

CC: @vbraun

Component: group theory

Author: Itay Bookstein

Branch/Commit: 117599e

Reviewer: Dima Pasechnik

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

dimpase commented 7 years ago

comment:1

namely

---> 13 print g1*g2

/home/dima/Sage/sage-dev/src/sage/structure/sage_object.pyx in sage.structure.sage_object.SageObject.__repr__ (build/cythonized/sage/structure/sage_object.c:2712)()
    190             return str(type(self))
    191         else:
--> 192             result = repr_func()
    193             if isinstance(result, unicode):
    194                 # Py3 compatibility: allow _repr_ to return unicode

/home/dima/Sage/sage-dev/src/sage/groups/matrix_gps/group_element.pyx in sage.groups.matrix_gps.group_element.MatrixGroupElement_gap._repr_ (build/cythonized/sage/groups/matrix_gps/group_element.c:6700)()
    490             '[1 1]\n[0 1]'
    491         """
--> 492         return str(self.matrix())
    493 
    494     def _latex_(self):

/home/dima/Sage/sage-dev/src/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (build/cythonized/sage/misc/cachefunc.c:13462)()
   2399         if self.cache is None:
   2400             f = self.f
-> 2401             self.cache = f(self._instance)
   2402         return self.cache
   2403 

/home/dima/Sage/sage-dev/src/sage/groups/matrix_gps/group_element.pyx in sage.groups.matrix_gps.group_element.MatrixGroupElement_gap.matrix (build/cythonized/sage/groups/matrix_gps/group_element.c:7760)()
    585         MS = self.parent().matrix_space()
    586         ring = MS.base_ring()
--> 587         m = MS([x.sage(ring=ring) for x in entries])
    588         m.set_immutable()
    589         return m

/home/dima/Sage/sage-dev/src/sage/libs/gap/element.pyx in sage.libs.gap.element.GapElement_FiniteField.sage (build/cythonized/sage/libs/gap/element.c:12711)()
   1386             field = self.DefaultField()
   1387             if field.Size().sage() != ring.cardinality():
-> 1388                 raise ValueError('the given finite field has incompatible size')
   1389             root = self.DefaultField().PrimitiveRoot()
   1390             exp = self.LogFFE(root)

ValueError: the given finite field has incompatible size

and in this case one has field.Size().sage() = 4 and ring.cardinality() = 16

dimpase commented 7 years ago

comment:2

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

bb437f30-3d11-4b39-a94f-c45c8b252c40 commented 7 years ago

comment:3

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.

bb437f30-3d11-4b39-a94f-c45c8b252c40 commented 7 years ago

Description changed:

--- 
+++ 
@@ -20,3 +20,14 @@

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
+```

bb437f30-3d11-4b39-a94f-c45c8b252c40 commented 7 years ago

Description changed:

--- 
+++ 
@@ -22,7 +22,7 @@

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

bb437f30-3d11-4b39-a94f-c45c8b252c40 commented 7 years ago

Branch: u/ibookstein/gap_to_sage_ffe_conversion_bugfix

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Commit: c522ced

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from c522ced to e1f598c

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

e1f598c Implemented a fix to the bug, added some doctests

dimpase commented 7 years ago

comment:9

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?

dimpase commented 7 years ago

comment:10

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);
<algebra-with-one of dimension 20 over GF(2)>

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

4ee98ae Added validations for explicit ring argument, added tests

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from e1f598c to 4ee98ae

bb437f30-3d11-4b39-a94f-c45c8b252c40 commented 7 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,5 @@
+Authors: Itay Bookstein
+
 As [reported](https://groups.google.com/d/msg/sage-devel/1VHx3laSU_U/wFxF2JsABwAJ) on sage-devel

bb437f30-3d11-4b39-a94f-c45c8b252c40 commented 7 years ago

Description changed:

--- 
+++ 
@@ -1,5 +1,3 @@
-Authors: Itay Bookstein
-
 As [reported](https://groups.google.com/d/msg/sage-devel/1VHx3laSU_U/wFxF2JsABwAJ) on sage-devel

bb437f30-3d11-4b39-a94f-c45c8b252c40 commented 7 years ago

Author: Itay Bookstein

bb437f30-3d11-4b39-a94f-c45c8b252c40 commented 7 years ago

comment:14

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's Z(...) 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 non-default (non-Conway) 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 get F.<x> = GF(2)['x']; libgap(GF(2^18, 'x')) == libgap(GF(2^18, 'x', modulus=x**18 + x**16 + x**11 + x**4 + 1)) printing True

dimpase commented 7 years ago

comment:15

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 non-default (non-Conway) modulus polynomial); so you think they are not handled in libGAP? If so, could you please open a ticket to deal with this?

dimpase commented 7 years ago

Reviewer: Dima Pasechnik

bb437f30-3d11-4b39-a94f-c45c8b252c40 commented 7 years ago

comment:16

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 one-liner, 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 non-default (non-Conway) 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 Sage-finite-field-to-GAP-finite-field bridges and make sure they make no assumptions about the modulus being non-default, e.g. src/sage/rings/finite_rings/element_ntl_gf2e.pyx method FiniteField_ntl_gf2eElement._gap_init_ (where it is explicitly blocked).

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from 4ee98ae to 117599e

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

117599e Inlined some temporaries

dimpase commented 7 years ago

comment:18

OK, this looks good enough.

Regarding the non-Conway irreducible polynomials for GFs, I have opened #23452.

bb437f30-3d11-4b39-a94f-c45c8b252c40 commented 7 years ago

comment:19

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 GAP-to-Sage conversion for this case (under make_any_gap_element's libGAP_T_POSOBJ case if result.IsFFE() is true) and found out that the current GAP-to-sage conversion after my editing is extremely slow because of the LogFFE call (it's slow when GAP doesn't use the efficient internal representation, which happens precisely when the size is over 2^16).
Adding support for algebraic extensions of non-prime fields via GAP's functionality? Maybe that's a bit much, I don't know.

dimpase commented 7 years ago

comment:20

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?

bb437f30-3d11-4b39-a94f-c45c8b252c40 commented 7 years ago

comment:21

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

dimpase commented 7 years ago

comment:22

Unless I miss something, for sufficiently big q GF(q) in Sage is implemented using NTL.

bb437f30-3d11-4b39-a94f-c45c8b252c40 commented 7 years ago

comment:23

They are, but once you try doing things in e.g. SL(2, F) the field elements are coerced back and forth (GAP-to-NTL 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 GapElements instead of FFEs. Perhaps I should move this discussion to sage-devel.

bb437f30-3d11-4b39-a94f-c45c8b252c40 commented 7 years ago

comment:24

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?

dimpase commented 7 years ago

comment:25

Replying to @sagetrac-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.

vbraun commented 7 years ago

Changed branch from u/ibookstein/gap_to_sage_ffe_conversion_bugfix to 117599e

sagemath / sage

Bug in finite field element GAP-to-Sage conversion when explicit field is specified #23153