Table des Matières
Publicité
Un polynôme P(X) appartient à un anneau arithmétique fini de modules
polynomiaux M(X), s'il existe un troisième polynôme Q(X), tel que (P(X) – Q(X))
est un multiple de M(X). Nous pourrions alors écrire : P(X)
Cette dernière expression est interprétée comme "P(X) est congru à Q(X),
modulo M(X)".
Fonction CHINREM
CHINREM signifie CHINese REMainder (théorème Chinois). L'opération
encodée dans cette commande résout un système de deux congruences utilisant
le Théorème Chinois. Cette commande peut être utilisée avec des polynômes,
de même qu'avec des nombres entiers (fonction ICHINREM). Les données
d'entrée' consistent en deux vecteurs [expression_1, modulo_1] et
[expression_2, modulo_2]. Les données de sortie sont un vecteur contenant
[expression_3, modulo_3], où modulo_3 est lié au produit
⋅
(modulo_1)
(modulo_2). Exemple: CHINREM([X+1, X^2-1],[X+1,X^2]) =
[X+1,-(X^4-X^2)]
Déclaration du Théorème Chinois pour les entiers
Si m
, m
,...,m
1
2
r
premier relatif et : a
entier x qui satisfait simultanément les congruences : x
(mod m
), ..., x
2
alors toutes les autres solutions sont congruentes à un modulo égal au produit
⋅
⋅
m
m
... m
.
1
2
r
Fonction EGCD
EGCD signifie Extended Greatest Common Divisor (Plus grand diviseur commun
étendu). Etant donné deux polynômes, A(X) et B(X), la fonction EGCD produit
les polynômes C(X), U(X), et V(X), de telle sorte que C(X) = U(X)*A(X) +
V(X)*B(X). Par exemple, pour A(X) = X^2+1, B(X) = X^2-1, EGCD(A(X),B(X)) =
{2, 1, -1}. c'est-à-dire 2 = 1*( X^2+1')-1*( X^2-1). De même, EGCD('X^3-
2*X+5','X') = { 5,1,-(X^2-2)}, c'est-à-dire 5 = – (X^2-2)*X + 1*(X^3-2*X+5).
sont des nombres naturels dont chaque paire est un nombre
, a
, ..., a
sont des entiers quelconques, alors il existe un
1
2
r
≡
a
(mod m
). De plus, si x = a est une solution quelconque,
r
r
≡
Q(X) (mod M(X)).
≡
a
(mod m
), x
1
1
Page. 5-20
≡
a
2
Publicité
Table des Matières
