Système modulaire de représentation

En mathématiques, dans la branche de l'arithmétique modulaire, un système modulaire de représentation est un outil notamment utilisé en cryptographie, eu égard à sa capacité à réduire des calculs sur de grandes valeurs à des calculs menés en parallèle sur des nombres de taille choisie. Les systèmes modulaires de représentation des nombres (Residue Number System) sont une application du théorème des restes chinois. Les nombres sont représentés par leurs restes modulo un ensemble de valeurs premières entre elles. On peut définir une addition et une multiplication qui vont ainsi s'effectuer sur chaque module de façon indépendante.

Il est ainsi possible d'avoir des calculs parallèles sans propagation de retenues.

Définitions

Soit $(m_{1},m_{2},\ldots ,m_{n})$ un n-uplet de modules mutuellement premiers entre eux. On l'appelle la base RNS.

On note: $M=\prod _{i=1}^{n}m_{i}$.

Soit $X$ un entier positif inférieur à $M$ avec $x_{i}\equiv X{\pmod {m_{i}}}$. Le n-uplet $(x_{1},\ldots ,x_{n})$ est appelé représentation RNS de $X$.

D'après le théorème des restes chinois, la représentation RNS de chaque entier positif $X$ inférieur à $M$ est unique.

Exemple

On considère la base RNS $(2;3;5)$. Voici les représentations RNS des entiers de $0$ à $29$ :

$0=(0;0;0)$	$1=(1;1;1)$	$2=(0;2;2)$	$3=(1;0;3)$	$4=(0;1;4)$
$5=(1;2;0)$	$6=(0;0;1)$	$7=(1;1;2)$	$8=(0;2;3)$	$9=(1;0;4)$
$10=(0;1;0)$	$11=(1;2;1)$	$12=(0;0;2)$	$13=(1;1;3)$	$14=(0;2;4)$
$15=(1;0;0)$	$16=(0;1;1)$	$17=(1;2;2)$	$18=(0;0;3)$	$19=(1;1;4)$
$20=(0;2;0)$	$21=(1;0;1)$	$22=(0;1;2)$	$23=(1;2;3)$	$24=(0;0;4)$
$25=(1;1;0)$	$26=(0;2;1)$	$27=(1;0;2)$	$28=(0;1;3)$	$29=(1;2;4)$

Opérations

Addition et multiplication

Soit $A$ et $B$ deux entiers naturels positifs de représentations respectives $(a_{1},\ldots ,a_{n})$ et $(b_{1},\ldots ,b_{n})$. Sur l'ensemble des nombres en représentation RNS, on peut définir les opérations suivantes :

L'addition : $A+B$ est représenté par l'ensemble des $a_{i}+b_{i}$ pour chaque module $m_{i}$ ;

La multiplication : $A\times B$ est représentée par l'ensemble des $a_{i}\times b_{i}$ pour chaque module $m_{i}$.

Division

La définition d'une division est plus problématique. Si le diviseur est premier avec chaque module, il est possible d'effectuer simplement une division modulo $M=\prod _{i=1}^{n}m_{i}$ sur chaque résidu. Et si la division est exacte, le problème est réglé.

Dans le cas d'une réduction modulaire d'un nombre $A$ par un autre nombre $B$, une approche désormais standard est d'utiliser une adaptation de l'algorithme de réduction modulaire de Montgomery. Cependant, il est nécessaire de procéder à des opérations coûteuses de conversion de base.

Une fois cette opération de réduction modulaire définie, il devient possible de construire une division euclidienne classique en utilisant la formule évidente $A=B\times q+\mid A\mid _{B}$, où $\mid A\mid _{B}$ est une notation pour $A{\pmod {B}}$.

Articles connexes

• Sun Zi
• Système couvrant