Brevet FR2853425A1 — publié le 20041008

SÉQUENCE DE MULTIPLICATION EFFICACE POUR OPÉRANDES À GRANDS NOMBRES ENTIERS PLUS LARGES QUE LE MATÉRIEL MULTIPLICATEUR La présente invention concerne des circuits de traitement arithmétique, spécifiquement un matériel multiplicateur, et les procédés d'utilisation de celui-ci pour exécuter des opérations de multiplication ou de multiplication-accumulation (et les opérations associées d'élévation au carré) impliquant au moins un opérande de plusieurs mots qui est plus large que le matériel multiplicateur. L'invention concerne en particulier la commande matérielle de la séquence de multiplication pour exécuter de telles opérations à plusieurs mots d'une manière efficace, où le procédé est caractérisé par l'ordre particulier dans lequel sont traités les mots des opérandes. Le matériel de multiplication a nécessairement une taille finie, typiquement définie comme ayant une paire d'entrée d'opérandes à mot unique et une sortie résultats en deux mots. Afin d'exécuter des opérations de multiplication-accumulation, la sortie du multiplicateur est normalement reliée à un circuit accumulateur, qui à au moins une largeur de deux mots plus un bit. (Le bit supplémentaire peut faire partie du résultat ou simplement être présent en tant qu'information de REPORT indiquant soit un dépassement par valeurs supérieures dans le cas d'une addition ou d'un dépassement par valeurs inférieures dans le cas de soustraction dans la partie accumulation de l'opération. ) L'opération de base est donc R = Z XY. Pour une multiplication simple, R = XY, l'entrée accumulateur Z = 0. Pour les opérations d'élévation au carré, X = Y. L'opération de base est habituellement conçue pour exécuter une arithmétique d'entiers standard, mais le matériel de multiplication qui exécute l'arithmétique polynomiale existe également, notamment pour utiliser les applications cryptographiques. En cryptographie et dans un certain nombre d'autres applications, on a besoin de multiplier de très gros nombres entiers comprenant un grand nombre de mots. Pour effectuer ces opérations à l'aide d'opérandes qui sont beaucoup plus larges que le matériel de multiplication, les opérandes doivent être découpés en une pluralité de segments à mot unique et introduits dans le matériel dans une certaine séquence spécifiée. Ces segments font l'objet d'opérations et les résultats intermédiaires sont accumulés de sorte que le produit final est calculé comme la somme de produits croisés de poids divers. Les segments d'opérande ayant la largeur d'un mot, ainsi que les résultats partiels, sont enregistrés dans une mémoire qui est adressée par le séquenceur d'opérations du matériel multiplicateur. Une séquence type conserve un segment d'opérandes constant tandis que d'autres segments d'opérande sont analysés mot par mot pour être introduits dans le multiplicateur ; ensuite le premier opérande incrémente au segment large d'un mot suivant et l'analyse du deuxième opérande est répétée. Si X = #i xiwi, Y = #j yjwj, et Z = #k xkwk, avec w = 2n, alors R = Ek rkwk = Z XY = #k zkwk #i#j (xiyj) wi+j, où i+j = k, et où n est la taille du mot en bits. Ainsi, dans une séquence d'opérations typique, les mots yj sont passés sur tous les j pour un mot fixe xi, puis i est incrémenté d'une unité et le cycle de mots yi est répété pour le nouveau xi. Tandis que la nouvelle séquence décrite ci-dessus est directe, facile à programmer et donne le résultat correct, chaque étape ou cycle nécessite une moyenne de trois accès de la mémoire à accès direct. En particulier, chaque étape nécessite que yj et Zk soient extraits de la mémoire, et qu'un résultat partiel rk soit réécrit en mémoire. Un objet de l'invention est de proposer une séquence de multiplication à plusieurs mots efficace pour les opérations à grands entiers, qui nécessite en moyenne un seul accès mémoire par multiplication. L'objet est réalisé par un procédé qui traite la séquence de multiplication en groupes de deux poids-mot de résultat (appelés colonnes). Dans un groupe de paires de colonnes, la séquence procède par colonnes alternantes avec des poids de segment d'opérande augmentant constamment (ou diminuant constamment) (qualifiés de modèle en zigzag), de sorte que l'un des segments provenant d'un cycle de multiplication précédent est aussi utilisé dans le présent cycle de multiplication, et, sauf éventuellement pour le premier cycle de multiplication dans un groupe donné, seul un des segments d'opérande doit être extrait de la mémoire dans un cycle de multiplication quelconque pour ce groupe. Des additions de produits partiels de mêmes poids de résultats sont exécutées dans une opération accumulée qui est transmise avec l'opération de multiplication. Des segments de deux mots d'un paramètre accumulé séparé peuvent aussi être ajoutés au début ou à la fin d'une séquence d'opérations accumulées du groupe correspondant. Un module de multiplication accumulation (MAC) exécute les cycles de multiplication et d'accumulation comme ordonné par un séquenceur d'opérations préprogrammée dans le logiciel interne dans le matériel de multiplication, avec lectures des segments d'opérande depuis la mémoire à accès direct (RAM) transférées au module MAC par le biais de registres internes au matériel de multiplication. De même, les écritures des résultats intermédiaires et finaux sont ramenés dans le registre interne pour segments de paramètres accumulés et finalement retournés dans la RAM. Une autre amélioration ajoute des registres de mémoire cache internes pour contenir les segments de paramètres fréquemment utilisés qui reviennent au début ou à la fin de chaque groupe de cycle de multiplication. L'invention a un avantage sur les séquences de multiplication précédentes en ce qu'elle adapte largement les exigences des multiplicateurs pour les segments de paramètre à la largeur de bande d'accès mémoire d'une lecture et d'une écriture par cycle de multiplication, de sorte qu'une multiplication globale de grands entiers de plusieurs mots est exécutée efficacement en un minimum de cycles. L'opération de multiplication peut aussi être étendue sur plusieurs cycles (en utilisant le traitement "pipeline"), auquel cas on considère encore que, en moyenne, une multiplication est exécutée par cycle, puisqu'un résultat de multiplication est disponible par cycle et puisqu'une nouvelle opération de multiplication peut être lancée par cycle. Ainsi, l'invention concerne un procédé de fonctionnement d'un circuit de multiplication pour calculer le produit de deux opérandes (X et Y) dont au moins un d'eaux est sensiblement plus large que le circuit de multiplication, le circuit de multiplication ayant une paire d'entrées d'opérandes d'une largeur de deux mots et une sortie résultat d'une largeur de deux mots, où un mot est un nombre spécifié de bits, chacun des opérandes composé d'une pluralité de segments d'opérande contigus d'une largeur de mot ordonnée (Xk et ym), caractérisés par des poids spécifiques (k et m), le circuit de multiplication ayant accès à une mémoire, le procédé comprenant les étapes consistant à : charger des segments d'opérandes d'une largeur d'un mot des deux opérandes dans un ordre spécifié à partir de la mémoire dans le circuit de multiplication, le circuit de multiplication comprenant au moins deux registres (RX et RY) ayant accès à ladite mémoire pour contenir temporairement les segments chargés ; - multiplier les segments chargés pour obtenir des produits intermédiaires d'une largeur de deux mots, les produits intermédiaires ayant un poids égal à la somme des poids des segments chargés ; ajouter des produits intermédiaires du même poids dans un accumulateur, l'accumulateur ayant une taille de trois mots plus un nombre de bits de report, suffisante pour gérer une taille d'opérande maximale spécifiée, l'accumulateur connecté à un registre d'entrée de deux mots (RZ) pour contenir temporairement tout produit d'un poids spécifique ajouté précédemment et un registre de sortie à deux mots (RR) pour contenir les résultats d'une étape d'addition, lesdits registres (RZ et RR) ayant accès à ladite mémoire ; et - enregistrer les résultats accumulés depuis ledit registre de sortie (RR) de nouveau dans ladite mémoire au moins après accumulation de tous les produits intermédiaires du poids spécifié ; dans lequel l'ordre spécifié pour les segments d'opérande de chargement dans lesdits registres est une séquence définie par les poids des produits intermédiaires résultants, dans lequel l'étape de multiplication est faite par groupes successifs de deux poids de produits adjacents, avec la séquence à l'intérieur d'un groupe sélectionnée de sorte que, à l'exception d'une première opération de multiplication dans un groupe donné, au plus un des segments d'opérande doive être lu de la mémoire et placé dans un registre (RX ou RY), l'autre segment d'opérande étant déjà enregistré dans l'autre registre (RY ou RX) à partir de l'opération de multiplication immédiatement précédente. Avantageusement, le registre d'entrée de l'accumulateur (RZ) sera chargé avec un segment d'un mot accumulé (Z), où le segment est du même poids que les produits intermédiaires à former dans ladite étape de multiplication, moyennant quoi le procédé de fonctionnement exécute une opération de multiplicationaccumulation sur une paire d'opérandes de multiplication et un opérande d'accumulation. De préférence, la séquence se déroulera à l'intérieur d'un groupe dans un modèle en zigzag de poids de segments d'opérande augmentant constamment. Avantageusement, la séquence se déroulera à l'intérieur d'un groupe dans un modèle en zigzag de poids de segments d'opérande diminuant constamment. De préférence, le circuit de multiplication contiendra en outre un ensemble de registre de mémoire cache interne, lesdits registres de mémoire cache étant chargés depuis la mémoire avec des segments d'opérande qui sont fréquemment utilisés dans une opération de multiplication. Avantageusement, la séquence se déroulera à l'intérieur d'un groupe commençant par une opération de multiplication avec au moins un segment d'opérande enregistré dans un registre de mémoire cache dans une première direction en zigzag de poids de segments d'opérande augmentant ou diminuant constamment, puis passe directement à une opération de multiplication du groupe pas encore exécutée qui a aussi au moins un segment d'opérande enregistré dans un registre de mémoire cache et continue dans une deuxième direction en zigzag de poids de segments d'opérande diminuant ou augmentant constamment jusqu'à ce que toutes les opérations de multiplication pour ce groupe soient terminées. De préférence, l'ordre spécifié sera préprogrammé dans le logiciel interne dans un séquenceur d'opérations du circuit de multiplication, avec des longueurs de mot d'opérande incluses en tant que paramètre d'entrée pour une commande de multiplication. L'invention se rapporte également à un circuit de multiplication, comprenant : un module de multiplication-accumulation (MAC) comprenant un ensemble multiplicateur qui introduit des segments d'opérandes récepteur à mot unique à multiplier pour former un produit intermédiaire de deux mots, et comprenant aussi un circuit accumulateur avec une première entrée de deux mots pour recevoir des produits intermédiaires provenant du multiplicateur, une deuxième entrée de deux mots pour recevoir une valeur accumulée, et une sortie de trois mots plus un certain nombre de bits de report suffisant pour gérer une taille d'opérande maximum spécifiée pour proposer une somme de valeurs d'entrée provenant des entrées de deux mots, la sortie de l'accumulateur retournant aussi deux mots à la deuxième entrée de deux mots ; un ensemble de registres d'adresses internes pour adresser une mémoire à accès direct ; un ensemble de registres de données internes (RX, RY, RZ, RR) connectés pour recevoir et transmettre des segments desdites opérandes depuis et à destination de ladite mémoire et aussi connectés audit ensemble multiplicateur et audit accumulateur de manière à fournir des segments d' opérande aux entrées de ceux-ci et à en recevoir des résultats, chacun desdits segments d'opérande ayant un poids spécifié ; et un séquenceur d'opérations pour contrôler l'accès à la mémoire par lesdits adresse interne et registres de données et contrôler la séquence d'opérations de multiplication et d'accumulation par lesdits ensemble multiplicateur et accumulateur respectifs, dans lequel ladite séquence est définie par les poids des produits résultants égaux à la somme des poids des segments d'opérande en cours de multiplication, dans lequel les opérations de multiplication sont faites dans des groupes successifs de deux poids de produits adjacents, avec la séquence dans un groupe sélectionné de sorte que, excepté une première opération de multiplication dans un groupe donné, au maximum un des segments d' opérande doive être lu de la mémoire dans un registre (RX ou RY), l'autre segment d'opérande étant déjà enregistré dans l'autre registre (RY ou RX) depuis l'opération de multiplication immédiatement précédente. Un mode d'exécution de l'invention sera décrit ciaprès, à titre d'exemple non limitatif, avec référence aux figures annexées dans lesquelles : La Figure 1 est une vue en projection horizontale schématique de l'architecture principale d'un système de traitement qui comprend un moteur de multiplication de la présente invention. La Figure 2 est un diagramme d'interface représentant les registres et l'interface mémoire pour un moteur de multiplication typique selon la présente invention. La figure 3 est une vue en projection horizontale schématique détaillée d'un module MAC dans le moteur de multiplication de la figure 1. La figure 4 est un tableau de plusieurs multiplications et additions mot par mot établie par opérande et par poids de résultat servant à illustrer la séquence d'opération selon la présente invention. Les figures 5a, 5b et 5c sont un tableau montrant une séquence d'opérations pour un mode de réalisation de multiplication de la présente invention, utilisant un ensemble additionnel de 5 registres de mémoire cache stockant des segments d'opérande fréquemment utilisés. La figure 6 est un tableau de plusieurs multiplications et additions mot par mot disposées comme sur la figure 4 par opérande et par poids de résultat pour une opération de multiplication-accumulation "rectangulaire" exemplaire avec des opérandes de différentes tailles. Les figures 7a, 7b et 7c sont un tableau montrant un autre exemple d'une séquence d'opération correspondant aux exemples de la figure 6, dans ce cas avec un ensemble de 7 registres de mémoire cache dans le matériel. Avec référence à la figure 1, l'architecture principale d'un système de traitement est vu pour inclure un processeur central principal 11 et un moteur multiplicateur 13 partageant une mémoire à accès direct ou RAM 15 et une mémoire cache à registres de commande de multiplicateur 17. Le moteur multiplicateur 13 comprend un module de multiplication accumulation (MAC) 21, un séquenceur d'opérations 23 connecté pour envoyer des signaux de commande au MAC 21, des registres de commande 25 et des registres de données internes 27. Des modules de gestion de mémoire/protection de mémoire (MMU/MPU) 14 et 19 assurent l'interface de la RAM 15 et de la mémoire cache 17 avec le processeur 11 et le moteur multiplicateur 13. Dans notre configuration préférée, il y a un MMU/MPU pour le processeur central 11 concernant à la fois les accès à la RAM et aux périphériques (afin de contrôler/limiter les accès à certaines zones/périphériques). Ici, le moteur multiplicateur 13 est considéré comme un périphérique. Comme le moteur multiplicateur a un accès direct à la RAM 15, il pourrait être un moyen pour l'utilisateur de surmonter les limitations d'accès spécifiées dans le MMU/MPU côté noyau 19. Par conséquent, nous proposons un autre MMU/MPU 14 pour contrôler les accès à la mémoire par le moteur multiplicateur 13. Les deux modules MMU/MPU 14 et 19 doivent être configurés de manière cohérente, mais il n'y a aucun lien entre eux et leur fonctionnement est indépendant. Le moteur multiplicateur 13 n'a généralement pas de ROM dédiée, mais il est configuré et paramétré par le processeur central 11. Les registres de commande 25 sont connectés à la mémoire cache des registres de commande 17 desquels ils reçoivent des instructions provenant du processeur central 11. Les registres de commande 25 transmettent les paramètres d'instruction et des informations d'état au séquenceur d'opérations 23, et communiquent aussi avec le module MAC 21, par exemple pour sélectionner le mode MAC (arithmétique standard ou arithmétique polynomiale) pour ces modules MAC qui peuvent être capables des deux types d'arithmétique, pour sélectionner une opération MAC à mot unique ou à mots multiples, et pour communiquer n'importe quelle valeur de report depuis une opération MAC en cours ou précédente. Les registres d'adresses ou de données internes 27 sont reliées à la RAM partagée 15 pour recevoir et émettre des paramètres d'opérande d'une opération MAC. Le séquenceur d'opération 23 est de préférence préprogrammé par logiciel interne (firmware) selon l'invention décrite ici. Le séquenceur d'opérations 23 envoie des instructions et des adresses aux registres internes 27 et de là à la RAM partagée 15 pour diriger le chargement de segments d'opérandes d'une largeur d'un mot dans un ordre spécifié selon la présente invention. L'architecture est typiquement construite de sorte que, lorsque le moteur multiplicateur 13 fonctionne, il a un accès privilégié à une partie spécifique de la RAM partagée 15. Cela permet au processeur central 11 d'accéder encore à d'autres parties de la RAM 15 pendant un calcul. En variante, l'accès à la RAM partagée 15 pourrait être entièrement dédié au moteur multiplicateur 13 pendant un calcul et accessible au processeur central 11 uniquement lorsque le multiplicateur 13 ne l'utilise pas. Le module MAC 21 peut être basé sur une taille de mot de 32 bits. Dans ce cas, les longueurs d'opérande sont toujours des multiples de 4 octets et les opérandes sont alignés sur des limites de mot de 32 bits avec des zéros d'en-tête si nécessaire. Ce choix facilite les calculs d'adresses pour la RAM partagée 15 puisque le processeur 11 travaille typiquement sur des adresses en octets. Le module MAC 21 aurait une paire d'entrées d'opérandes X et Y (de largeur de mot) de 32 bits pour l'ensemble multiplicateur, une entrée d'accumulateur Z d'une largeur de deux mots, une sortie de résultats de multiplicateur d'une largeur de deux mots qui forme une seconde entrée d'accumulateur, et une sortie d'accumulateur R d'une largeur de deux mots. Bien que le module MAC 21 ne fonctionne que sur des entrées X et Y d'une largeur d'un mot, le moteur multiplicateur 13 général, y compris le séquenceur d'opérations programmées 23, peut être considéré comme un multiplicateur de grands entiers (de plusieurs mots). Il prend en charge les opérations de multiplication efficaces telles que multiplication-accumulation de nombres à N mots, élévation au carré-accumulation de nombres de N mots (entrée multiplication Y = X), multiplication ou élévation au carré de nombres à N mots sans accumulation (entrée accumulateur Z = 0), multiplication-accumulation d'un nombre de N mots par une constante A de 1 mot (et même d'1 octet). Avec référence à la figure 2, l'interaction entre le moteur multiplicateur 13 avec ses divers registres et mémoires cache et avec la RAM partagée 15 est illustrée par un diagramme d'interface. La RAM 15 enregistre les paramètres X, Y, Z et R à des blocs d'adresse spécifiques qu'il faut pointer pour y accéder. Les mots des opérandes sont toujours enregistrés bit de moindre poids en premier dans la RAM, à commencer par une adresse de base. Pour demander un paramètre, ou un mot de segment d'opérande spécifique, le registre d'adresse correspondant X ADDR, Y ADDR, Z ADDR ou R ADDR (certains des registres internes 27 sur la figure 1) doit être chargé avec l'adresse associée. Les mots adressés sont ensuite chargés vers et depuis le registre de données correspondant RX, RY, RZ et RR (plus des registres internes 27 sur la figure 1 utilisés par le module MAC 21). Les registres 25 incluent typiquement un ou plusieurs registres d'opérations pour spécifier une opération désirée à exécuter (multiplication, multiplication-accumulation, multiplication-soustraction, multiplication par une constante d'un seul mot, élévation au carré, etc. ), un ou plusieurs registres spécifiant diverses options (mode naturel ou polynomial, opération entière ou tronquée, report ou entrée de report, etc.) ainsi qu'indications des longueurs d'opérande, et un ou plusieurs registres indiquant diverses conditions (occupé/inactif, un résultat de dépassement par valeurs supérieures/dépassement par valeurs inférieures/zéro, conditions d'erreur, etc.). Avec référence à la figure 3, le module MAC 21 de la figure 1 est constitué d'un ensemble multiplicateur de nombres entiers 31 recevant des opérandes à mot unique ou plus généralement des segments de mot à mot unique d'opérandes plus grandes de plusieurs mots via des registres de données RX et RY chargés de la RAM partagée. L'ensemble multiplicateur 31 envoie un résultat à deux mots multipliant les mots d'entrée vers un accumulateur 33. L'accumulateur a une taille de trois mots (= 96 bits) plus un certain nombre de bits de report suffisant pour gérer une taille d'opérande maximum spécifiée. Par exemple, pour les opérandes de 512 mots, la colonne la plus longue a 512 lignes de produits intermédiaires à ajouter, nécessitant ainsi un espace de 9 bits pour la somme de report. Cela donne une largeur d'accumulateur totale de 105 bits pour cet exemple. L'accumulateur 33 reçoit aussi un paramètre d'entrée à deux mots provenant du registre de données RZ, et envoie un résultat à un registre de données de résultat RR. Un retour à deux mots peut être proposé depuis la sortie de l'accumulateur ou du registre de données RR à destination du registre d'opérandes d'accumulation pour permettre au segment d'opérande accumulé d'être mis à jour avant que le résultat final dans le registre RR ne soit écrit de nouveau dans la RAM. Une taille typique pour le module de multiplication accumulation (MAC) gère des mots de 32 bits, avec des entrées d'opérande de 32 bits provenant des registres RX et RY à destination de l'ensemble multiplicateur, et avec une sortie d'ensemble multiplicateur d'opérandes de 64 bits, et des entrées et sorties d'accumulateur vers et depuis des registres RZ et RR. Soit A représentant un opérande d'un seul mot ou un segment d'opérande X de plusieurs mots qui est chargé dans l'ensemble multiplicateur 31 depuis le registre de données RX, et B représentant un segment d'un seul mot d'un opérande de plusieurs mots Y qui est chargé dans l'ensemble multiplicateur 31 depuis le registre de données RY, puis A = #i ai2i, B = #j bj2j, où ai et bj sont les bits individuels de l'opérande ou du segment, et où i et j sont compris entre 0 et 31. Pour une multiplication sur le champ d'entier zp, AB = #i#j aibj2i+j. Pour une multiplication au-dessus du champ de Galois GF(2n), l' addition de deux bits est réduite modulo 2 de sorte que AB = #k=02n-2(2k##i+j=k (arbjmod 2)) Il peut aussi y avoir un terme "report dans" W qui est ajouté. Le traitement du report dépend des options indiquées par les registres 25 mentionnés ci-dessus. Notez aussi que le terme "report dans" W ne doit pas nécessairement avoir un rapport direct au terme de report sortant provenant d'un calcul immédiatement antérieur. Finalement, l'opération du champ de Galois a une influence sur le traitement du report en ce que l'ajout du terme "report dans" W vers le bit de moindre poids est aussi conduit modulo 2. Une multiplication grandeur nature d'opérandes de plusieurs mots X et Y implique une séquence des multiplications de mots uniques qui viennent d'être décrites. X et Y sont respectivement des nombres de N mots et de M mots. L'opération générale est R = [Z] ((X'Y) + W). Ceci peut être écrit sous forme de somme de produits comme : R = [#k=0N+M-1Zkbk] ~ (#i=0N-1(#j=0M-1(XiYjbi+j)) + W). Cette formule est valide à la fois pour les opérations Zp et GF ( 2n) , et b = 232.L'accumulateur de reports de trois mots et plus peut calculer Acc := Acc (Xi-Yj) ou Acc : = Acc ~(Xi#Yj#232), si nécessaire . L' invention réside dans l'ordre particulier dans lequel les multiplications à un seul mot se déroulent. Séquence d'opérations En référence à la figure 4, le tableau montre une disposition d'opérations de multiplication mot par mot des premiers segments d'opérande BO-B7 de l'opérande à plusieurs mots Y. À titre d'illustration, les deux opérandes X et Y ont une largeur de B mots, mais ce ne doit pas nécessairement être le cas. Pour obtenir les mots de résultat RO ... R15, il faudra éventuellement ajouter les divers produits partiels verticalement ensemble avec les mots d'accumulation correspondants CO... C15 de l' opérande Z. Dans l' ordre des accès à la mémoire, le chargement des segments d'opérandes, leur multiplication respective, et l'ajout aux segments d'accumulation, sont organisés en doubles colonnes de poids de résultat adjacents. Chaque groupe de deux colonnes est traité en partant soit du haut soit du bas et en progressant ligne par ligne en zigzag. Aussi, les groupes adjacents de paires de colonnes ne doivent pas nécessairement progresser dans la même direction. Ainsi, sur la figure 4, la séquence de multiplication pourrait aller ainsi : A1B0, AOBO, AOB1 ; AOB3, AOB2, A1B2, A1B1, A3B1, A2BO, A3BO, A5BO, A4BO, A4B1, A3B1, A3B2, A2B2, A2B3, A1B3, A1B4, AOB4, AOB5 ; AOB7, AOB6, A1B6, A1B5, A2B5, A2B4, A3B4, A3B3, A4B3, A4B2, A5B2, A5B1, A6B1, A6BO, A7BO ; A7B1, A7B2, A6B2, A6B3, A5B3, A5B4, A4B4, A4B5, A3B5, A3B6, A2B6, A2B7, A1B7 ; A3B7, A4B7, A4B6, A5B6, A5B5, A6B5, A6B4, A7B4, A7B3, A7B5, A7B6, A6B6, A6B7, A5B7 ; A7B7. Des points-virgules séparent les différents groupes de paires de colonnes dans la liste de séquence. Dans cet exemple particulier, des groupes successifs progressent dans des directions opposées (de haut en bas, puis de bas en haut, puis de haut en bas à nouveau, etc. ) Notez que seul un opérande a besoin d'être lu avant que l'ensemble puisse exécuter la multiplication suivante, car un opérande est déjà en place depuis la multiplication suivante. Si des groupes successifs de paires de colonnes progressent toujours dans la même direction, alors un certain nombre de registres de mémoire cache peut être fourni pour enregistrer certains segments d'opérande fréquemment utilisés nécessaires pour éviter deux lectures avant la première plusieurs multiplie au début de chaque groupe. Dans ce cas, cinq mémoires cache enregistreront AO, Al, BO, Bl et B2 pendant la moitié ascendante de la séquence de multiplication. La moitié droite de la figure 4, lorsque chaque groupe successif deviendra plus long. Les figures 5a, 5b et 5c illustrent l'intérêt d'avoir de telles mémoires cache, en montrant une séquence de multiplication pour ce mode de réalisation de l'invention. La première colonne représente les accès de lecture de la RAM, la deuxième colonne représente des opérations de l'ensemble multiplicateur, et les cinq colonnes les plus à droite montrent le contenu des cinq mémoires cache pendant chaque cycle de multiplication. Pour une multiplication de 8 mots par 8 mots avec 5 mémoires cache, il y a 64 cycles de multiplication, 7 cycles de chargement de mémoire cache uniquement, 5 cycles de lecture d'autres mémoires, plus 3 cycles à la fin pour terminer pour un total de seulement 79 cycles. L'avantage par rapport aux séquences précédentes est encore plus évident quand on multiplie des nombres entiers plus grands courants dans les applications cryptographiques (par exemple, 1024 mots par 1024 bits). La taille en mots de chaque opérande peut être paire ou impaire, et ne doit pas nécessairement être la même pour les deux opérandes. Le cas présenté est souvent qualifié d'opération de "multiplication rectangulaire". Un exemple d'opération de multiplication et d' accumulation rectangulaire où un des opérandes X a un nombre impair de mots (5) et l'autre opérande de multiplication Y a un nombre pair de mots (14), et où l'opérande d'accumulation Z et le résultat R ont un nombre impair de mots (19) est présenté dans les figures 6,7a, 7b et 7c à titre d'illustration. Dans cet exemple, il y a aussi 7 registres de mémoire cache internes pour enregistrer les segments de paramètre fréquemment utilisés. Seule une partie de la séquence totale est montrée, pour les groupes RO-R1, R2-R3, R4-R5, R6-R7,... (R9 à Rll omis), R12-R13, R14-R15, et R16-R17. Dans les groupes, le modèle de multiplication encore une fois est arrangé de sorte que au plus un accès de lecture de la RAM et un accès d'écriture dans la RAM sont requis. La première colonne indique l'adresse RAM spécifique qui est appliquée et accédée dans des cycles successifs. Les écritures dans la RAM sont représentées avec des bordures en gras. La deuxième et la troisième colonnes montrent les opérations exécutées par l'ensemble multiplicateur et l'accumulateur, respectivement. Les sept colonnes les plus à droite montrent le contenu des registres de mémoire cache internes utilisés par l'ensemble multiplicateur et l'accumulateur. Cet exemple montre également que la séquence de multiplication ne doit pas nécessairement descendre strictement en zigzag de haut en bas ou remonter en zigzag de bas en haut sur tout un groupe de paires de colonnes. Au contraire, les débuts et/ou les fins de telles séquences en zigzag peuvent être déplacés et même évoluer dans une direction opposée par rapport à la première partie d'une séquence de groupe, parce que les paramètres nécessaires sont disponibles dans les mémoires cache. Ainsi, dans le premier groupe RO-R1, l'ordre peut être YOXO, YOX1, YlXO, au lieu de YOXO, Y1X0, YOX1 pour une séquence strictement descendante, ou au lieu de YOX1, YOXO, Y1X0 pour une séquence strictement ascendante. Dans les deuxième, troisième et quatrième groupes, la séquence commence au milieu à Y1X1, Y3X1 et Y5X1 respectivement, descend en zigzag jusqu'en bas, puis remonte directement jusqu'à Y2X1, Y4X1 et Y6X1 respectivement et se termine en zigzag ascendant jusqu'en haut. Cela est possible parce que le segment d'opérande Xl est enregistré dans la mémoire cache interne, de sorte qu'une seule autre lecture suffit malgré le saut de YOX3 à Y2X1, de YOX4 à Y4X1, et de Y2X4 à Y6X1 respectivement au milieu de la séquence. Cela est aussi valable pour l'un quelconque des groupes omis dans les figures 7a-7c et pour le groupe R12-R13. Dans le groupe R14-R15, la séquence commence en haut et descend strictement en zigzag jusqu'à Y12X3, puis saute à Y10X4 et se termine en zigzag ascendant avec Y11X4 et Y11X3. Ce saut et changement de direction dans la séquence est permis parce que le paramètre X4 est déjà disponible dans un registre de la mémoire cache. Le groupe de multiplication final R16-R17 est représenté dans un modèle en zigzag strictement descendant, mais peut se dérouler dans n'importe quel ordre parce que les segments d'opérande X3 et X4 sont disponibles dans des registres de la mémoire cache. Les opérations d'élévation au carré et les opérations d'élévations au carré-accumulation se déroulent de la même manière que l'un quelconque des exemples précédents, sauf que les opérandes X et Y sont identiques. Cependant, comme les segments spécifiques de X et Y ne sont généralement pas les mêmes dans un cycle de multiplication particulier quelconque, les opérations d'élévation au carré peuvent être traitées tout comme n'importe quelle autre opération de multiplication dans laquelle les opérandes X et Y diffèrent. REVENDICATIONS 1. Procédé de fonctionnement d'un circuit de multiplication pour calculer le produit de deux opérandes (X et Y) dont au moins un d'eaux est sensiblement plus large que le circuit de multiplication, le circuit de multiplication ayant une paire d'entrées d'opérandes d'une largeur de deux mots et une sortie résultat d'une largeur de deux mots, où un mot est un nombre spécifié de bits, chacun des opérandes composé d'une pluralité de segments d'opérande contigus d'une largeur de mot ordonnée (Xk et ym), caractérisés par des poids spécifiques (k et m), le circuit de multiplication ayant accès à une mémoire, le procédé comprenant les étapes consistant à : charger des segments d'opérandes d'une largeur d'un mot des deux opérandes dans un ordre spécifié à partir de la mémoire dans le circuit de multiplication, le circuit de multiplication comprenant au moins deux registres (RX et RY) ayant accès à ladite mémoire pour contenir temporairement les segments chargés ; multiplier les segments chargés pour obtenir des produits intermédiaires d'une largeur de deux mots, les produits intermédiaires ayant un poids égal à la somme des poids des segments chargés ; ajouter des produits intermédiaires du même poids dans un accumulateur (33), l'accumulateur ayant une taille de trois mots plus un nombre de bits de report, suffisante pour gérer une taille d'opérande maximale spécifiée, l'accumulateur connecté à un registre d'entrée de deux mots (RZ) pour contenir temporairement tout produit d'un poids spécifique ajouté précédemment et un registre de sortie à deux mots (RR) pour contenir les résultats d'une étape d'addition, lesdits registres (RZ et RR) ayant accès à ladite mémoire ; et enregistrer les résultats accumulés depuis ledit registre de sortie (RR) de nouveau dans ladite mémoire au moins après accumulation de tous les produits intermédiaires du poids spécifié ; dans lequel l'ordre spécifié pour les segments d'opérande de chargement dans lesdits registres est une séquence définie par les poids des produits intermédiaires résultants, dans lequel l'étape de multiplication est faite par groupes successifs de deux poids de produits adjacents, avec la séquence à l'intérieur d'un groupe sélectionnée de sorte que, à l'exception d'une première opération de multiplication dans un groupe donné, au plus un des segments d'opérande doive être lu de la mémoire et placé dans un registre (RX ou RY), l'autre segment d'opérande étant déjà enregistré dans l'autre registre (RY ou RX) à partir de l'opération de multiplication immédiatement précédente. 2. Procédé de la revendication 1, dans lequel le registre d'entrée de l'accumulateur (RZ) est chargé avec un segment d'un mot accumulé (Z), où le segment est du même poids que les produits intermédiaires à former dans ladite étape de multiplication, moyennant quoi le procédé de fonctionnement exécute une opération de multiplication-accumulation sur une paire d'opérandes de multiplication et un opérande d'accumulation. 3. Procédé de la revendication 1, dans lequel la séquence se déroule à l'intérieur d'un groupe dans un modèle en zigzag de poids de segments d'opérande augmentant constamment. 4. Procédé de la revendication 1, dans lequel la séquence se déroule à l'intérieur d'un groupe dans un modèle en zigzag de poids de segments d'opérande diminuant constamment. 5. Procédé de la revendication 1, dans lequel le circuit de multiplication contient en outre un ensemble de registre de mémoire cache interne, lesdits registres de mémoire cache (17) étant chargés depuis la mémoire avec des segments d'opérande qui sont fréquemment utilisés dans une opération de multiplication. 6. Procédé de la revendication 1, dans lequel la séquence se déroule à l'intérieur d'un groupe commençant par une opération de multiplication avec au moins un segment d'opérande enregistré dans un registre de mémoire cache (17) dans une première direction en zigzag de poids de segments d'opérande augmentant ou diminuant constamment, puis passe directement à une opération de multiplication du groupe pas encore exécutée qui a aussi au moins un segment d'opérande enregistré dans un registre de mémoire cache et continue dans une deuxième direction en zigzag de poids de segments d'opérande diminuant ou augmentant constamment jusqu'à ce que toutes les opérations de multiplication pour ce groupe soient terminées. 7. Procédé de la revendication 1, dans lequel l'ordre spécifié est préprogrammé dans le logiciel interne dans un séquenceur d'opérations du circuit de multiplication, avec des longueurs de mot d'opérande incluses en tant que paramètre d'entrée pour une commande de multiplication. 8. Circuit de multiplication, comprenant : un module de multiplication-accumulation (MAC) (21) comprenant un ensemble multiplicateur qui introduit des segments d'opérandes récepteur à mot unique à multiplier pour former un produit intermédiaire de deux mots, et comprenant aussi un circuit accumulateur avec une première entrée de deux mots pour recevoir des produits intermédiaires provenant du multiplicateur, une deuxième entrée de deux mots pour recevoir une valeur accumulée, et une sortie de trois mots plus un certain nombre de bits de report suffisant pour gérer une taille d'opérande maximum spécifiée pour proposer une somme de valeurs d'entrée provenant des entrées de deux mots, la sortie de l'accumulateur retournant aussi deux mots à la deuxième entrée de deux mots ; un ensemble de registres d'adresses internes pour adresser une mémoire à accès direct ; un ensemble de registres de données internes (RX, RY, RZ, RR) connectés pour recevoir et transmettre des segments desdites opérandes depuis et à destination de ladite mémoire et aussi connectés audit ensemble multiplicateur et audit accumulateur de manière à fournir des segments d'opérande aux entrées de ceux-ci et à en recevoir des résultats, chacun desdits segments d'opérande ayant un poids spécifié ; et un séquenceur d'opérations pour contrôler l'accès à la mémoire par lesdits adresse interne et registres de données et contrôler la séquence d'opérations de multiplication et d'accumulation par lesdits ensemble multiplicateur et accumulateur respectifs, dans lequel ladite séquence est définie par les poids des produits résultants égaux à la somme des poids des segments d'opérande en cours de multiplication, dans lequel les opérations de multiplication sont faites dans des groupes successifs de deux poids de produits adjacents, avec la séquence dans un groupe sélectionné de sorte que, excepté une première opération de multiplication dans un groupe donné, au maximum un des segments d' opérande doive être lu de la mémoire dans un registre (RX ou RY), l'autre segment d'opérande étant déjà enregistré dans l'autre registre (RY ou RX) depuis l'opération de multiplication immédiatement précédente.