Arithmétique sur les corps finis

Intérêt pour le système RNS

Prenons deux entiers x, y et leurs représentations RNS dans la base B notées ~x, ~y. On suppose que x, y < M. L’addition en RNS, notée +~ , est effectuée en réalisant une addition modulaire (addition dans Z/miZ) dans chaque composante RNS : ~x+~ ~y = (|x1 + y1|m1 , . . . , |xn + yn|mn ) (6.5) De même, la multiplication RNS, notée ×~ , est effectuée à travers n multiplications modulaires : ~x×~ ~y = (|x1 × y1|m1 , . . . , |xn × yn|mn ) (6.6) Le résultat des opérations arithmétiques est valide si le résultat attendu est dans [0, M − 1]. Sinon, il sera réduit modulo M. En effet, l’entier correspondant à la représentation RNS ~x+~ ~y est égal à la somme x + y si et seulement si 0 ≤ x + y < M. De même, l’entier correspondant à la représentation RNS ~x×~ ~y est égal au produit x × y si et seulement si 0 ≤ x × y < M. Ce système de représentation est particulièrement intéressant pour l’arithmétique sur des grands entiers, vu qu’il permet de distribuer le calcul sur plusieurs petits résidus. Dans le cas où nous disposons de plusieurs unités calculatoires, les opérations sur les composantes RNS peuvent être parallélisées. Le système RNS ne propage pas de retenue : ainsi, les unités calculatoires qui vont traiter les composantes RNS n’ont pas besoin de communiquer et peuvent être asynchrones [Tay84]. Une autre propriété intéressante de la représentation RNS est qu’il s’agit d’une représentation non-positionnelle, dans le sens où les composantes RNS ont toutes une place équivalente. Dans le cas d’une exécution séquentielle, on peut changer l’ordre de calcul des composantes. Dans le cas d’une exécution parallèle, on peut changer l’association entre les unités calculatoires et les composantes RNS. L’introduction d’aléa dans le traitement des composantes RNS permet de protéger contre certaines attaques physiques de type attaques par canaux cachés. Nous avons vu que les opérations telles que l’addition, la soustraction et la multiplication sont intéressantes en utilisant le système RNS. Cependant, son caractère non-positionnel rend 91 Chapitre 6. Arithmétique sur les corps finis difficile l’information sur l’ordre de grandeur d’un nombre représenté en RNS. Ainsi, il n’y a pas de moyen simple pour détecter le dépassement de capacité, et les implémentations en RNS d’opérations telles que la division ou la comparaison sont plutôt subtiles. Pour la comparaison RNS, plus de détails peuvent être consultés dans [Sou07]. Pour la division, nous nous intéresserons dans ce recueil à comment effectuer cette opération en RNS, plus particulièrement au calcul du reste d’une division. Parmi les premiers articles qui se sont intéressés à cette question, on peut mentionner les travaux de [Gam91, LC92, HK95, BDM98]. 6.2 RNS pour l’arithmétique sur les corps finis Nous avons déjà vu dans les chapitres précédents que l’algèbre linéaire est formée de SpMV (Sparse-Matrix–Vector product) de type v ← Au sur un corps fini de grande caractéristique Z/`Z, où A est la matrice creuse et u et v sont deux vecteurs denses. Nous rappelons que les éléments des vecteurs u et v sont « grands » (c’est-à-dire que leur représentant dans [0, `[ occupe autant de mots machine que `). Pour les coefficients de la matrice A, nous distinguons deux cas (voir la sous-section 3.2.1) : — les matrices FFS : leurs coefficients sont « petits », dans le sens où ils sont bornés par une valeur maximale B inférieur à 2 10 (B peut être encore beaucoup plus petite que cette borne, nous avons dans la sous-section 3.2.1 que B était égal à 36). Nous notons que la grande majorité (autour de 90%) de ces coefficients sont des ±1 ; — les matrices NFS : en plus des coefficients « petits », la matrice contient des coefficients « grands ». L’objectif est de représenter le corps Z/`Z en RNS et d’effectuer les opérations arithmétiques du SpMV en RNS. On commence par convertir le vecteur u de sa représentation entière à sa représentation RNS. Ensuite, on effectue en RNS le produit v ← Au et on réduit le vecteur v modulo `. Enfin, on passe de la représentation RNS du vecteur v à sa représentation entière. Dans le cas de plusieurs produits itérés v ← Aiu (ce qui est le cas de l’algorithme de résolution de Wiedemann, voir sous-section 3.5.2), on préfère n’effectuer qu’une seule conversion de l’entier en RNS (pour u) et une seule conversion de RNS en entier (pour v). En d’autres termes, il est préférable de rester en RNS pendant le calcul de tous les produits itérés, vu que les opérations de conversion d’une représentation à une autre sont coûteuses. De plus, au lieu d’avoir une réduction modulo ` après chaque produit matrice-vecteur, on envisage d’accumuler un certain nombre de produits matrice-vecteur avant de faire une réduction modulo `. Le nombre de produits accumulés dépend de la taille de la base RNS. Si on suppose que x et y sont des éléments des vecteurs v et u respectivement, nous avons besoin des opérations suivantes : 1. calculer ~x à partir de x ; 2. calculer x à partir de ~x. Ces deux opérations ne sont pas critiques vu que, dans le contexte de produits itérés, chaque opération n’est effectuée qu’une seule fois. Nous avons aussi besoin d’effectuer les opérations arithmétiques suivantes en restant en RNS, c’est-à-dire en ne manipulant que des représentations RNS : 3. x ← x ± y ; 4. x ← x + λ × y, où λ est un coefficient « petit » de A ; 5. x ← x + Λ × y, où Λ est un coefficient « grand » de A ; 6. x ← x mod `. Aux opérations précédemment mentionnées, on ajoute l’opération suivante dont on verra l’utilité plus loin dans la sous-section 6.4.2 : 7. convertir la représentation RNS de x d’une base RNS à une autre. On se munit d’une base RNS B = (m1, m2, . . . , mn). On suppose que les mi ont la même taille en bits notée k (c’est-à-dire mi < 2 k ).

Multiplication en RNS 

Tout comme les deux cas précédents, l’opération est effectuée sur les n composantes RNS. L’algorithme donne un résultat valide si et seulement si (` − 1)2 < M. Cette condition est bien entendu contraignante vu qu’il en suit que pour pouvoir multiplier deux éléments de Z/`Z en RNS, on a besoin d’une base RNS deux fois plus grande que la base RNS qui permet de représenter un élément de Z/`Z.Dans une architecture multi-threadée (ou pourvue de plusieurs unités vectorielles) où on dispose de plus que n threads (ou n unités vectorielles), on peut associer pour les trois opérations mentionnées un thread (ou une unité vectorielle) à chaque composante RNS. Ainsi, les opérations élémentaires (opérations dans les composantes RNS) peuvent être effectuées en parallèle par les n threads (ou n unités vectorielles) et la complexité parallèle est égale à la complexité d’une opération élémentaire. 

Réduction modulo

en RNS Le but est de réduire modulo ` une représentation RNS d’un entier x dans [0, M − 1] en restant dans le domaine RNS. Dans la littérature, cette question a été plus généralement étudiée dans les travaux qui cherchent à optimiser la multiplication modulaire avec RNS, qui est une opération centrale dans plusieurs cryptosystèmes. Plusieurs travaux se sont intéressés à la multiplication de Montgomery, parmi lesquels on peut citer les travaux de Bajard et al. [BDK98] et de Kim et al. [KPH04].