Arithmétique modulaire

Implémentation de l'arithmétique modulaire pour les entiers et les polynômes.

Librairie

Le répertoire lib contient le code de la librairie statique libmod. Pour compiler la librairie depuis la racine :

make lib/libmod.a

Arithmétiques

Quatre arithmétiques différentes sont implémentées :

• integer : arithmétique d'entiers
• modint : arithmétique d’entiers modulo un entier m
• modpoly : arithmétique de polynômes à coefficients dans Z/mZ
• modpolyp : arithmétique de polynômes modulo un polynôme P

La librairie contient aussi :

• extendedGcdInt : algorithme d’Euclide étendu pour les entiers
• extendedGcdPoly : algorithme d'Euclide étendu pour les polynômes à coefficients dans Z/mZ

La librairie définit les quatre types suivants :

• integer : entier de 32 bits
• modulus : entier modulo de 32 bits
• polynomial : polynôme d'entiers
• degree : degré d'un polynôme

Séries formelles

Les fichiers fps définissent des fonctions pour manipuler les séries formelles. Le type fps permet de définir une série formelle tronquée, et prec renseigne sa précision.

Arbres de polynômes

Les fichiers polytree définissent les arbres de polynômes permettant l'implémentation des algorithmes rapides suivants pour les polynômes à coefficients dans Z/mZ :

• mp_fast_multipoint_eval : évaluation multipoint rapide
• mp_fast_interpolation : interpolation rapide

Les arbres peuvent être exportés au format dot et visualisés avec Graphviz. Exemples :

Matrices d'entiers

Les fichiers matrix définissent les matrices d'entiers. Le type matrix permet de définir une matrice et dim représente une dimension. Les matrices d'entiers sont utilisées dans les fonctions suivantes :

• p_sylvester : retourne la matrice de Sylvester de deux polynômes
• p_resultant : calcule le résultant de deux polynômes (déterminant de la matrice de Sylvester)

Exemples

Le répertoire examples contient des exemples d'utilisation de la librairie libmod.

• Pour compiler un exemple :

cd examples
make example01.out

• Pour compiler tous les exemples :

cd examples
make

Le README du répertoire examples montre le rôle de chaque exemple.

Exécutables

Le répertoire src contient les fonctions principales pour générer des exécutables utilisant la librairie libmod.

Compilation

Les exécutables sont créés dans le répertoire build.

• Pour compiler tous les exécutables :

make

• Pour compiler l'exécutable extendedGcdInt.out :

cd src
make build/extendedGcdInt.out

Protocole similaire pour tous les exécutables ci-dessous.

Description

Voici la liste des exécutables :

• extendedGcdInt.out : algorithme d'Euclide étendu pour les entiers. Exemple (source) :

== Extended Euclidean algorithm for integers ==
a = 240
b = 46
== Iteration 0 ==
(r, u, v) = (240, 1, 0)
== Iteration 1 ==
(r, u, v) = (46, 0, 1)
== Iteration 2 ==
(r, u, v) = (10, 1, -5)
== Iteration 3 ==
(r, u, v) = (6, -4, 21)
== Iteration 4 ==
(r, u, v) = (4, 5, -26)
== Result ==
(r, u, v) = (2, -9, 47)

• extendedGcdPoly.out : algorithme d'Euclide étendu pour les polynômes à coefficients dans Z/mZ. Exemple (source) :

== Extended Euclidean algorithm for polynomials ==
Degree of A: 8
A[0] = 1
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1
A[5] = 0
A[6] = 0
A[7] = 0
A[8] = 1
Degree of B: 6
B[0] = 1
B[1] = 1
B[2] = 0
B[3] = 0
B[4] = 1
B[5] = 0
B[6] = 1
Modulus: 2
A = X^8 + X^4 + X^3 + X + 1
B = X^6 + X^4 + X + 1
== Iteration 0 ==
R = X^8 + X^4 + X^3 + X + 1
U = 1
V = 0
== Iteration 1 ==
R = X^6 + X^4 + X + 1
U = 0
V = 1
== Iteration 2 ==
R = X^2
U = 1
V = X^2 + 1
== Iteration 3 ==
R = X + 1
U = X^4 + X^2
V = X^6 + X^2 + 1
== Result ==
R = 1
U = X^5 + X^4 + X^3 + X^2 + 1
V = X^7 + X^6 + X^3 + X

• evalPoly.out : évaluation d'un polynôme en un point dans Z/mZ. Exemple :

== Polynomial evaluation ==
Degree of P: 3
P[0] = 4
P[1] = 1
P[2] = 2
P[3] = 1
Modulus: 7
P = X^3 + 2 X^2 + X + 4
X = 2
P(2) = 1

• multipointEvalPoly.out : évaluation multipoint d'un polynôme dans Z/mZ. Exemple :

== Polynomial multipoint evaluation ==
Degree of P: 3
P[0] = 4
P[1] = 1
P[2] = 2
P[3] = 1
Modulus: 7
P = X^3 + 2 X^2 + X + 4
n = 4
x0 = 2
x1 = 5
x2 = 3
x3 = 4
== Result ==
P(2) = 1
P(5) = 2
P(3) = 3
P(4) = 6

• euclideanDivisionPoly.out : division euclidienne de polynômes à coefficients dans Z/mZ. Exemple :

== Euclidean division of polynomials ==
Degree of P: 4
P[0] = 9
P[1] = 1
P[2] = 4
P[3] = 7
P[4] = 1
Degree of D: 3
D[0] = 2
D[1] = 1
D[2] = 1
D[3] = 10
Modulus: 11
P = X^4 + 7 X^3 + 4 X^2 + X + 9
D = 10 X^3 + X^2 + X + 2
== Results ==
Q = 10 X + 3
R = 2 X^2 + 3

• interpolationPoly.out : interpolation de Lagrange dans Z/mZ. Exemple :

== Polynomial interpolation ==
Modulus: 7
n = 4
x0 = 2
y0 = 1
x1 = 5
y1 = 2
x2 = 3
y2 = 3
x3 = 4
y3 = 6
Lagrange polynomial:
L = X^3 + 2 X^2 + X + 4
Verification:
L(2) = 1
L(5) = 2
L(3) = 3
L(4) = 6

Algorithmes

Voici la liste des algorithmes implémentés (ou à faire) :

• Algorithme d'Euclide étendu (pour les entiers et les polynômes)
• Méthode de Ruffini-Horner
• Évaluation multipoint rapide
• Interpolation lagrangienne
• Interpolation rapide
• Algorithme de Wiedemann
• Algorithme de remontée de Hensel
• Algorithme de Berlekamp

Documentation

La documentation peut être générée par doxygen avec la commande :

make docs

Il suffit ensuite d'aller à l'adresse docs/html/index.html.

Pour supprimer la documentation :

make cleandocs

Tests

Le répertoire tests contient des tests unitaires de la librairie libmod. Ces tests sont réalisés par le framework MinUnit.

Auteur

Quentin Deschamps