Brevet FR3083885A1 — publié le 20200117

CIRCUIT DE GÉNÉRATION DE FACTEURS DE ROTATION POUR PROCESSEUR NTT DESCRIPTION DOMAINE TECHNIQUE La présente invention concerne le domaine des processeurs NU (Number Theoretic Tronsform). Elle trouve notamment application dans la cryptographie sur réseau euclidien, en particulier dans la cryptographie homomorphe. ÉTAT DE LA TECHNIQUE ANTÉRIEURE La transformée en nombres entiers ou NU (Number Theoretic Transform) est connue depuis les années 70 et a retrouvé récemment un intérêt dans les applications cryptographiques. On rappelle qu'une transformée en nombres entiers est l'équivalent d'une transformée de Fourier dans un corps de Galois de caractéristique t h GF(q), la racine 2:r primitive d'une transformée de Fourier d'ordre N dans L, à savoir e' A1, étant remplacée par une racine N ème de l'unité du corps GF(q). Ainsi, N est le plus petit entier n non nul tel que vt =1. La transformée en nombres entiers d'une séquence a= a0 de N éléments de GF(q) est définie par une séquence A = /10,...,&, telle que : (1) où les opérations d'addition et de multiplication sont celles du corps GF(q). Il convient de noter que (7- n'est pas nécessairement une racine primitive de GE (g) , autrement dit son ordre n'est pas nécessairement égal à l'ordre y- I du groupe multiplicatif de GF(q) mais que l'ordre N de yi est nécessairement un diviseur de q -1. n-0 2 Si N et q sont premiers entre eux, il existe un inverse 1\U' dans le corps de Galois GF(q) et l'on peut définir la transformée en nombres entiers inverse ou INTT (Inverse NTT) par : N-I 5 a ' = A yi-nk (2) k=0 les inverses yrnk existant dans la mesure où GF(q) est un corps. Par analogie avec la transformée de Fourier, les éléments Kfr et gr"- apparaissant dans l'expression (1) ou (2), sont dénommés facteurs de rotation. 10 De manière générale, la caractéristique q d'un corps est de la forme q = If où p est un nombre premier et in est un entier non nul. Nous considérerons dans la suite les corps finis GF(q) dont la caractéristique est un nombre premier p , dont on sait qu'ils sont isomorphes à Z =ZIpZ . Une présentation générale de la NTT pourra être trouvée dans l'article de J.M. 15 Pollard « The fast Fourier transform in a finite field » publié dans Mathematics of Computation, vol. 25, N° 114, avril 1971, pp. 365-374. La transformée NTT est utilisée en arithmétique RNS (Residue Number System) dans le contexte de la cryptographie sur réseau euclidien où elle permet de simplifier considérablement la multiplication de polynômes de degrés élevés et de grands 20 coefficients. En effet, on sait que la multiplication de deux polynômes nécessite de calculer la convolution de la séquence des coefficients du premier polynôme avec la séquence des coefficients du second polynôme. En se plaçant dans l'espace dual, c'est-à-dire après NTT, la multiplication des polynômes ne nécessite plus qu'une simple multiplication un à un des coefficients des séquences transformées. Il suffit alors d'effectuer une INTT de la séquence résultante pour obtenir les coefficients de la séquence correspondant au produit des deux polynômes. 3 Cette accélération du calcul polynomial peut s'appliquer à une représentation RNS des polynômes. Plus précisément, si l'on considère un polynôme , on peut lui faire correspondre un ensemble L de polynômes f CO= (titi où t_o aP =oei modp, et pi , e=0,...,L -1 sont des entiers premiers entre eux(et 5 généralement premiers) choisis relativement petits. L'ensemble {p0, est dénommé base RNS. Cette représentation des coefficients et, par voie de conséquence, du polynôme associé, est une application immédiate du Théorème des Restes Chinois ou CRT (Chinese Remainders Theorem). On notera dans la suite CRT (aj={ce, et) 1 et 10 CRT(f)=If(a) t' Réciproquement, à une représentation RNS f(1)(x)= , = 0,.., L- I , on peut associer un polynôme f =ICRT{f(o) [(L-01 défini par f(x)=Icp, où les 1-0 coefficients a, -/CRTIOC,. (41" 1)1 sont donnés par : 15 rH( p f \-1 .ceic mod p, mod P (3 '=0 \ .Pi L-1 et où P _np,, est le produit des nombres premiers utilisés pour la décomposition RNS des coefficients. Ainsi, la multiplication de deux polynômes de degré N ,f(x)= et 1=0 20 g(x) =1/4' peut être ramenée par représentation RNS et transformée NU à N.L 4 N-1 N-1 P''il, multiplications des coefficients Aï. = ) et Bk" =1, ) (y,), k N-1 dans l'espace dual où yr1 est une N ème racine de l'unité du corps Z et af(d13,(1) sont des éléments de Z obtenus par décomposition des coefficients a, et fi dans la base RNS p,1 Il est ensuite possible de revenir à l'espace de départ au moyen d'une 5 transformée inverse INTT de chaque séquence de coefficients Cc') = S-1 k N -1 pour obtenir les coefficients en représentation RNS y`kg (-W)ik i=0 puis les coefficients du polynôme produit h(x) =f(x)g(x) par ICRT. Etant donné que le degré de h(x) est 2N , on peut considérer d'emblée des polynômes de degré W' = 2N (et donc des racines N'ème de l'unité) en bourrant de N zéros (zero padding) les N 10 coefficients de plus forts degrés de f (x) et g (x) . Moyennant cette convention, on peut rester dans le même espace pour le polynôme produit et les polynômes .f (x) et g(x) à multiplier. On pourra trouver une description détaillée de l'application de la transformée NU à la multiplication de polynômes en représentation CRT dans l'article de W. Dai et al. 15 intitulé « Accelerating NTRU based homomorphic encryption using GPUs » publié dans Proc. of IEEE High Performance Extreme Computing Conference (HPEC), 2014, 9-11 Sept. 2014. Une multiplication polynomiale utilisant une transformée NU des coefficients de polynômes représentés dans une base RNS requiert de disposer des racines de l'unité yr, 20 des corps finis Z,, ainsi que de leurs puissances (et) , n = N - I , tant pour le calcul de la transformée NU des coefficients (en représentation RNS) des polynômes à multiplier que pour le calcul de la transformée INTT des coefficients (en représentation RNS) du polynôme produit dans l'espace dual. Une première approche consiste à stocker en mémoire les facteurs de rotation 25 n = N -1, pour les corps finis Zpr , L = L-1. Toutefois, étant donné que les degrés des polynômes sont généralement très élevés et que les cryptoprocesseurs 5 doivent pouvoir opérer sur une grande variété de corps finis et de racines de l'unité, la taille mémoire requise est importante. Une seconde approche consiste à effectuer le calcul des facteurs de rotation à la volée pour les fournir au processeur chargé du calcul de la NU. 5 Un objet général de la présente invention est de proposer un circuit de génération de facteurs de rotation pour processeur NU qui permette d'accélérer les calculs cryptographiques sur réseau euclidien. Un objet plus spécifique de la présente invention est de proposer un circuit de génération de facteurs de rotation qui puisse s'adapter au rythme de traitement d'un processeur NU par flot, tout en ne requérant que peu de 10 ressources mémoire locale et/ou ne présentant qu'une faible latence de calcul. EXPOSÉ DE L'INVENTION La présente invention est définie par un circuit générateur de facteurs de rotation sur au moins un corps fini, pour processeur NU par flot, ledit circuit générateur étant 15 destiné à générer au moins une séquence de N facteurs de rotation où y./ est une racine de l'unité dans ce corps, ledit circuit comprenant au moins un module gestionnaire de cache comprenant une mémoire cache et un contrôleur local contrôlant l'écriture et la lecture dans la mémoire cache ; un banc de multiplieurs modulaires comprenant une pluralité de W 20 multiplieurs modulaires opérant en parallèle, chaque multiplieur modulaire effectuant une multiplication sur ledit corps de deux opérandes issus d'un mot lu de la mémoire cache ; un contrôleur central initialisant la mémoire cache avec les G premiers facteurs de rotation de la séquence et contrôlant le gestionnaire de cache de manière à fournir à chaque cycle de calcul d'une pluralité T =N 11/V de cycles de calcul, un mot lu de 25 la mémoire cache au banc de multiplieurs modulaires, à écrire dans la mémoire cache, au terme de chaque cycle de calcul, hormis pour le dernier de ladite pluralité, un mot comprenant les W résultats en sortie desdits multiplieurs modulaires, et à fournir au terme de chaque cycle de calcul, en sortie du générateur, ces W résultats comme W facteurs de rotation consécutifs de ladite série. 6 Selon un premier mode de réalisation, le le banc de W multiplieurs modulaires effectue respectivement les multiplications R0=U0U1 mod p ; R1 = Ut, mod p ;... ; mod p où U est le mot lu de la mémoire cache et U, w=0,...,W sont les opérandes en entrée du banc des multiplieurs modulaires et R, w = 0,...,W -1 5 sont les 117 résultats en sortie de ces multiplieurs. La mémoire cache comprend avantageusement une première partie de taille W et une seconde partie de taille LatMM +1 où LatMM est la latence du banc de multiplieurs modulaires, le contrôleur central initialisant le contenu de la première partie de la mémoire cache avec itt et la seconde partie avec y» , le mot lu de la 10 mémoire cache pour le premier cycle de calcul étant U'Ui...U, =V4.07-2...Vy Dans ce cas, à chaque fois qu'un facteur de rotation calculé par le banc de multiplieurs modulaires est un multiple de W, une adresse dans la seconde partie de la mémoire cache est incrémentée et le facteur de rotation est stocké à l'adresse ainsi incrémentée. 15 La mémoire cache peut comprendre en outre un pointeur d'adresse pointant vers l'adresse où lire la valeur de U, pour le prochain cycle de calcul, les valeurs de étant lues de la première partie et le mot Up,...U', formé par la concaténation de ces valeurs étant fourni au banc de multiplieurs modulaires pour le prochain cycle de calcul. Selon un second mode de réalisation, le banc de W multiplieurs modulaires 20 effectue respectivement les multiplications R0=U0U1 mod p ; R1=U1U1mod p ; R1=u,u, mot! p...; R = U U w mod p où Uot./,...U'' est le mot lu de la mémoire cache 2 2 2 et U, sont =O. - sont les opérandes en entrée du banc des multiplieurs modulaires et 2 w= 0, ...,147 -1 sont les W résultats en sortie de ces multiplieurs. Avantageusement, la mémoire cache est N w -1 , le contrôleur central W 2 25 initialisant le contenu de la mémoire cache avec y» , 7 Dans ce cas, après qu'un mot est lu de la mémoire cache pour préparer un cycle de calcul, le contenu de cette mémoire est décalé de - et, qu'au terme du cycle de calcul, 2 le mot constitué par les résultats en sortie du banc de multiplieurs modulaires est stocké à la suite du contenu ainsi décalé. 5 Avantageusement, quel que soit le mode de réalisation, ledit circuit générateur est destiné à générer une pluralité L de séquences de N facteurs de rotation ttui2,ti.,-,1,y/02,..,/p71 où les éléments yi, C =0,...,L-1 sont des racines N ème de l'unité dans une pluralité L de corps fini, ledit circuit générateur comprenant : une pluralité L de modules gestionnaires de cache, chaque module 10 gestionnaire de cache comprenant une mémoire cache et un contrôleur local contrôlant l'écriture et la lecture dans la mémoire cache correspondante ; - un banc de multiplieurs modulaires mutualisé entre les différents modules gestionnaires de cache ; - un contrôleur central initialisant tour à tour les L mémoires cache avec les 15 G premiers facteurs de rotation de la séquence tel , et contrôlant chaque gestionnaire de cache de manière à fournir, pour chaque cycle de calcul d'une pluralité T = N IW de cycles de calcul, un mot lu de la mémoire cache au banc de multiplieurs modulaires, à écrire dans la mémoire cache associée à ce gestionnaire de cache, au terme de chaque cycle de calcul, hormis pour le dernier de ladite pluralité, un mot comprenant 20 les W résultats en sortie du banc de multiplieurs modulaires, et à fournir au terme de chaque cycle de calcul, en sortie du générateur, ces W résultats comme un ensemble de W facteurs de rotation consécutifs de ladite séquence, les ensembles de W facteurs de rotation relatifs aux L séquences étant fournis de manière entrelacée. Chaque module gestionnaire de cache peut être pourvu en entrée d'un 25 multiplexeur contrôlé par le contrôleur central, de manière à transmettre à la mémoire cache associée au module gestionnaire de cache, soit un mot d'initialisation les G premiers facteurs de rotation de la séquence correspondante, soit W résultats du banc de multiplieurs modulaires. 8 BRÈVE DESCRIPTION DES DESSINS D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture d'un mode de réalisation préférentiel de l'invention, décrit en référence aux figures jointes parmi lesquelles : 5 La Fig. 1 représente de manière schématique un graphe des dépendances pour la génération des facteurs de rotation ; La Fig. 2 représente de manière schématique un premier exemple de recouvrement du graphe de la Fig. 1, correspondant à une première stratégie de génération des facteurs de rotation ; 10 La Fig. 3 représente de manière schématique un second exemple de recouvrement du graphe de la Fig. 1, correspondant à une seconde stratégie de génération des facteurs de rotation ; La Fig. 4 représente de manière schématique l'architecture générale d'un circuit de génération de facteurs de rotation selon un premier mode de réalisation de l'invention ; 15 La Fig. 5 représente de manière schématique l'architecture générale d'un banc de multiplieurs modulaires pour le circuit de génération de la Fig. 4; La Fig. 6A représente de manière schématique un premier exemple de banc de multiplieurs modulaires ; La Fig. 6B illustre la stratégie de génération des facteurs de rotation au moyen du 20 banc de multiplieurs modulaires de la Fig. 6A; La Fig. 6C représente de manière schématique l'ordonnancement des calculs dans le circuit de génération des facteurs de rotation lorsque le banc de multiplieurs modulaires est celui de la Fig. 6A; La Fig. 7A représente de manière schématique un second exemple de banc de 25 multiplieurs modulaires ; La Fig. 7B illustre la stratégie de génération des facteurs de rotation au moyen du banc de multiplieurs modulaires de la Fig. 7A; La Fig. 7C représente de manière schématique l'ordonnancement des calculs dans le circuit de génération des facteurs de rotation lorsque le banc de multiplieurs modulaires est celui de la Fig. 7A; 9 La Fig. 8 représente de manière schématique l'architecture générale d'un circuit de génération de facteurs de rotation selon un second mode de réalisation de l'invention ; La Fig. 9 représente de manière schématique l'ordonnancement des calculs dans le circuit de génération des facteurs de rotation de la Fig. 8. 5 EXPOSÉ DÉTAILLÉ DE MODES DE RÉALISATION PARTICULIERS Nous considérerons tout d'abord la génération de facteurs de rotation dans un corps fini, que l'on assimilera à Z1, où p est un nombre premier, à un isomorphisme près et donc sans perte de généralité. Si yi est une racine N ème de l'unité dans ce corps, le 10 problème en question est de générer l'ensemble des éléments {y,'" = -11. Ces facteurs de rotation sont destinés à être fournis à un processeur NTT ou, de manière équivalente, à un processeur INTT, à une cadence prédéterminée. La génération des facteurs de rotation peut être représentée à l'aide d'un graphe orienté, dit graphe des dépendances, dans lequel chaque noeud représente une puissance 15 , une puissance étant associée à autant de noeuds que de manières de la calculer à partir des noeuds précédents. Chaque noeud du graphe, hormis celui représentant la racine w, est supposé avoir un degré entrant (nombre d'arcs aboutissant à ce noeud) inférieur ou égal à 2, autrement dit chaque facteur de rotation yin est généré à partir d'au plus 2 facteurs précédents seulement. 20 La Fig. 1 illustre le graphe des dépendances pour la génération des six premiers éléments de la série {gt n =0,.. -11. Les arcs identifient les parents de chaque noeud. Ainsi, par exemple, V peut être calculé de six manières différentes selon les parents choisis. Le poids associé à chaque arc est celui du facteur de parenté. Ainsi, un noeud peut 25 être l'extrémité de deux arcs de poids 1 (par exemple y/ est calculé comme le produit Vy» ou y2y/ 4 à partir de deux noeuds parents distincts) ou d'un seul arc de poids 2 (par exemple (v6 est calculé comme le produit V(//3 à partir d'un seul noeud parent). 10 Le graphe des dépendances peut être parcouru de manière à minimiser les besoins en mémoire locale ou la latence de calcul pour la génération des facteurs de rotation. La Fig. 2 représente un premier exemple un recouvrement du graphe de la Fig. 1, 5 visant à minimiser les besoins en ressources mémoire. Par recouvrement du graphe en question, on entend un sous-graphe dans lequel chaque noeud a pour parents des noeuds de ce sous-graphe et tel que chaque facteur de rotation de la série lien n = 0,...,N -11 est représenté par un noeud de ce sous-graphe. Le recouvrement de graphe illustré en Fig. 1 correspond à une minimisation des 10 ressources en mémoire locale pour la génération de la série lyt" 0,...,N -11. En effet, dans ce cas, il suffit de garder en mémoire la racine de l'unité yr et les facteurs de rotation se calculent au moyen de la relation de récurrence suivante : R=1 = (4) = RR,, n e N - 1] 15 On note toutefois que la latence de calcul correspondant à cette stratégie de génération est élevée dans la mesure où il faut attendre n étapes de récurrence avant de disposer du facteur de rotation V. 20 La Fig. 3 représente un second exemple d'un recouvrement du graphe de la Fig. 1, visant à minimiser la latence de calcul. Ainsi, par exemple, comme illustré sur la Fig. 3, il n'est plus nécessaire d'attendre la génération de (/ pour calculer e. Un facteur de rotation est généré dès que les facteurs de rotation des noeuds parents sont disponibles. 25 En revanche, cette stratégie de génération nécessite de pouvoir stocker des facteurs de rotation précédemment générés. Par exemple, il sera nécessaire de stocker y» pour la future génération de q» et (eh pendant que l'on calcule y» = y/y/2. 11 La stratégie de génération des facteurs de rotation correspondant à ce recouvrement de graphe peut être représentée par la relation de récurrence suivante : 120=1; R1= 5 et Vtz Rin= R,n+, = (5) Dans les exemples précédents, on a supposé que l'on disposait au départ du seul facteur de rotation yx. Toutefois, de manière générale, on pourra disposer de G facteurs de rotations initiaux, correspondant aux G premiers éléments de la série, soit 10 Dans la suite, nous supposerons en outre que le circuit de génération de facteurs de rotation génère la série {w" n =0,...,N -il sur plusieurs cycles, la totalité des facteurs de rotation de la série étant générée au bout de T =N IW cycles. A chaque cycle, le processeur NU effectue une opération radix (similaire à une opération radix dans une FFT) 15 portant sur W données d'entrée. Nous supposerons enfin, pour des raisons de simplification de la présentation que G =W , autrement dit que l'on dispose d'autant de facteurs de rotation initiaux que la largeur du chemin de données, et que W et N sont des puissance de 2. 20 La Fig. 4 représente de manière schématique l'architecture générale d'un circuit de génération de facteurs de rotation selon un premier mode de réalisation de l'invention. Le circuit de génération 400 comprend essentiellement un module gestionnaire de cache, 410, un banc de multiplieurs modulaires, 420, et un contrôleur central, 430. Le module gestionnaire de cache dispose d'un contrôleur local, 411, d'une 25 mémoire cache 412, d'un registre de sortie 415 pour fournir W facteurs de rotation à chaque cycle ainsi que d'un registre de sortie intermédiaire 417 pour fournir, à chaque début de cycle des opérandes issus de la mémoire cache au banc de multiplieurs modulaires. De manière générale, le module gestionnaire de cache a pour fonction de 12 cadencer les calculs de la série de facteurs de rotation selon la stratégie de recouvrement du graphe de dépendances retenue. Le banc de multiplieurs modulaires reçoit à chaque cycle des opérandes du module gestionnaire de cache, à savoir des puissances tel stockées dans la mémoire cache, 5 et en déduit les facteurs de rotation à fournir pour le cycle courant. Les facteurs de rotation ainsi calculés sont fournis au registre de sortie 415 et stockés dans la mémoire cache. Plus précisément, les résultats en sortie des multiplicateurs modulaires sont fournis à un registre d'entrée intermédiaire 407 avant d'être transmis au registre de sortie 415 et stockés dans la mémoire cache 412. 10 Au début de chaque séquence de T cycles, les G facteurs de rotation initiaux Igi qfq sont fournis au module gestionnaire de cache 410 via un registre d'entrée 405. Les sorties du registre d'entrée et du registre d'entrée intermédiaire sont multiplexées par le multiplexeur 409. Ce multiplexeur, piloté par le contrôleur central 430, transmet les facteurs de rotation initiaux vers l'entrée du module gestionnaire de cache lors de 15 l'initialisation d'une série de T cycles, puis les facteurs de rotation calculés par le banc de multiplieurs modulaires vers l'entrée du module gestionnaire de cache au début de chacun des T-1 cycles suivants de la série. Le contrôleur central 430 génère un ensemble GenCtr/ de signaux de contrôle constitué composé des signaux new set, complue et new data qui pilotent le 20 contrôleur local du module gestionnaire de cache. Le premier signal de contrôle, new set , sert à initialiser le gestionnaire de calcul tous les T cycles et en particulier de remettre à zéro les compteurs internes du contrôleur local. Il ordonne également au multiplexeur d'entrée 409 de transmettre au module gestionnaire de cache, les facteurs de rotation 1 initiaux {ri vjG reçus sur le registre d'entrée 405. Le second signal de contrôle, 25 compute , commande au module gestionnaire de cache d'effectuer un cycle de calcul, c'est- à-dire de lire les opérandes dans la mémoire cache et les fournir au banc de multiplieurs modulaires 420. Le troisième signal de contrôle, new data, indique au contrôleur local qu'il doit prendre en considération les nouveaux facteurs de rotation calculés par le banc de multiplieurs modulaires. En retour, le contrôleur local informe le contrôleur central 13 lorsqu'il est prêt à effectuer un nouveau calcul au moyen d'une information de disponibilité data _available . Plus précisément, cette information de disponibilité prend une valeur logique haute lorsque le cache 412 contient les facteurs de rotation permettant de calculer les éléments suivants de la série et que le contrôleur central n'a pas encore commandité 5 ces calculs au moyen du signal complue Le contrôleur local comprend un premier compteur comptabilisant le nombre de facteurs de rotation déjà générés, un second compteur comptabilisant le nombre de facteurs de rotation stockés dans la mémoire cache et un troisième compteur comptabilisant le nombre de cycles de calcul demandés par le contrôleur central depuis la 10 dernière initialisation (c'est-à-dire depuis le début de la série). Le contrôleur local comprend un circuit de logique combinatoire recevant les signaux de contrôle du contrôleur central et fournissant les signaux de contrôle des compteurs précités, l'information de disponibilité, les signaux de contrôle de la mémoire cache ainsi que celui du registre de sortie. Le signal de contrôle du registre de sortie permet de fournir sur le bus 15 de sortie les W derniers facteurs de rotation générés. Le contrôleur central est essentiellement composé d'un circuit de logique combinatoire et d'un registre à décalage. La profondeur du registre à décalage est déterminée en fonction de la latence du banc de multiplieurs modulaires (pour effectuer les calculs) ainsi que de la latence du module gestionnaire de cache (pour mettre à jour le 20 registre de sortie et son registre de sortie intermédiaire). Le registre à décalage avance à chaque cycle d'horloge. Le contrôleur central reçoit en entrée un signal new_input lui indiquant qu'un nouvel ensemble de facteurs de rotation initiaux fvd,...,(v,G1 est disponible sur le bus d'entrée pour une nouvelle série de calculs de facteurs de rotation {v" n =0,...,N -11 où 25 est une nouvelle racine de l'unité dans Z,. Comme on l'a vu plus haut le contrôleur central reçoit également du module gestionnaire de cache l'information de disponibilité data avouable . A partir des signaux new input et data available le circuit de logique combinatoire du contrôleur central génère les signaux de contrôle new set, (-ampute et new data pour le prochain cycle de calcul. En outre, le circuit de logique combinatoire 14 met à jour l'entrée du registre à décalage à chaque début de cycle de calcul. En sortie du registre à décalage, autrement dit après avoir pris en compte les latences respectives du banc de multiplieurs modulaires, un signal valid est généré, indiquant qu'un jeu de W facteurs de rotation est disponible sur le bus de sortie. 5 La Fig. 5 représente de manière schématique l'architecture générale d'un banc de multiplieurs modulaires pour le circuit de génération de la Fig. 4. Elle comprend une matrice d'interconnexion, 510, destinée à recevoir les opérandes issus de la mémoire cache et à les distribuer sur les entrées de W multiplieurs 10 modulaires opérant en parallèle, 520, désignés par MNID,...,MMW_I, chaque multiplieur modulaire MM effectuant une multiplication modulo p de ses deux opérandes d'entrée pour fournir le résultat R. La Fig. 6A représente de manière schématique un premier exemple de banc de 15 multiplieurs modulaires. Cet exemple d'implémentation correspond à une stratégie de minimisation de la taille de la mémoire cache du module gestionnaire de cache. La matrice d'interconnexion reçoit W +1 opérandes et les distribue sur les 2W entrées des multiplieurs modulaires. Dans cet exemple G=W =4 et les opérandes sont notés U, .,U, . Les 20 multiplieurs modulaires effectuent les calculs suivants : Ro=U,,U, mod p R,=UoU, mod p Rip =LI», mod p 25 R3=110L14 raod p (6) De manière générale, selon la stratégie de minimisation de la taille du cache, le banc de multiplieurs modulaires effectue les opérations suivantes : 15 =UuL rnod p 121 =111.12 mod p /21 = U'U, mod p (7) 5 La Fig. 6B illustre la stratégie de génération des facteurs de rotation au moyen du banc de multiplieurs de la Fig. 6A pour N =32 et une latence du banc de multiplieurs modulaires LatMM =3 . On rappelle que dans l'exemple de la Fig. 6A, G =W = 4. On a représenté en 650 à 657 les sorties du banc de multiplieurs modulaires ou 10 plus précisément les données en sortie du multiplexeur 409 (dans la mesure où 650 correspond à l'état d'initia lisation), pour 8 cycles de calcul successifs. Les valeurs figurant dans les cases en trait discontinu sont celles qui sont stockées dans une seconde partie de la mémoire cache comme expliqué ci-après. 15 La Fig. 6C représente de manière schématique l'ordonnancement des calculs dans le circuit de génération des facteurs de rotation lorsque le banc de multiplieurs modulaires est implémenté comme en Fig. 6A. On a représenté en 661, les opérandes Un,...,U, en entrée de la batterie des multiplieurs modulaires ; en 662 et 663 une première partie et une seconde partie de la 20 mémoire cache, notées AGRS et AGRO ; en 665 les résultats en sortie du banc de multiplieurs modulaires. La taille de AGRS est égale à W, celle de AGRO est égale à LaiMM +1. (on a supposé dans l'exemple illustré que le banc de multiplieurs modulaires présentait une latence LatAIM de 3 cycles d'horloge). 25 Les emplacements mémoire de AGRS sont notés Co,....C' ceux de AGRO sont notés 4,...,133. On stocke dans AGRS en Co,...,C, les derniers résultats fournis par 4, R3 et dans AGRO en B3, des facteurs de rotation, dits de réserve, définis comme les LaiMM +1 premiers facteurs de rotation yi de la série où i est un multiple de W . 16 Pour des raisons de clarté, les exposants i ont été représentés en lieu et place des facteurs de rotation correspondants r. Les opérandes U...., U4 sont lus des emplacements mémoire Cr, C, de AGRS et l'opérande U' est lu de AGRO à l'adresse donnée par l'index Ind en 664. Cet index est 5 généré par le contrôleur local du module gestionnaire de cache. Le calcul de la série des facteurs de rotation V21 débute avec la réception des valeurs initiales tr.....V1 . Ces valeurs initiales sont stockées (au temps ) en mémoire cache aux emplacements CO3..., C1. La valeur initiale v4 étant un facteur de rotation de réserve, elle est en outre stockée en 130. Les valeurs stockées dans la mémoire 10 cache sont fournies au banc de multiplieurs modulaires avec Un =(B0)=v4 , =( )= , U2= (c, )- u, -(c2)- u, -(c,)- yi4 Les résultats apparaissant en sortie du banc de multiplieurs modulaires au bout de LatMM cycles d'horloge (au temps t,) sont alors R' = çA, R1 = V6 , R, =V7 , R, = çA. Ces résultats sont ensuite stockés (au temps t',) aux emplacements de AGRS et yA 15 étant un facteur de rotation de réserve est stocké à l'emplacement 131. Les opérandes sont lus des emplacements mémoire de AGRS et l'opérante U0 est lu de AGRO à l'adresse donnée par l'index Ind , soit de B' soit : U, -(B1)- y?, U = (C')= U2 =(CI)= ), U3 = (C2)=V U4 = (C3)= . Les résultats apparaissant en sortie du banc de multiplieurs modulaires au bout de 20 LatMM cycles d'horloge (au temps t,) sont alors R0= W.9 R = = , !? = yfl2 Le processus se poursuit jusqu'à la génération de la dernière série de W facteurs de rotation en t4,soit Ro = te29, R, el, R2 = R,=v" . La Fig. 7A représente de manière schématique un second exemple de banc de 25 multiplieurs modulaires. 17 Cet exemple d'implémentation correspond à une génération au plus tôt des facteurs de rotation. La matrice d'interconnexion reçoit ici -+ I opérandes et les distribue sur les 2W 2 entrées des multiplieurs modulaires. 5 Dans cet exemple G =1,17 = 4 et les opérandes dont notés Uo,UI,U, . Les multiplieurs modulaires MM'...., MM, effectuent les calculs suivants : R'=U'U, mod p R,=U,U, mod p 10 R,=U1U2 rnod p Ri =U2U, mod p (8) De manière générale, selon la stratégie de minimisation de la latence de calcul, le banc de multiplieurs modulaires effectue les opérations suivantes : 15 R'=U'U, mod p rnod p R, =U,U2 mod p 20 R =UU w mod p (9) 7 7 La Fig. 7B illustre la stratégie de génération des facteurs de rotation au moyen du banc de multiplieurs modulaires de la Fig. 7A. On a représenté en 750 à 757 les sorties du banc de multiplieurs modulaires ou 25 plus précisément les données en sortie du multiplexeur 409 (dans la mesure où 750 correspond à l'état d'initialisation), pour 8 cycles de calcul successifs. 18 La Fig. 7C représente de manière schématique l'ordonnancement des calculs dans le circuit de génération des facteurs de rotation lorsque le banc de multiplieurs modulaires est implémenté comme en Fig. 7A. On a représenté en 761, les opérandes Un,U,,U, en entrée de la batterie des 5 multiplieurs modulaires; en 763 les emplacements de la mémoire cache Cu C, ; en 765 les résultats R en sortie du banc de multiplieurs modulaires. On a supposé ici que la latence du banc de multiplieurs modulaires était de LaiMM = 5 cycles d'horloge. Le calcul de la série des facteurs de rotation Itt»,...,y// débute comme précédemment avec la réception des valeurs initiales {y .....y4) . Les valeurs initiales 10 {y4 sont sont stockées (au temps t') en mémoire cache aux emplacements Les valeurs stockées dans la mémoire cache sont fournies au banc de multiplieurs modulaires avec Un = (Cn)= , U=(C1)=V3 U,=(C1)=yi4. Une fois ces valeurs fournies, le contenu de la mémoire est décalé de 2 emplacements au coup d'horloge suivant (au temps O. Ainsi, dans le cas présent, après décalage, seule la valeur V reste 15 stockée, à l'emplacement C, . Les résultats apparaissant en sortie du banc de multiplieurs modulaires au bout de LatMM (au temps t,) sont alors Ro = V5 R, = V6 , R2 =Va R, =V' . Les résultats sont stockés à la suite de C0 aux emplacements pour la préparation des calculs suivants. 20 Les valeurs stockées en CO3C1,C, sont ensuite fournies (au temps t7) au banc de multiplieurs modulaires, à savoir : U0-(C0)=r4 , U, -(C,)- , u, =(C2)= V16 . Une fois ces valeurs fournies, le contenu de la mémoire cache est à nouveau décalé de deux emplacements. Ainsi, seules restent stockées dans le cache les valeurs e , . Au temps t, les valeurs stockées dans la mémoire cache sont fournies au banc de 25 multiplieurs modulaires avec U, -(C')- , U1-(C1)- , U, -(C2)- (e, puis le 19 contenu de la mémoire cache est à nouveau décalé de deux emplacements : seule la valeur V reste stockée en C'. Les résultats apparaissant en sortie du banc de multiplieurs modulaires au temps t11 sont alors R0= y'9, 121= yll), /22 = R3=v12 . Les résultats sont stockés à la 5 suite de C' aux emplacements pour la préparation des calculs suivants. Au temps t13, les valeurs stockées sont fournies à la batterie de de multiplieurs modulaires avec U, =(ç)=V, U,=((;)=V9 , U,=(C2)= Vin . Le processus se poursuit selon la même logique jusqu'au temps t' où le banc de multiplieurs modulaires fournit les derniers W facteurs de rotation ty/29,..., V21 . 10 Dans le cas présent, toutes choses étant égales par ailleurs, le calcul de la série complète {y»,...,y/32} est aussi rapide dans le premier exemple que dans le second. En effet, dans le premier exemple si la latence avait été LettAIM =5 , le calcul aurait également été terminé qu'au temps t' . Cependant, de manière générale avec un recouvrement de graphe de dépendance du type de la Fig. 7B, le calcul de la série complète des facteurs de 15 rotation est plus rapide (plus précisément la cadence -N ) que pour un recouvrement de type de la Fig. 6B. La taille de la mémoire cache dans le second exemple est de N -W. En effet, à 2 W chacun des -N I calculs, on écrit W facteurs de rotation et on en élimine -, la taille 2 ( mémoire nécessaire pour ne pas écraser des données utiles est --1 -. Pour des 0/1/ 2 2 20 valeurs élevées du degré N, on vérifie que la taille mémoire requise dans le premier exemple (W +LtuMM +1) est bien inférieure à celle requise dans le second exemple. Dans les deux exemples d'implémentation décrits plus haut, on remarque que des temps d'attente (ou « bulles », par exemple en 670 ou 770) sont présents dans l'alimentation de la batterie des multiplieurs modulaires, en raison de la latence LaiMM 25 et des relations de dépendance à respecter dans le graphe des dépendances. Il en résulte 20 une génération saccadée des facteurs de rotation, à tout le moins des premiers éléments de la série. Ces temps d'attente peuvent être mis à profit dans un second mode de réalisation de l'invention pour calculer des facteurs de rotation sur une pluralité de corps finis Zpe , 5 L-1 dans un contexte de transformées NU en arithmétique RNS. La Fig. 8 représente de manière schématique l'architecture générale d'un circuit de génération de facteurs de rotation selon un second mode de réalisation de l'invention. A la différence du premier mode de réalisation, le circuit de génération des 10 facteurs de rotation comprend ici une pluralité L de modules gestionnaires de cache 8100,...,810Li, ayant chacun la structure du module gestionnaire de cache 410. Chacun de ces modules est associé à un corps fini Zpe et dispose de son contrôleur local ainsi que de sa mémoire cache. En sortie de chacun de ces modules, on retrouve un bus de sortie et un bus de sortie intermédiaire. 15 Les bus de sortie des différents modules gestionnaires de cache sont multiplexés par un premier multiplexeur de sortie 841 contrôlé par le contrôleur central au moyen d'une commande SEL output . De même, les bus de sortie intermédiaire des différents modules gestionnaires de cache sont multiplexés par un second multiplexeur de sortie 842, contrôlé par le contrôleur central au moyen d'une commande SEL _MMS . 20 Comme dans le premier mode de réalisation, le circuit de génération de facteurs de rotation comprend un banc de multiplieurs modulaires, 820, et un contrôleur central, 830. Le banc de multiplieurs modulaires 820 est alimenté en données via un registre commun, 850, en sortie du second multiplexeur de sortie. Il reçoit également du contrôleur 25 central un signal modulo, indiquant aux multiplieurs modulaires dans quel corps Z les multiplications doivent être effectuées. Les facteurs de rotation initiaux sont fournis tour à tour aux modules gestionnaires de calcul, 810, , =0.....L-1, via le registre d'entrée 805. Les facteurs de rotation calculés par le banc de multiplieurs modulaires sont fournis quant à eux via le 21 registre d'entrée intermédiaire 807. Les sorties respectives du registre d'entrée et du registre d'entrée intermédiaire sont chacune distribuées à tous les modules gestionnaires de calcul. Chaque module gestionnaire de cache, 810, possède en entrée un multiplexeur associé, 809,, commandé par le contrôleur central 830. Ainsi le contrôleur central peut 5 indiquer à l'un des modules gestionnaires de calcul 810, d'importer les facteurs de rotation initiaux Itt4,...,ttf,G1 ou bien des facteurs de rotation calculés par le banc de multiplieurs modulaires. Le contrôleur central comprend un circuit de logique combinatoire et deux registres à décalage permettant respectivement de générer les signaux de contrôle des L 10 modules gestionnaires de cache, 810e, L -1, et de propager : le signal de contrôle du multiplexeur de sortie 841, SEL MMS , le signal de contrôle du multiplexeur de sortie intermédiaire 843, SEL output , ainsi que les signaux de validité, valid , et de provenance, num , décrits plus loin. Plus précisément, le contrôleur central reçoit en entrée un signal new input lui indiquant qu'un nouvel ensemble de facteurs de rotation initiaux est 15 disponible sur le bus d'entrée pour une nouvelle série de calculs de facteurs de rotation. Il reçoit également des modules gestionnaires de calcul les informations de disponibilité data available , = 0, ..., L-1, lui indiquant quels sont les modules disponibles pour un nouveau calcul. A partir des signaux new input et data available f , C = L-1, le circuit de logique combinatoire du contrôleur central génère l'ensemble GenCtrl, des 20 signaux de contrôle new set e , compute £ et new data C , £ = L -1 pour le prochain cycle de calcul. Comme nous le verrons plus loin, le contrôleur central peut donner une priorité moins élevée aux calculs les plus avancés. Autrement dit, plus une série est avancée, plus faible sera sa priorité attribuée et plus tardivement le signal compute é correspondant sera mis à jour. 25 En sortie, le contrôleur central fournit les signaux de contrôle pour les premier et second multiplexeurs de sortie 841, 843. Lorsqu'un jeu de 1/17 facteurs de rotation est disponible sur le bus de sortie, le contrôleur central l'indique au moyen du signal valid et précise au moyen du signal num à quel corps Zpr appartient ce jeu. 22 La Fig. 9 représente de manière schématique l'ordonnancement des calculs dans le circuit de génération des facteurs de rotation de la Fig. 8. Sans préjudice de généralisation, le second mode de réalisation sera décrit pour 5 une stratégie de calcul au plus tôt. L'homme du métier comprendra cependant qu'il pourra trouver également à s'appliquer lorsque l'on souhaite minimiser la taille mémoire du cache. On a supposé dans l'exemple d'ordonnancement illustré en Fig. 9 que N = 32, G =W = 4 et donc T =8 . Autrement dit, un nouveau jeu de valeurs initiales est fourni au générateur de facteurs de rotation tous les T = 8 cycles. On 10 a supposé ici que la latence du banc de multiplieurs modulaires était de LatMM =5 cycles d'horloge comme en Fig. 7C. On a représenté en 910, les jeux de valeurs initiales ; en 920, les opérandes en entrée de la batterie des multiplieurs modulaires ; en 930 les résultats en sortie du banc de multiplieurs modulaires et en 940 la sortie du premier 15 multiplexeur de sortie. Les cases en grisé correspondent à l'insertion d'un nouveau jeu de valeurs initiales. Par souci de simplification, le contenu des mémoires cache n'a pas été représenté. On observe qu'après l'arrivée de plusieurs jeux (ici 3), les multiplieurs modulaires sont saturés en données. L'ordonnancement des différentes séries respecte bien le débit de 20 T = 8 cycles de calcul entre les jeux initiaux, au prix d'une légère latence supplémentaire pour la génération de la première série (4 cycles d'horloge supplémentaires correspondant à l'insertion des 2 séries de valeurs initiales suivantes). Enfin, les éléments des différentes séries sont fournis en sortie dès qu'ils REVENDICATIONS1. Circuit générateur de facteurs de rotation (400) sur au moins un corps fini (Z ) pour processeur NU par flot, ledit circuit générateur étant destiné à générer au moins une séquence de N facteurs de rotation Ig." 11 où yir est une racine de l'unité dans ce corps, caractérisé en ce qu'il comprend : au moins un module gestionnaire de cache (410, 8100,..,810L) comprenant une mémoire cache (411) et un contrôleur local (412) contrôlant l'écriture et la lecture dans la mémoire cache ; un banc de multiplieurs modulaires (420, 820) comprenant une pluralité de W multiplieurs modulaires (520) opérant en parallèle, chaque multiplieur modulaire effectuant une multiplication sur ledit corps de deux opérandes issus d'un mot lu de la mémoire cache ; un contrôleur central (430, 830) initialisant la mémoire cache avec les G premiers facteurs de rotation de la séquence et contrôlant le gestionnaire de cache de manière à fournir à chaque cycle de calcul d'une pluralité T =N IW de cycles de calcul, un mot lu de la mémoire cache au banc de multiplieurs modulaires, à écrire dans la mémoire cache, au terme de chaque cycle de calcul, hormis pour le dernier de ladite pluralité, un mot comprenant les W résultats en sortie desdits multiplieurs modulaires, et à fournir au terme de chaque cycle de calcul, en sortie du générateur, ces W résultats comme W facteurs de rotation consécutifs de ladite série. 2. Circuit générateur de facteurs de rotation selon la revendication 1, caractérisé en ce que le banc de W multiplieurs modulaires effectue respectivement les multiplications R,, = U'U, mod p ; mod p ;... ; mod p où Up,...Uw est le mot lu de la mémoire cache et UL, , w = 0,...,W sont les opérandes en entrée du banc des multiplieurs modulaires et R, , w = -1 sont les W résultats en sortie de ces multiplieurs. 24 3. Circuit générateur de facteurs de rotation selon la revendication 2, caractérisé en ce que la mémoire cache comprend une première partie de taille W et une seconde partie de taille LatMM +1 où LatMM est la latence du banc de multiplieurs 5 modulaires, le contrôleur central initialisant le contenu de la première partie de la mémoire cache avec et la seconde partie avec y?, le mot lu de la mémoire cache pour le premier cycle de calcul étant U'U,...U,, = yfwyf'tv2...yfw. 4. Circuit générateur de facteurs de rotation selon la revendication 3, 10 caractérisé en ce qu'à chaque fois qu'un facteur de rotation calculé par le banc de multiplieurs modulaires est un multiple de W, une adresse dans la seconde partie de la mémoire cache est incrémentée et le facteur de rotation est stocké à l'adresse ainsi incrémentée. 15 5. Circuit générateur de facteurs de rotation selon la revendication 4, caractérisé en ce que la mémoire cache comprend en outre un pointeur d'adresse (Ind ) pointant vers l'adresse où lire la valeur de U, pour le prochain cycle de calcul, les valeurs de étant lues de la première partie et le mot U'U,...Uw. formé par la concaténation de ces valeurs étant fourni au banc de multiplieurs modulaires pour le prochain cycle de 20 calcul. 6. Circuit générateur de facteurs de rotation selon la revendication 1, caractérisé en ce que le banc de W multiplieurs modulaires effectue respectivement les multiplications Ro =UJJ, modp ; R1=U1U1 modp ; p 25 = U,U'. mod p où LIOU,...U, est le mot lu de la mémoire cache et U, w = 2 2 2 2 sont les opérandes en entrée du banc des multiplieurs modulaires et /2', w =0,...,W -1 sont les W résultats en sortie de ces multiplieurs. rotation selon la revendication 6, N -, le contrôleur central 2 initialisant le contenu de la mémoire cache avec (Er, 5 8. Circuit générateur de facteurs de rotation selon la revendication 7, caractérisé en ce qu'après qu'un mot soit lu de la mémoire cache pour préparer un cycle de calcul, le contenu de cette mémoire est décalé de - et, qu'au terme du cycle de calcul, 2 le mot constitué par les résultats en sortie du banc de multiplieurs modulaires est stocké à 10 la suite du contenu ainsi décalé. 9. Circuit générateur de facteurs de rotation selon l'une de revendications précédentes, caractérisé en ce que ledit circuit générateur est destiné à générer une pluralité L de séquences de N facteurs de rotation ,ylti f I où les éléments yt, 15 , e =0,...,L -1 sont des racines N ème de l'unité dans une pluralité L de corps finis , L -1), ledit circuit générateur comprenant : une pluralité L de modules gestionnaires de cache (8100,..,810L), chaque module gestionnaire de cache (810É) comprenant une mémoire cache et un contrôleur local contrôlant l'écriture et la lecture dans la mémoire cache correspondante ; 20 un banc de multiplieurs modulaires (820) mutualisé entre les différents modules gestionnaires de cache ; un contrôleur central (830) initialisant tour à tour les L mémoires cache avec les G premiers facteurs de rotation de la séquence 1r,°,(E/,1,(E/,`,.., 1 , et contrôlant chaque gestionnaire de cache de manière à fournir, pour chaque cycle de calcul d'une 25 pluralité T =N IW de cycles de calcul, un mot lu de la mémoire cache au banc de multiplieurs modulaires, à écrire dans la mémoire cache associée à ce gestionnaire de cache, au terme de chaque cycle de calcul, hormis pour le dernier de ladite pluralité, un 25 7. Circuit générateur de facteurs de caractérisé en ce que la taille de la mémoire cache est 26 mot comprenant les W résultats en sortie du banc de multiplieurs modulaires, et à fournir au terme de chaque cycle de calcul, en sortie du générateur, ces W résultats comme un ensemble de W facteurs de rotation consécutifs de ladite séquence, les ensembles de W facteurs de rotation relatifs aux L séquences étant fournis de manière entrelacée. 5 10. Circuit générateur de facteurs de rotation selon la revendication 9, caractérisé en ce que chaque module gestionnaire de cache est pourvu en entrée d'un multiplexeur contrôlé par le contrôleur central, de manière à transmettre à la mémoire cache associée au module gestionnaire de cache, soit un mot d'initialisation les G premiers 10 facteurs de rotation de la séquence correspondante, soit W résultats du banc de multiplieurs modulaires.