ZEN

Overview

Many computational problems need arithmetic operations in polynomial finite rings over Z/nZ, where n is an integer (n>1). Integer factorization and primality testing are examples of such applications. To solve them, programmers either use general symbolic mathematical software packages or write specific programs (most of the time in C).

Symbolic mathematical software packages (e.g. Maple, Mathematica,...) usually handle with difficulty computations in finite fields. In the worst cases, such programs perform computations with rationals before finally reducing the objects modulo the characteristic n, or such reductions are performed but extensions of a finite ring can't be implemented. In any case, applications written with such packages are ten to hundred times slower than an ad hoc implementation in C. On the other hand, optimized C libraries (PARI, Lidia, ...) deal only with limited classes of finite fields, mainly Z/nZ or GF(2ⁿ).

We believe it is possible to keep the efficiency of these C libraries while working in any polynomial extension of Z/nZ. We designed the ZEN library to perform efficient arithmetic operations in these sets. That means one can work not only in any polynomial extension of Z/nZ, but also in any polynomial extension of another finite ring even if n is not a prime or even if the polynomial which defines the extension is not irreducible.

In addition, these functionalities are provided without loss of simplicity. Of course, a compromise had to be made between simplicity and efficiency. Therefore, this library can be used at two levels.

• For a standard usage, the functions ZENFcts of the library can be used to perform operations on elements, polynomials, matrices, series and elliptic curves over every polynomial extension over Z/nZ. Here, you only have to include zen.h in your C sources and link your object files with the library libzen.a.
• For advanced users who need to gain more efficiency, it is possible to replace procedure calls by macros in their own functions. Such users have to know the internal data structures of the library and to write specific functions for each structure if they still want to handle any finite ring. These users are then sure that their applications are not penalized by inoportune procedure calls.

Features

The main features of the library are as follows:

• Basic operations on elements over any finite ring, including Karatsuba multiplication for large integers;
• Operations on polynomials over any finite ring, including Karatsuba multiplication for all polynomials;
• Operations on matrices over any finite ring, including inversion, and kernel computation;
• Operations on truncated series over any finite ring;
• Operations on elliptic curves over any finite ring, mainly the group law.
• Montgomery's representation for modular finite fields;
• Chinese remainder representations;