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

[dimpase]

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]

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]

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

[sagetrac-ibookstein]

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.

[sagetrac-ibookstein]

Branch: u/ibookstein/gap_to_sage_ffe_conversion_bugfix

[sagetrac-git]

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

[sagetrac-git]

Commit: c522ced

[sagetrac-git]

Changed commit from c522ced to e1f598c

[sagetrac-git]

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

e1f598c

Implemented a fix to the bug, added some doctests

[dimpase]

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]

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

[sagetrac-git]

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

4ee98ae

Added validations for explicit ring argument, added tests

[sagetrac-git]

Changed commit from e1f598c to 4ee98ae

[sagetrac-ibookstein]

Author: Itay Bookstein

[sagetrac-ibookstein]

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]

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]

Reviewer: Dima Pasechnik

[sagetrac-ibookstein]

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

[sagetrac-git]

Changed commit from 4ee98ae to 117599e

[sagetrac-git]

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

117599e

Inlined some temporaries

[dimpase]

comment:18

OK, this looks good enough.

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

[sagetrac-ibookstein]

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]

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?

[sagetrac-ibookstein]

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]

comment:22

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

[sagetrac-ibookstein]

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.

[sagetrac-ibookstein]

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]

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]

Changed branch from u/ibookstein/gap_to_sage_ffe_conversion_bugfix to 117599e