Système modulaire de représentation

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.

Sommaire

1 Définitions

1.1 Exemple

2 Opérations

2.1 Addition et multiplication

2.2 Division

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}$ . 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.

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

Catégories :
Théorie algorithmique des nombres
Arithmétique modulaire

$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)$

Contenu soumis à la licence CC-BY-SA. Source : Article Système modulaire de représentation de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

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 … Wikipédia en Français
Système modulaire de représentation : 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 … Wikipédia en Français
Système modulaire de représentation : 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 … Wikipédia en Français
Systeme de numeration — Système de numération Numérations selon les cultures Numération arabo indienne arabe khmer indienne mongole thaï Numérations à l’origine chinoise chinoise japonaise à bâtons suzhou Numérations alphabétiques … Wikipédia en Français
Système numéral — Système de numération Numérations selon les cultures Numération arabo indienne arabe khmer indienne mongole thaï Numérations à l’origine chinoise chinoise japonaise à bâtons suzhou Numérations alphabétiques … Wikipédia en Français
Système de numération — Un système de numération est un ensemble de règles d utilisation des signes, des mots ou des gestes permettant d écrire, d énoncer ou de mimer des nombres. Sous leur forme écrite, ces derniers sont nés, en même temps que l écriture, de la… … Wikipédia en Français
Representation mentale — Représentation mentale La représentation mentale est une représentation que l on se fait, par la pensée, d une image, d un concept ou d une situation. Une représentation mentale peut être de l ordre du réel ou du fictif. Sommaire 1 Généralités 2… … Wikipédia en Français
Représentation (Psychologie) — Représentation mentale La représentation mentale est une représentation que l on se fait, par la pensée, d une image, d un concept ou d une situation. Une représentation mentale peut être de l ordre du réel ou du fictif. Sommaire 1 Généralités 2… … Wikipédia en Français
Systeme multi-agents — Système multi agents Un système multi agent (SMA) est un système composé d un ensemble d agents, situés dans un certain environnement et interagissant selon certaines relations. Un agent est une entité caractérisée par le fait qu elle est, au… … Wikipédia en Français
Système multi-agent — Système multi agents Un système multi agent (SMA) est un système composé d un ensemble d agents, situés dans un certain environnement et interagissant selon certaines relations. Un agent est une entité caractérisée par le fait qu elle est, au… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Système modulaire de représentation

Sommaire

Définitions

Exemple

Opérations

Addition et multiplication

Division

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Système modulaire de représentation

Sommaire

Définitions

Exemple

Opérations

Addition et multiplication

Division

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link