Opened 5 years ago

Closed 5 years ago

#23153 closed defect (fixed)

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

Reported by: dimpase Owned by: ibookstein
Priority: critical Milestone: sage-8.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:

Status badges

Description (last modified by ibookstein)

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

Change History (26)

comment:1 Changed 5 years ago by dimpase

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

comment:2 Changed 5 years ago by dimpase

  • 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 ibookstein

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 ibookstein

  • Description modified (diff)
  • Owner changed from (none) to ibookstein

comment:5 Changed 5 years ago by ibookstein

  • Description modified (diff)
  • Summary changed from bug in SL(2,GF(q)) multiplication to Bug in finite field element GAP-to-Sage conversion when explicit field is specified

comment:6 Changed 5 years ago by ibookstein

  • Branch set to u/ibookstein/gap_to_sage_ffe_conversion_bugfix

comment:7 Changed 5 years ago by git

  • Commit set to c522ced2719d9e701a85825f0662e73a1185145a

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

comment:8 Changed 5 years ago by git

  • Commit changed from c522ced2719d9e701a85825f0662e73a1185145a to e1f598c44b47c6408d632570910e952a009f0543

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

e1f598cImplemented a fix to the bug, added some doctests

comment:9 Changed 5 years ago by dimpase

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 dimpase

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

comment:11 Changed 5 years ago by git

  • Commit changed from e1f598c44b47c6408d632570910e952a009f0543 to 4ee98ae1a8b30a63a1918d22956d25a2fb88cf65

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

4ee98aeAdded validations for explicit ring argument, added tests

comment:12 Changed 5 years ago by ibookstein

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

comment:13 Changed 5 years ago by ibookstein

  • Authors set to Itay Bookstein
  • Description modified (diff)

comment:14 Changed 5 years ago by ibookstein

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
Last edited 5 years ago by ibookstein (previous) (diff)

comment:15 Changed 5 years ago by dimpase

  • 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 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?

comment:16 Changed 5 years ago by ibookstein

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

comment:17 Changed 5 years ago by git

  • Commit changed from 4ee98ae1a8b30a63a1918d22956d25a2fb88cf65 to 117599e0987414baec6169a1b7dd337b7e681b23

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

117599eInlined some temporaries

comment:18 Changed 5 years ago by dimpase

  • Status changed from needs_review to positive_review

OK, this looks good enough.

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

comment:19 Changed 5 years ago by ibookstein

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.
Last edited 5 years ago by ibookstein (previous) (diff)

comment:20 Changed 5 years ago by dimpase

IMHO Sage's support for GF(q) with large q is much better than in GAP - in particular for q=2k, 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 ibookstein

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

comment:22 Changed 5 years ago by dimpase

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

comment:23 Changed 5 years ago by ibookstein

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.

comment:24 follow-up: Changed 5 years ago by 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?

comment:25 in reply to: ↑ 24 Changed 5 years ago by dimpase

  • Milestone changed from sage-8.0 to sage-8.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 vbraun

  • Branch changed from u/ibookstein/gap_to_sage_ffe_conversion_bugfix to 117599e0987414baec6169a1b7dd337b7e681b23
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.