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
...) deal only with limited classes of finite fields, mainly
Z/nZ or GF(2n).
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
- 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
The main features of the library are as follows:
We have also developed high level procedures on top of ZEN : the
- 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;