Systeme modulaire de representation : RNS

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 utilisé en cryptographie. 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 ensemble 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}$. La famille $\{x_1,\ldots,x_n\}$ est appelée 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.

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é 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.

Ce document provient de « Syst%C3%A8me modulaire de repr%C3%A9sentation ».