Speed up PARI finite field operations

[sagetrac-johanbosman]

Let us perform a simple addition of finite field elements that are represented using PARI.

sage: F.<a> = GF(3^11)
sage: x = F.random_element()
sage: y = F.random_element()
sage: %timeit x + y
625 loops, best of 3: 13.2 µs per loop

Let us now measure how much time the actual addition takes:

sage: vx = x._FiniteField_ext_pariElement__value
sage: vy = y._FiniteField_ext_pariElement__value
sage: %timeit vx + vy
625 loops, best of 3: 4.6 µs per loop

This means two thirds of the execution time is used to wrap a ribbon around the result and only one third for the actual addition!

But in fact Pari has a faster implementation for finite fields than this! This was already mentioned at http://groups.google.com/group/sage-nt/browse_thread/thread/e2dbbc72caeb589a

sage: def pari_ffelt(x): parix=pari(x); return parix.lift().subst(parix.variable(), "ffgen((%s).mod)"%parix) 

sage: px = pari_ffelt(x)
sage: py = pari_ffelt(y)
sage: %timeit px + py
625 loops, best of 3: 2.43 µs per loop

For multiplication, we have the following timings:

sage: %timeit x * y
625 loops, best of 3: 18.2 µs per loop
sage: %timeit vx * vy
625 loops, best of 3: 8.4 µs per loop
sage: %timeit px * py
625 loops, best of 3: 3.33 µs per loop

This ticket implements an interface to PARI's FFELT type for non-prime finite fields. It can be tested by constructing finite fields as follows, for p prime and n >= 2:

sage: F.<a> = FiniteField(p^n, impl='pari_ffelt')

This implementation should probably become the default for non-prime finite fields of characteristic > 2 and cardinality > 2¹⁶, superseding the existing PARI polmod implementation. This switch is the goal of ticket #14888.

Apply:

• attachment: trac_12142-FiniteField_pari_ffelt.improved.patch
• attachment: trac_12142-singular_conversion.patch
• attachment: trac_12142-reviewer.patch
• attachment: trac_12142-doctest.patch
• attachment: trac_12142-remove_cinit.patch

Depends on #14817
Depends on #14818
Depends on #14832
Depends on #14833

CC: @koffie @jpflori

Component: basic arithmetic

Author: Peter Bruin

Reviewer: Jean-Pierre Flori

Merged: sage-5.12.beta3

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

[jpflori]

comment:3

Just a reminder for myself, it would also be nice to have a common cython interface to deal with finite fields elements, surely using templates as for polynomials.

[pjbruin]

Author: Peter Bruin

[pjbruin]

comment:4

I have been working on an interface to PARI's implementation of finite fields (t_FFELT). Like for the other interfaces (except the existing PARI polmod implementation), the field class is written in Python and the element class in Cython. I hope to upload a patch soon after cleaning up the documentation and fixing a minor problem.

The speed improvement for addition and multiplication relative to the current implementation appears to vary roughly from a factor 3 to a factor 12, depending on the size of the field.

For small fields, this PARI interface is (of course) much slower than Givaro (a factor 4-6 for F_{3¹⁰}). For fields of characteristic 2, it is slower than NTL+gf2x, but the difference is not that dramatic.

[pjbruin]

Dependencies: #14817, #14818, #14832, #14833

[pjbruin]

comment:5

This ticket led to several other patches, which I put into separate tickets; see the list of dependencies. The dependence on #14817 is optional.

A patch for this ticket is now practically ready.

[pjbruin]

Work Issues: conversion from/to Singular

[pjbruin]

comment:6

The attached patch implements a new class FiniteField_pari_ffelt and associated element class FiniteFieldElement_pari_ffelt. There is currently one doctest failure, related to conversion from and to Singular.

[pjbruin]

comment:7

Attachment: trac_12142-singular_conversion.patch.gz

OK, converting between FiniteFieldElement and Singular was an easy generalisation of existing code. I will try to make a small table comparing the performance of the various implementations. In the meantime this is ready to be reviewed.

[pjbruin]

Changed work issues from conversion from/to Singular to none

[pjbruin]

Description changed:

--- 
+++ 
@@ -38,3 +38,12 @@
 625 loops, best of 3: 3.33 µs per loop
 ```
 
+This ticket implements an interface to PARI's FFELT type for non-prime finite fields.  It is not the default yet, but it can be tested by constructing finite fields as follows, for *p* prime and *n* >= 2:
+
+```
+sage: F.<a> = FiniteField(p^n, impl='pari_ffelt')
+```
+This implementation should probably become the default for finite fields of characteristic > 2 and cardinality > 2<sup>16</sup>, superseding the existing PARI polmod implementation.
+
+Apply: [attachment: trac_12142-FiniteField_pari_ffelt.patch](https://github.com/sagemath/sage-prod/files/10654200/trac_12142-FiniteField_pari_ffelt.patch.gz), [attachment: trac_12142-singular_conversion.patch](https://github.com/sagemath/sage-prod/files/10654199/trac_12142-singular_conversion.patch.gz)
+