[go: up one dir, main page]

FR2867579A1 - Multiplieur modulaire de montgomery - Google Patents

Multiplieur modulaire de montgomery Download PDF

Info

Publication number
FR2867579A1
FR2867579A1 FR0502052A FR0502052A FR2867579A1 FR 2867579 A1 FR2867579 A1 FR 2867579A1 FR 0502052 A FR0502052 A FR 0502052A FR 0502052 A FR0502052 A FR 0502052A FR 2867579 A1 FR2867579 A1 FR 2867579A1
Authority
FR
France
Prior art keywords
multiplier
bit
multiplicand
bits
register
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
FR0502052A
Other languages
English (en)
Other versions
FR2867579B1 (fr
Inventor
Hee Kwan Son
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Samsung Electronics Co Ltd
Original Assignee
Samsung Electronics Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Samsung Electronics Co Ltd filed Critical Samsung Electronics Co Ltd
Publication of FR2867579A1 publication Critical patent/FR2867579A1/fr
Application granted granted Critical
Publication of FR2867579B1 publication Critical patent/FR2867579B1/fr
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/52—Multiplying; Dividing
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
    • G06F7/728—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic using Montgomery reduction
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/52—Multiplying; Dividing
    • G06F7/523—Multiplying only
    • G06F7/533—Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even
    • G06F7/5334—Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even by using multiple bit scanning, i.e. by decoding groups of successive multiplier bits in order to select an appropriate precalculated multiple of the multiplicand as a partial product
    • G06F7/5336—Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even by using multiple bit scanning, i.e. by decoding groups of successive multiplier bits in order to select an appropriate precalculated multiple of the multiplicand as a partial product overlapped, i.e. with successive bitgroups sharing one or more bits being recoded into signed digit representation, e.g. using the Modified Booth Algorithm

Landscapes

  • Physics & Mathematics (AREA)
  • Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Computational Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Computing Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Mathematical Physics (AREA)
  • Complex Calculations (AREA)
  • Executing Machine-Instructions (AREA)

Abstract

Dans un multiplieur de Montgomery, un générateur de produit modulo sélectionne un produit modulo parmi plusieurs modules à n bits sélectionnables, un module M donné comprenant une plage binaire étendue délivrée à l'instant courant, parmi des modules à n bits. Un générateur de produit partiel peut sélectionner un multiplicande parmi plusieurs multiplicandes à n bits sélectionnables en tant que produit partiel, un multiplicande donné comprenant une plage étendue de bits délivrés à l'instant courant parmi les multiplicandes à n bits. Un accumulateur peut accumuler le produit modulo et le produit partiel sélectionnés pour générer un résultat de multiplication. Le multiplieur de Montgomery peut faire partie d'une unité de calcul qui peut comporter une mémoire et un hôte, et peut effectuer un calcul de multiplication de Montgomery et un calcul de multiplication normal sur la base d'un état logique d'un signal de commande qui lui est délivré.

Description

La présente demande revendique priorité conformément à l'article 35 U.S.C.
119 sur la demande de brevet coréenne N 2004-13855 déposée le 2 Mars 2004 auprès de l'Office Coréen de la Propriété Intellectuelle (KIPO), dont le
contenu est cité ici dans sa totalité à titre de référence.
La présente invention concerne de façon générale le domaine des systèmes cryptographiques et plus précisément, un multiplieur modulaire de Montgomery pour de tels systèmes cryptographiques.
Dans des environnements de communication d'informations échangeant diverses données par l'intermédiaire de réseaux informatiques, de champs de communication fixes et/ou mobiles (sans fil), les systèmes cryptographiques (cryptosystèmes) sont de plus en plus considérés comme étant des dispositifs nécessaires pour assurer la sécurité des données. En particulier, il est nécessaire qu'un système de comptabilité électronique ou d'identification soit doté d'un système de sécurité des données utilisant des technologies de cryptage et/ou de décryptage. Les technologies cryptographiques peuvent être brièvement réparties en techniques utilisant une clé secrète (clé symétrique, clé privée ou clé commune) et une clé publique (clé asymétrique).
L'algorithme cryptographique du Système de Cryptage de Données (DES) proposé par le Département du Commerce des États Unis d'Amérique est un système de cryptage à clé secrète typique. Comme autres systèmes de cryptage typiques, on citera la Norme Gouvernementale (GOST) de l'ex-URSS, et l'algorithme de Cryptage Interne de Données (IDEA) utilisé en Suisse. Pour un système de cryptage à clé secrète, il est avantageux d'avoir un canal supplémentaire pour la sécurité étant donné que les partenaires s'échangeant des informations doivent partager la même clé secrète. Ces systèmes de cryptage du type à clé secrète nécessitent donc généralement le maintien à jour et la gestion de nombreuses clés secrètes par un utilisateur pour que l'utilisateur puisse transmettre des informations à de nombreux autres utilisateurs.
Un type de système de cryptage à clé publique utilise des clés de cryptage et de décryptage différentes les unes des autres qui peuvent rendre diffic=ile la détection d'une clé correspondante par l'utilisateur, malgré le fait que la personne connaisse l'une des deux clés. Dans le système de cryptage public, les informations sont brouillées ou désembrouillées au moyen d'une clé secrète et/ou d'une clé publique (les informations doivent être brouillées au moyen d'une clé privée et désembrouillées au moyen d'une clé publique, et inversement). Alors que le système de cryptage public peut être approprié dans la gestion des clés, comme il n'est pas nécessaire de disposer d'un canal supplémentaire pour le partage des clés, et peut assurer une sécurité améliorée des données par comparaison à un système de cryptage secret, un système de cryptage public est considéré comme ayant une capacité limitée à traiter des données à haut débit, étant donné que deux clés différentes doivent être générées et que des opérations mathématiques complexes doivent être effectuées pour régénérer les informations en utilisant les deux clés différentes.
Un système cryptographique évolué utilise un algorithme de Montgomery qui peut être plus avantageux pour mettre en oeuvre un algorithme cryptographique à clé publique à la fois dans des formes de réalisation matérielles et logicielles. Un système de cryptage utilisant un algorithme de Montgomery est capable de transformer une opération modulaire sur un nombre, qu'il est difficile de mettre en oeuvre au moyen d'un matériel, en une opération de décalage d'une multiplication et d'une addition simplifiées. L'algorithme de Montgomery utilise un processus de transformation d'opérande avant et après une étape de calcul de multiplication unique. Par conséquent, bien qu'un système de cryptage de type Montgomery puisse être plus lent que d'autres systèmes de multiplication modulaires dans un même domaine de multiplication, pour des applications exécutant des opérations de multiplication itératives, un système de cryptage de type Montgomery peut traiter des opérations cryptographiques plus rapidement que des algorithmes cryptographiques à base de clés publiques classiques en raison du fait qu'il n'est pas nécessaire d'utiliser une étape de transformation d'opérande lors de chaque cycle de traitement.
L'un des procédés permettant d'augmenter la vitesse de traitement pour la multiplication consiste à étendre le nombre de radicaux. Si la valeur d'un radical augmente, le nombre itératif d'accumulations dans un processus de multiplication donné décroît d'une quantité correspondante.
Cependant, l'augmentation du nombre de radicaux peut conduire à un cycle d'accumulation plus complexe du fait d'étapes de traitements supplémentaires, allongeant ainsi le temps de traitement. Par exemple, bien qu'il soit relativement simple de mettre en oeuvre sous forme matérielle un algorithme de calcul à radical-2, le nombre itératif de cycles d'accumulation est deux fois plus élevé que celui d'un algorithme de calcul à radical-4. Inversement, l'algorithme de calcul à radical-4 nécessite un temps de traitement plus long pour chaque cycle d'itérations et nécessite une architecture matérielle plus complexe par rapport aux exigences matérielles de l'algorithme de calcul à radical-2.
Un exemple de mode de réalisation de la présente invention concerne un multiplieur de Montgomery. Le multiplieur peut comporter un générateur de produit modulo sélectionnant l'un de plusieurs modules à n bits -M, 0, M, 2M, et un résultat de ligne précédente SI en tant que produit modulo, et un générateur de produit partiel sélectionnant un multiplicande parmi l'un des multiplicandes -2A, -A, 0, + A et +2A en tant que produit partiel. Un accumulateur du multiplieur peut être configuré pour empiler dans celui-ci le produit modulo sélectionné et le produit partiel. Dans un exemple, une unité de calcul de Montgomery peut comporter une mémoire, qui sert de système hôte stockant dans la mémoire un multiplicande A, un multiplicateur B, un module M, ainsi que le multiplieur de Montgomery mentionné précédemment. Le multiplieur de Montgomery peut effectuer une opération de multiplication de Montgomery avec le multiplicande, le multiplicateur et le module stockés sous le contrôle de l'hôte, et peut stocker en mémoire un résultat de calcul fourni par l'opération de multiplication de Montgomery stocké.
Un autre exemple de mode de réalisation de l'invention concerne un accumulateur. L'accumulateur peut comporter une pluralité de compresseurs pouvant fonctionner dans un mode d'addition avec sauvegarde du report, chacun de la pluralité de compresseurs recevant un produit modulo, un produit partiel, une première valeur et une seconde valeur, et générant une somme suivante correspondante, un report suivant correspondant, et une valeur inférieure suivante correspondante. L'accumulateur peut comporter un registre de somme pour recevoir la somme suivante correspondante de chacun de la pluralité de compresseurs pour délivrer en sortie une somme courante mise à jour correspondante, un registre de report pour recevoir le report suivant correspondant de chacun de la pluralité de compresseurs, afin de délivrer en sortie un report courant mis à jour correspondant, et un registre de valeurs inférieures pour recevoir la valeur inférieure suivante correspondante de chacun de la pluralité de compresseurs afin de délivrer en sortie une valeur inférieure courante mise à jour.
Un autre exemple de mode de réalisation de l'invention concerne un module de calcul. Le module de calcul peut comporter un multiplieur effectuant séquentiellement (n/c)*(n/c) fois des opérations de multiplication pour un multiplicande à n bits composé de n/c parties de bits, d'un nombre multiplieur à n bits composé de n/c plages, d'un module à n bits composé de n/c plages, des plages étendues du multiplieur et des plages étendues du module. Pour l'unité de calcul, n > c et n et c sont des entiers positifs.
Un autre exemple de forme de réalisation de l'invention concerne une unité de multiplication de Montgomery. L'unité de multiplication peut comporter une matrice de calcul ayant n/c lignes, n et c étant des entiers positifs, chaque ligne étant associée à des opérations de multiplication unités effectuées de façon itérative n/c fois, et à une opération d'addition avec propagation du report. L'unité de multiplication peut comporter un accumulateur ayant une structure d'addition avec sauvegarde du report pour effectuer les opérations de multiplication unités itératives, et un additionneur supplémentaire avec propagation du report pour effectuer l'opération d'addition avec propagation du report.
Un autre exemple de mode de réalisation de l'invention concerne un multiplieur de Montgomery. Le multiplieur de Montgomery peut comporter un générateur de produit modulo sélectionnant un produit modulo parmi une pluralité de modules M sélectionnables à n bits, un module donné M étant formé à partir d'une plage binaire étendue délivrée en entrée à l'instant courant parmi les modules à n bits. Le multiplieur peut comporter un générateur de produit partiel sélectionnant un multiplicande parmi une pluralité de multiplicandes A à n bits pouvant être sélectionnés en tant que produit partiel, un multiplicande A donné étant formé d'une plage binaire étendue délivrée en entrée à l'instant courant parmi les multiplicandes à n bits. Un accumulateur du multiplieur peut accumuler le produit modulo sélectionné et le produit partiel pour générer un résultat de multiplication. Dans un exemple, le multiplieur de Montgomery mentionné ci-dessus peut faire partie d'une unité de calcul et peut comporter une mémoire et un hôte.
Un autre exemple de mode de réalisation de l'invention concerne un multiplieur de Montgomery. Le multiplieur de Montgomery peut être adapté à effectuer une opération de multiplication de Montgomery et une opération de multiplication normale sur la base d'un état logique d'un signal de commande qui lui est délivré en entrée.
La présente invention ressortira plus clairement d'exemples de modes de réalisation de celle-ci fournis en référence aux dessins annexés dans lesquels des éléments identiques sont représentés par des références numériques analogues, ces dessins étant fournis à titre non limitatif d'illustration l'invention.
La figure une structuredes exemples de modes de réalisation de 1 est un diagramme schématique illustrant d'une matrice de calcul permettant d'effectuer une opération en quadruple précision.
La figure 2 illustre une séquence d'une opération de multiplication unité avec la quadruple précision illustrée sur la figure 1.
La figure 3 est un diagramme schématique d'un système cryptographique d'un exemple de mode de réalisation de l'invention.
La figure 4 est un schéma fonctionnel d'un trajet de données du multiplieur de Montgomery d'un exemple de mode 25 de réalisation de l'invention.
La figure 5 est un schéma fonctionnel illustrant l'interface mémoire 12 du multiplieur de Montgomery représenté sur la figure 3.
La figure 6 est une table de vérité illustrant les signaux sélectionnés par un multiplexeur 12_1 dans l'interface mémoire 12 en fonction d'un signal de commande FORCE_RI[2:0].
La figure 7 est une table de vérité illustrant les signaux sélectionnés par le multiplexeur 12_3 dans l'interface mémoire 12 en fonction d'un signal de commande SEL_RDO[1:0].
Les figures 8A à 8C sont des schémas fonctionnels illustrant une structure fonctionnelle du multiplieur de Montgomery 10 d'un exemple de mode de réalisation de l'invention.
La figure 9 illustre une configuration de circuit détaillée d'un exemple de registre 105 stockant une valeur de multiplicande A dans un exemple de mode de réalisation de l'invention.
La figure 10 illustre une structure d'un générateur de produit modulo 120 pour générer une valeur d'un produit modulo MM1 conformément à un exemple de mode de réalisation de l'invention.
La figure 11 est une table de vérité illustrant la configuration de codes d'un enregistreur de Montgomery 110 conformément à un exemple de mode de réalisation de l'invention.
La figure 12 illustre un registre stockant une valeur de multiplicateur B conformément à un exemple de mode de réalisation de l'invention.
La figure 13 illustre un exemple de circuit d'un générateur de produit partiel 130 conformément à un exemple de mode de réalisation de l'invention.
La figure 14 est une table de vérité illustrant la configuration de codes utilisés par un enregistreur de Booth 140 conformément à un exemple de mode de réalisation de l'invention.
La figure 15 illustre un accumulateur 150 conformément à un exemple de mode de réalisation de l'invention.
La figure 16 illustre la configuration de signaux fournis en entrée à des compresseurs dans un exemple d'accumulateur lorsqu'un signal de décalage SHIFT_ACC est au niveau logique "1".
La figure 17 illustre la configuration de signaux fournis en entrée à des compresseurs dans un exemple d'accumulateur lorsqu'un signal de décalage SHIFT_ACC est au niveau logique "0".
La figure 18 illustre un exemple de circuit d'un compresseur 4:2 conformément à un exemple de mode de réalisation de l'invention.
La figure 19 illustre une configuration détaillée d'un 5 registre à décalage 116 conformément à un exemple de mode de réalisation de l'invention.
La figure 20 illustre une configuration détaillée d'un registre à décalage 115 conformément à un exemple de mode de réalisation de l'invention.
La figure 21 illustre une configuration détaillée d'un registre à décalage 180 servant à stocker une somme S0[1:0] de l'accumulateur 150, conformément à un exemple de mode de réalisation de l'invention.
La figure 22 illustre un circuit pour générer SPPI[1:0] devant être fourni à l'enregistreur de Montgomery 110, conformément à un exemple de mode de réalisation de l'invention.
La figure 23 illustre une configuration de circuit d'un bloc de calcul CPA 160 d'un exemple de mode de 20 réalisation de l'invention.
La figure 24 illustre une caractéristique de maintien d'un demi-mot de poids fort d'un mot donné dans l'accumulateur 150, tout en passant à une opération CPA depuis la dernière opération CPA de chaque ligne dans un mode multi-précision à nombre pair de multiplications.
La figure 25 est une table de vérité illustrant la configuration de formules logiques pour des signaux d'entrée/sortie donnés de l'enregistreur de Booth 140.
La figure 26 est une table de vérité illustrant la configuration de formules logiques pour des signaux d'entrée/sortie donnés de l'enregistreur de Montgomery 110.
Des exemples de modes de réalisation de l'invention vont être décrits ciaprès de façon plus détaillée en référence aux dessins annexés. La présente invention peut cependant être mise en oeuvre sous diverses formes et ne doit pas être considérée comme étant limitée aux exemples de modes de réalisation indiqués ici. En effet, ces exemples de modes de réalisation sont proposés afin que le présent fascicule soit détaillé et complet et de mieux faire ressortir le cadre de l'invention aux spécialistes de la technique. Des références numériques identiques désignent des éléments analogues dans l'ensemble du fascicule.
Compte tenu des problèmes décrits pour les systèmes de cryptage classiques, il peut être souhaitable de concevoir une architecture d'un système de cryptage qui soit capable d'améliorer la vitesse de traitement pour une opération modulaire, sans avoir à augmenter ou compliquer le matériel constituant le système. Par ailleurs, du fait de la meilleure aptitude de fonctionnement des systèmes informatiques, il peut être nécessaire d'augmenter la longueur de la clé cryptographique afin d'assurer la sécurité d'un système cryptographique. La longueur d'une clé cryptographique donnée peut de façon souhaitable être variable en fonction de l'application donnée. Par conséquent, un système de cryptage qui peut être adapté à divers environnements d'application avec des clés cryptographiques données de longueurs variables, peut être souhaitable.
Comme cela sera décrit plus en détail ci-après, les exemples de modes de réalisation de l'invention introduisent un multiplieur modulaire de Montgomery à échelle modulable prenant en charge une multiplicité de précisions. Les exemples de modes de réalisation de l'invention permettent d'effectuer un calcul de multiplication avec une multiplicité de précisions en utilisant un multiplieur de Montgomery moins complexe. En outre, l'exemple de multiplieur peut effectuer un calcul de multiplication normal, en plus du calcul de multiplication basée sur un signal de commande approprié.
Les exemples de modes de réalisation de l'invention peuvent être appliqués à un algorithme de multiplication de Montgomery basé sur un système logique de calcul à radical-4, appelé ci-après "algorithme de multiplication de Montgomery entrelacé à radical-4" (R4IMM). Conformément système de calcul logique proposé pour être appliqué à des systèmes de calcul communication utilisant des algorithmes aux le le multiplieur peut ou à des réseaux de cryptographiques du en oeuvre dans des clé publique, et peut être mis etc. exemples de modes de réalisation décrits ci-après, type à cartes à circuit intégré (IC) portatives (ou cartes à 10 puces), Conformément aux exemples de modes de réalisation, des paramètres utilisés dans l'algorithme R4IMM peuvent être définis comme suit.
M représente la valeur d'un module et est un entier impair positif supérieur à 2, c'est-à-dire 3, 7, etc. M' est un entier qui satisfait à l'équation suivante (-M*M')mod 4=1; A représente une valeur de multiplicande et est un entier qui respecte la condition 0 -< A < M; B désigne une valeur de multiplicateur et est un entier qui respeçte une condition 0 <_ B < M. Dans le cas présent, B = r,A', bI E {0, 1, 2, 3}, où bI est un multiplicande unité qui se compose de 2 bits; o est un paramètre qui représente un opérande, et 25 désigne une longueur donnée du multiplicande, du multiplicateur et du module; c est un paramètre qui représente une "longueur de plage" (c'est-à-dire une plage de bits ou d'octets, etc.) lorsqu'un calcul de multiplication unité est en cours 30 d'exécution, et représente une largeur d'un trajet de données qui est présent dans le matériel système w est un paramètre qui représente une longueur de mot (c'est-à-dire la largeur d'un bus de données dans une mémoire) ; et d est un paramètre qui représente une longueur en chiffres d'un radical. Par exemple, si un système de cryptage utilisant un multiplicateur à radical-4 a une largeur de bus de données de 32 bits, la longueur de mot w est de 32 tandis que la longueur de chiffre d est de 2 dans un multiplicateur à radical-4.
Un algorithme R4IMM de base pouvant être appliqué aux exemples de modes de réalisation de l'invention peut être décrit comme suit. So:=O
pour I:= 0 à (n/2-1) q1:= (((SI+ b1A) mod 4) *M') mod 4 S1+1:= (SI+bIA + c'en/4 finpour si (SN ? M) SN: = SN-M Dans l'algorithme R4IMM de base décrit ci-dessus, le paramètre I désigne un indice de chiffre ou le nombre de calculs itératifs. Le quotient qI désigne le nombre de modules M devant être ajoutés pour mettre à "00" les deux bits de poids faible (bits LSB) de SI + bI + q1M. Dans un système à résidu (RNS), dans lequel un nombre obtenu en additionnant un multiple entier du module M à un certain nombre est identique au nombre original, le produit modulo q1M (multiple entier de la valeur du module M) est égal au nombre original. En outre, même lorsque les deux bits de poids faible "00" de l'ensemble SI + bI + q1M sont divisés par la valeur du radical 4 (c'est-à-dire décalés vers la droite de deux (2) bits), les informations ne sont pas perdues en raison du fait que ses nombres de poids fort (c'est-à-dire ses bits de poids fort MSB) sont préservés.
Une valeur de produit partiel PPI et une valeur du produit modulo MM1 sont obtenues pour mettre en oeuvre l'algorithme R4IMM sur un système matériel. Comme le multiplicande unité bI et le quotient qI sont chacun à deux bits, le produit partiel PP1 et le produit modulo MM1 peuvent être générés en utilisant quatre valeurs disponibles, comme illustré dans l'équation 1 (dans le cas présent, bI {0, 1, 2, 4} et qI {0, 1, 2, 3}).
[Equation 1] b1A = PP1 E {0, A, 2A, 3A} q1A = MMI E {0, M, 2M, 3M} Cependant, si le produit partiel PP1 et le produit modulo MM1. sont établis comme à l'équation 1, un calcul permettant d'obtenir une somme d'une valeur décalée d'un bit de A ou de M et de sa valeur originale (c'est-à-dire de A ou de M) doit être effectué afin de calculer 3A ou 3M. Dans une exemple, un additionneur indépendant peut être utilisé pour calculer les valeurs 3A ou 3M, ou bien les valeurs 3A ou 3M peuvent être calculées à l'avance et stockées afin qu'on puisse s'y référer plus tard. Cependant, le calcul de 3A et de 3M peut imposer une charge excessive à l'architecture matérielle classique et peut constituer une source de dégradation des performances de fonctionnement, étant donné que le système doit être conçu pour tenir compte du temps et de l'espace nécessaires pour calculer dans celui-ci les valeurs 3A et 3M.
Par conséquent, les exemples de modes de réalisation de l'invention peuvent être configurés de façon à réduire la charge matérielle tout en augmentant les performances de calcul lorsqu'on génère la valeur du produit partiel PP1 et les valeurs des produits modulo MM1. Cette réduction de la charge imposée au matériel avec amélioration du traitement est possible par utilisation de deux types distincts de dispositifs d'enregistrement et/ou de méthodologies d'enregistrement.
En outre, le multiplieur utilisé conformément aux exemples de modes de réalisation de l'invention peut effectuer un calcul de multiplication à c bits en un temps donné et est capable de traiter un calcul de multiplication à n bits (où n est un multiple entier de c) en utilisant des cycles de calcul itératifs. Un algorithme R4IMM à précision multiple peut donc être configuré de la façon suivante.
pour row_idx = 0 à row_idx = (n/c-1) commencer pour col_idx = 0 à col_idx = (o/c-1) commencer do_ini(); pour wrd_idx = 0 à wrd_idx = (c/w-1) commencer pour dgt_idx = 0 à dgt_idx = (w/d-1) commencer do_acc(); finpour finpour finpour pour wrd_idx = 0 à wrd_idx = (c/w-1) commencer do- cpa(); finpour finpour Dans cet algorithme, la fonction do_ini() désigne une fonction permettant d'accumuler une plage (plage de bits ou octets d'un mot) qui est positionnée à la même position qu'une colonne courante et sur une valeur courante dans l'accumulateur, à partir du résultat du calcul S déterminé à la ligne précédente. En d'autres termes, la fonction do_ini() modifie une valeur initiale d'un accumulateur du multiplieur au début d'une boucle sur une colonne donnée. Cette procédure de modification est effectuée en raison du fait que le multiplieur de Montgomery des exemples de modes de réalisation de l'invention est conçu pour être adapté à une opération donnée à précisions multiples.
10 15 20 La fonction do_acc() désigne une fonction d'accumulation de deux vecteurs du produit partiel PP et du produit modulo MM, qui sont générés lors de chaque cycle dans l'accumulateur. Comme l'accumulateur utilisé dans les exemples de modes de réalisation de l'invention peut être mis en oeuvre sous la forme de l'architecture d'un ou plusieurs additionneurs avec sauvegarde du report (CSA), une valeur obtenue à partir de l'addition peut être représentée de façon divisée dans chacun d'un vecteur de report, d'un vecteur de somme, et d'un vecteur de valeur inférieure, qui sont tous stockés dans un registre correspondant affecté au vecteur donné.
La fonction do_cpa() désigne une opération d'addition avec valeur de report, une valeur de somme et une valeur inférieure. Cette fonction peut être mise en oeuvre en utilisant un additionneur avec propagation du report, dans lequel les valeurs sont obtenues en tant que résultat accumulé lors de la dernière étape de chaque ligne.
La figure 1 est un diagramme schématique illustrant la structure d'une matrice de calcul permettant de mettre en oeuvre une opération à quadruple précision. Se référant à la figure 1, pour une opération à quadruple précision, le multiplicande A, le multiplicateur B, et le module M sont chacun divisés en quatre plages chacune représentée par A = { A3A2A1Ao} , B = { B3B2B1Bo} , et M = { M3M2M1Mo} . Dans un multiplieur ayant une longueur de plage de c bits, un calcul de multiplication peut être effectuée séquentiellement dans une unité constituée par la plage, par exemple Ao*Bo, Al*Bo, A2*Bo, A3*Bo, etc., le résultat final du calcul de multiplication étant stocké.
La figure 2 illustre une séquence d'un calcul de multiplication unité à quadruple précision représenté sur la figure 1. Conformément aux exemples de modes de réalisation de l'invention, les paramètres A3, A2, Al, A0, B3, B2, et BO peuvent représenter des longueurs de plages, et les ensembles de calculs Ao*Bo, Al*Bo, A2*Bo, A3*Bo, etc., peuvent être appelés calculs (ou boîtes) de multiplication unités. Chacun des calculs pour le multiplicande A et le multiplicateur B peut être effectuée par un accumulateur d'une boucle d'addition avec sauvegarde du report (CSA), et peut comprendre une boucle d'addition avec propagation du report (CPA) pour sommer trois valeurs finales (un report, une somme et une valeur inférieure) dans l'accumulateur afin de générer une valeur unique après achèvement du calcul de multiplication unité final de chaque ligne. La figure 2 illustre ainsi la séquence des calculs de multiplication unités effectués avec la précision quadruple représentée sur la figure 1.
La figure 3 est un diagramme schématique d'un système cryptographique d'un exemple de mode de réalisation de l'invention. Se référant à la figure 3, le système de cryptage 1 peut comporter un multiplieur de Montgomery 10, un hôte 20, un dispositif d'arbitrage d'accès mémoire 30, et une mémoire 40. L'hôte 20 peut comprendre une interface périphérique 21 pour les communications avec des dispositifs périphériques tels que le multiplieur de Montgomery 10 et des unités d'entrée/sortie, et une interface mémoire pour les communications avec la mémoire 40.
Le multiplieur 10 peut comporter une interface hôte 11 pour communiquer avec l'hôte 20, et une interface mémoire 12 pour communiquer avec la mémoire 40. Les conditions des communications entre le multiplieur 10, l'hôte 20 et la mémoire 40 peuvent être régulées par exemple par un arbitre d'accès mémoire 30. L'interface hôte 11 peut comporter un registre à fonctions spéciales (SFR) 13. Le multiplieur 10 peut également comporter un contrôleur (non représenté) pour générer certains signaux de commande désignés ci-après de façon plus détaillée FORCE_RI[2:0], SEL_RDO[1:0], FORCE_PP[1:0], FORCE_MM[1:0], USE_X_REG, SEL_CPA_IN[2:0], IS_1ST_CPA_WORD, IS_ODD_PREC, UDP_SIGN_S, UPD_MS1B_S, SFT_BI_PISO, SFT_QI_PISO, STO_BR_ROW et SHIFT_ACC.
L'hôte 20 stocke les opérandes (le multiplicande A, le multiplicateur B, le module M) dans la mémoire 40, et ordonne l'exécution d'un mode d'opération d'enregistrement en envoyant un ordre de début de fonctionnement au registre SFR 13. Le multiplieur 10 informe égalementl'hôte 20 de la fin d'un calcul en enregistrant les informations de fin d'opération dans le SFR 13, mais après stockage de la valeur S obtenue d'un calcul donné dans un champ de la mémoire 40. Le champ dans lequel la valeur S obtenue est stockée peut être désignée par l'hôte 20. Le registre SFR 13 peut également stocker un bit de signe qui sera décrit plus loin plus en détail.
La mémoire 40 peut être divisée en segments qui sont dimensionnés sous la forme d'une capacité de stockage donnée. L'entrée de stockage de segment et les valeurs qui en résultent peuvent être désignées par l'hôte 20 avec un indice affecté à chaque segment. Par conséquent, si un résultat obtenu après un cycle d'un calcul de multiplication est à nouveau appliqué au calcul de multiplication suivant en tant que valeur d'entrée (il s'agit d'un calcul exponentiel utilisé dans un système cryptographique à clé publique tel que le système RSA), il est possible d'effectuer le calcul de multiplication suivant après n'avoir changé qu'un indice du segment pour des valeurs d'entrée et de sortie, c'est-à-dire sans aucune migration des données. Cela peut être avantageux pour améliorer les performances du système.
La figure 4 est un schéma fonctionnel d'un multiplieur de Montgomery d'un exemple de mode de réalisation de l'invention. La figure 4 illustre la configuration d'une entrée de donnée et d'une sortie de donnée du multiplieur de Montgomery 10.
La figure 5 est un schéma fonctionnel illustrant l'interface mémoire 12 du multiplieur de Montgomery représenté sur la figure 3. L'interface mémoire 12 comporte des multiplexeurs 12_1 et 12_3 et des registres 12_2 et 12 4.
La figure 6 est une table de vérité illustrant les signaux sélectionnés par un multiplexeur 12_1 dans l'interface mémoire 12 conformément à un signal de commande FORCE_RI[2:0], et la figure 7 est une table de vérité illustrant les signaux sélectionnés par le multiplexeur 12_3 dans l'interface mémoire 12 conformément à un signal de commande SEL_RDO[1:0]. Le multiplexeur 12_1 délivre en sortie l'un des signaux d'entrée en réponse au signal de commande FORCE_RI[2:0]. Comme illustré sur la figure 6, un signal de données REG_DI[31:0] délivré en sortie par le multiplexeur 12_1 et par le registre 12_2 peut être fourni au trajet de données 100 du multiplieur de Montgomery, comme cela sera décrit plus en détail ci-après. Le multiplexeur 12_3 délivre en sortie l'un de ses signaux d'entrée en réponse à un état du signal de commande SEL_RDO[1:0]. Comme illustré sur la figure 4, un signal de données RAM_DO[31:0] délivré en sortie par le multiplexeur 12_3 et par le registre 12_4 peut être stocké dans la mémoire 40.
Les figures 8A à 8C sont des schémas fonctionnels illustrant la structure fonctionnelle du multiplieur de Montgomery d'un exemple de mode de réalisation de l'invention. Le multiplieur de Montgomery représenté sur les figures 8A à 8C peut comprendre des registres de module 102 et 103 pour stocker le module M, des registres de multiplicande 104 et 105 pour stocker le multiplicande A, un registre de multiplicateur 106 pour stocker le multiplicateur B, un registre de valeur précédente 101 stockant une valeur obtenue de la ligne précédente (SI), un enregistreur de Montgomery 110, un enregistreur de Booth 140, un générateur de module multiple 120 pour générer un produit modulo MM, un générateur de produit partiel 130 pour générer un produit partiel PP, un accumulateur 150 pour effectuer un calcul de multiplication de Montgomery, et un bloc CPA 160 pour sommer trois valeurs obtenues (une valeur de report, une valeur de somme et une valeur inférieure) dans l'accumulateur 150.
La longueur de chaque opérande stocké dans les registres 101 - 105 peut être égale à (c+w/2)+l. Chaque registre peut être composé d'un registre du type à entrée parallèle et à sortie parallèle (PIPO) et peut être commandé par division d'une bascule à 1 bit et de 2*(c/w)+1 sous- registres. La longueur des sous-registres peut être égale à w/2.
La figure 9 illustre la configuration détaillée d'un circuit d'un exemple de registre 105 stockant une valeur de multiplicande A conformément à un exemple de mode de réalisation de l'invention. La structure du registre 105 est un exemple; chacun des registres 101 - 105 peut être formé de façon à avoir la même architecture. Se référant à la figure 9, le registre 105 peut être configuré dans des conditions telles que c=256 et w=32, et peut comporter 17 sous-registres 200 - 216 et un registre de signe 220. Bien que 17 sous-registres soient représentés, un registre donné peut être configuré de façon à comporter par exemple moins ou plus de 17 sous-registres; ce nombre peut dépendre de l'application.
Lorsque c=256 et w=32, la taille de chacun des sous- registres 200-216 peut être de 16 bits (représentant un demi-mot) et la taille du registre de signe 220 peut être d'un bit. Les sous-registres de numéros pairs 200, 202, 204,... et 216 peuvent recevoir 16 bits de poids faible REG_DI[15:0] de données (un mot à 32 bits) délivrés par l'interface mémoire 12 alors que les sous-registres de numéros impairs 201, 203, 205, ..., et 215 peuvent recevoir les 16 bits de poids fort REG_DI[31:16] des données à 32 bits délivrées par l'interface mémoire 12.
Sous sa forme originale, la longueur de bit n de l'opérande est un multiple entier de la longueur binaire de plage c, de sorte qu'un bit de signe est ajouté à l'opérande en raison du fait que les fonctions d'enregistrement de Booth et de Montgomery lui sont appliquées. Par conséquent, la longueur binaire (c') de chaque opérande utilisé dans le trajet de données 100 du multiplieur de Montgomery devient égale à c'=c+k, où la valeur minimum de k est égale à 1. Le paramètre c' est appelé "longueur binaire de plage étendue" et est un paramètre qui représente la longueur binaire d'une plage étendue. Dans la pratique, à mesure que des données d'entrée sont lues depuis la mémoire 40 et que la largeur de bus de données w=32 restitue un mot, un demi-mot et un quart de mot de façon à ce qu'ils aient respectivement 32, 16 et 8 bits, en tant que débit de transmission des données, les valeurs disponibles de k sont w, w/2 et w/4 pour les débits de transmission de données. Une valeur plus petite de k réduit le nombre de cycles d'itération pour le calcul de multiplication unité (calcul CSA sur la figure 1) et réduit donc la taille du matériel correspondant mettant en oeuvre les cycles d'itération. Cela peut être avantageux pour obtenir de meilleures performances de calcul avec une taille et/ou une consommation de puissance réduite des circuits, etc. Par conséquent, une architecture matérielle simplifiée peut être réalisée lorsque k=w/2 et non pas k=w et si k=w/4 par comparaison à k=w/2. Les valeurs disponibles pour k peuvent donc être l'une des valeurs w, w/2 et w/4. Dans un exemple, les exemples de modes de réalisation de l'invention utilisent une valeur de k égale à k=w/2. Par conséquent, dans cet exemple, avec une longueur binaire de plage c=256, une longueur de mot w=32 et une valeur de k=32/2=16, la longueur binaire de plage étendue c' peut être déterminée comme étant c'=272 bits (comme c'=c+k et k=w/2, c'=256+ 16=272). Le bit de SIGN__S qui est stocké dans le registre SFR 13 peut être stocké dans le registre de signe 220 via l'interface mémoire 12.
Chaque sous-registre effectue une opération de chargement sélective de données en réponse à une horloge déclenchée ou à un signal de commande d'activation de chargement. Par conséquent, un multiplicande AX_PIPO_REG[272:0] délivré par le registre 105 est composé de 273 bits (la longueur binaire de plage étendue de 272 bits et le bit SIGN_S à 1 bit). Les structures des registres 101-104 sont identiques à celle du registre 105. Comme illustré sur la figure 8B, les données fournies aux registres 101-105 sont REG_DI[31:0]. Comme illustré sur la figure 5, les données REG_DI[31:0] peuvent être générées par combinaison de données de longueur de mot RAM_DI[32:0] fournies à l'interface mémoire 12 par la mémoire 40, des bits de signe SIGNA, SIGN_B et SIGN_S, et du second bit de poids fort MS1B_S de la valeur obtenue précédemment. Comme illustré dans la table de vérité de la figure 6, le signal de commande FORCE_RI[2:0] détermine l'instant ou/et la façon dont la combinaison est générée pour définir les données REG_DI[31:0].
La valeur de registre précédente 101 peut être utilisée pour fournir une valeur obtenue à la ligne précédente SI, pour effectuer un calcul avec une ligne courante. Sur la figure 8B, cela est représenté sous la forme SI_PIPO_REG[272:0].
Deux registres de modules 102 et 103 sont utilisés pour fournir des valeurs de modules M (figure 8 MY_PIPO_REG[272:0] et MX_PIPO_REG[272:0]) aux multiples registres de modules 120 et deux registres de multiplicandes 104 et 105 sont utilisés pour fournir des valeurs de multiplicandes A au générateur de produit partiel 130 (figure 8B, AY_PIPO_REG[272:0] et AX_PIPO_REG[272:0]). La raison pour laquelle on utilise deux registres servant chacun à stocker la ou les valeur(s) de multiplicande(s) A et la ou les valeur(s) de module(s) M est que l'on cherche à augmenter les vitesses de traitement pour traiter A et M. Par exemple, parmi les deux registres 104 et 105 destinés aux multiplicandes A, un registre (104 ou 105) stocke une valeur de multiplicande A devant être utilisée pour un calcul de multiplication unité courant dans le trajet de données du multiplieur de Montgomery 100, tandis que l'autre stocke une valeur de multiplicande A devant être utilisée dans le calcul de multiplication unité suivant. De même, parmi les deux registres 102 et 103 du module M, un registre (102 ou 103) stocke une valeur de module M devant être utilisée dans un calcul de multiplication unité courant dans le multiplieur de Montgomery 10, tandis que l'autre registre stocke une valeur de module M devant être utilisée dans le calcul de multiplication unité suivant. Il est donc possible de commencer le calcul de multiplication unité suivant sans aucun retard en lisant les valeurs de multiplicandes et de modules depuis la mémoire, après achèvement du calcul de multiplication unité courant.
Le multiplieur 10 obtient une solution de multiplication de Montgomery par des cycles de traitement itératifs. L'enregistreur de Montgomery 110 et le générateur de produit modulo 120 sont utilisés pour sélectionner le produit modulo MM1. Lors de la sélection du produit modulo MM1, l'enregistreur de Montgomery 110 reçoit des données itératives de l'accumulateur 150. Les données itératives SPPI[1:0] dans cet exemple de mode de réalisation de l'invention peuvent être générées sur la base d'une somme ACC_S_REG1[1:0], d'un report ACC_REGI[1:0], d'une valeur inférieure ACC_L_REG1[2:0], et d'un produit partiel PPI[1:0], tous stockés dans l'accumulateur 150, et d'un signal de commande de décalage SHIFT_ACC pour une entrée de contre-réaction de l'accumulateur 150. Les données itératives SPP1[1:0] peuvent être une longueur (ou une taille) binaire variable en fonction des exemples de modes de réalisation de l'invention. Par exemple, SPP1 peut avoir plus de deux (2) bits, tout comme d'autres éléments du mode de réalisation.
La figure 10 illustre une structure du générateur de produit modulo 120 pour générer le produit modulo MM1 conformément à un exemple de mode de réalisation de la présente invention. Le générateur de produit modulo 120 peut comporter des multiplexeurs 301--303 et une porte ET 304. Le multiplexeur 301 délivre en sortie l'un des modules MY_PIPO_REG[272:0] et MX_PIPO_REG[272:0], qui sont fournis par les registres de modules 102 et 103, en réponse à un signal de sélection de registre USE_X_REG.
Le multiplexeur 303 délivre en sortie l'une d'une valeur précédente SI_PIPO_REG[272:0], M, 2M et -M en réponse à un signal de sélection de produit modulo SEL_MM[1:0]. La valeur 2M peut être obtenue en décalant la valeur M, qui est délivrée en sortie par le multiplexeur 302, vers la gauche d'1 bit puis en insérant un "0" à la position du bit de poids faible. La valeur -M peut être obtenue en inversant les bits du M qui est délivré en sortie par le multiplexeur 302.
La porte ET 304 combine un signal de validation de produit modulo EN_MM provenant de l'enregistreur de Montgomery 110 (figure 8A) avec une sortie du multiplexeur 303 pour délivrer en sortie le produit modulo MM1. Le produit modulo MM1 peut être composé de (c+w/2)+2 bits. Par exemple, lorsque c=256 et w=16, MMI comporte 274 bits. Le signal de validation de produit modulo EN_MM peut être utilisé pour mettre à "0" le produit modulo MM1. Le produit modulo MM1 est fourni à l'accumulateur 150, comme illustré sur la figure 8B.
La figure 11 est une table de vérité illustrant la configuration de codes dans l'enregistreur de Montgomery 110 conformément à un exemple de mode de réalisation de l'invention. Bien que la figure 11 représente trois entrées M[1] et SPPI[1:0] délivrées à l'enregistreur de Montgomery 110, les exemples de mode de réalisation pourraient être configurés comme ayant un nombre quelconque souhaité d'entrées et de sorties.
Comme décrit précédemment, le produit modulo MMI dans un système à radical-4 peut comprendre 0, M, 2M et 3M. L'obtention de 3M nécessite typiquement un additionneur ou un élément de mémoire supplémentaire pour additionner 2M à M. L'ajout de l'additionneur et/ou de l'élément de mémoire contribue à la taille du matériel et/ou au retard de calcul, en affectant donc la vitesse de calcul et la consommation d'énergie. La méthode de codage représentée sur la figure 11 utilise une inversion binaire et un décalage binaire afin d'obtenir le produit modulo MM1 sans additionneurs ni éléments de mémoire supplémentaires. L'enregistreur de Montgomery 110 reçoit le second bit de poids fort M[1] du module M et les deux bits de poids faible SPP1, c'est-à-dire SPPI[1:0]. L'enregistreur de Montgomery 110 délivre en sortie le signal de sélection de produit modulo SEL_MM[1:0], le signal de validation de produit modulo EM_MM, et un signal d'inversion de signe NEG_MM pour indiquer une inversion de signe (le signal NEG_MM indique si une inversion de bits est utilisée pour obtenir -M).
Dans un autre exemple de mode de réalisation de l'invention, un procédé semblable permettant de réduire la taille du matériel, d'augmenter la vitesse de calcul et/ou de réduire la consommation d'énergie peut être utilisé dans le générateur de produit partiel 130 et dans l'enregistreur de Booth 140 respectivement représentés sur les figures 13 et 14. En général, le multiplieur 100 reçoit le produit modulo MM' et le produit partiel PP1 par l'intermédiaire de l'accumulateur 150 puis effectue la multiplication modulo conformément à des cycles de calculs itératifs. Les figures 13 et 14 seront décrites plus en détail ci-après.
La figure 12 illustre le registre 106 stockant le multiplicateur B, conformément à un exemple de mode de réalisation de l'invention. Le registre de multiplicateur 106 stocke le multiplicateur B reçu de la mémoire 40 puis délivre en sortie avec décalage un bit de poids fort BR, parmi les bits de poids faible Bl et BO et les bits de poids plus faible du cycle précédent du multiplicateur B, vers la droite une fois par cycle, à l'exception du cycle destiné à corriger une valeur initiale de l'accumulateur 150. Comme illustré sur la figure 12, le registre de multiplicateur 106 comporte un registre à décalage 401, des multiplexeurs 402 et 405, et des bascules 403 et 404.
Le registre à décalage 401 peut être configuré de façon à avoir la même longueur binaire que la longueur de mot (w=32), et peut être mis en fonctionnement en réponse à un signal de sélection de décalage SFT_BI_PISO. Le registre à décalage 401 reçoit une première fois un mot de donnée de multiplicateur par l'intermédiaire de REG_DI[31:0] de l'interface mémoire 12 lorsque le signal de sélection de décalage SFT_BI_PISO est à un niveau logique "0", alors qu'il décale le mot reçu vers la droite de deux bits lorsque le signal de sélection de décalage SFT_BI_PISO est à un niveau logique "1". Les deux bits de poids faible B1 et BO du registre à décalage 401 sont délivrés en sortie à l'enregistreur de Booth 140.
Un signal STO_BR_ROW est fourni pour stocker le second bit de poids faible B1 ayant été utilisé dans le dernier cycle du calcul de multiplication unité pour le niveau bas (c'est-à-dire lorsque le signal de sélection de décalage SFT_BI_PISO est à un niveau logique "0"). Le multiplexeur 402 délivre en sortie sélectivement une valeur stockée dans la bascule 403 ou dans le second bit de poids faible B1 du registre à décalage 401. La bascule 403 stocke une sortie de multiplexeur 402 et la bascule 404 stocke le second bit de poids faible Bi du registre à décalage 401. Un signal USE_BR_ROW est fourni pour commander la valeur BR_ROW de la bascule 403 afin qu'elle soit sélectionnée en tant que bit BR lors du second cycle (c'est-à-dire le cycle suivant, après le cycle de correction d'une valeur initiale de l'accumulateur 150). Le bit BR est fourni à l'enregistreur de Booth 140.
L'enregistreur de Booth 140 et le sélecteur de produit partiel 130 sont utilisés pour sélectionner les valeurs du produit partiel PP1 0, A, A, 2A et 2A, afin qu'elles soient fournies à l'accumulateur 150. Comme illustré sur les figures 8A et 8C, l'enregistreur de Booth 140 reçoit les bits B1, BO et BR du multiplicateur B en provenance du registre 106, et fournit le signal de sélection de produit partiel SEL_PP[1:0], le signal de validation de produit partiel EN_PP, et le signal d'inversion de signe de produit partiel NEG_PP au générateur de produit partiel 130.
La figure 13 illustre un exemple des circuits du générateur de produit partiel 130 conformément à un exemple de mode de réalisation de l'invention. Le générateur de produit partiel 130 peut comporter des multiplexeurs 501503 et une porte ET 504. Le multiplexeur 501 délivre en sortie une valeur de multiplicande donnée A (c'est-à-dire A[272:0]) parmi les multiplicandes AY_PIPO_REG[272:0] et AX_PIPO_REG[272:0] fournis par les registres 104 et 105 en réponse au signal de sélection de registre USE_X_REG.
Le multiplexeur 503 délivre en sortie une valeur de multiplicande sélectionnée parmi 2A, A, 2A et A en réponse au signal de sélection de produit modulo SEL_PP[1:0] fourni par l'enregistreur de Booth 140. La valeur 2A est obtenue en décalant A, qui est délivré en sortie par le multiplexeur 501, vers la gauche d'un bit et en insérant un "1" à sa position du bit de poids faible. La valeur 2A est obtenue en décalant A, qui est délivré en sortie par le multiplexeur 501, vers la gauche d'un bit et en insérant un "0" à sa position du bit de poids faible.
La porte ET 504 délivre en sortie le produit partiel PP1 en combinant logiquement le signal de validation de produit partiel EN_PP de l'enregistreur de Booth 140 et une sortie du multiplexeur 503. Le signal de validation de produit partiel EN_PP est utilisé pour créer un "0" en tant que produit partiel PP1. Le produit partiel PP1 peut être dimensionné à (c+w/2)+2 bits. Dans cet exemple, le produit partiel PPI a 274 bits lorsque c=256 et w=32. Le produit partiel PP1 est fourni à l'accumulateur 150.
La figure 14 est une table de vérité illustrant la configuration de codes dans l'enregistreur de Booth 140 conformément à un exemple de mode de réalisation de l'invention. Bien que la figure 14 représente trois entrées B1, BO et BR délivrées à l'enregistreur de Booth 140, les exemples de modes de réalisation pourraient être configurés comme ayant un nombre quelconque d'entrées et de sorties souhaitées.
Se référant à nouveau aux figures 8A et 8C, le produit modulo MMI[273:0] généré par le générateur de produit modulo 120 et le produit partiel PP1[273:0] généré par le générateur de produit partiel 130 sont fournis à l'accumulateur 150.
La figure 15 illustre l'accumulateur 150 d'un exemple de mode de réalisation de l'invention. Se référant à la figure 15, l'accumulateur 150 peut se composer de compresseurs 4:2 610617 connectés en série qui comprennent un nombre de bits égal à c'=c+w/2+5. Comme décrit précédemment en référence aux figures 10 et 13, chaque longueur binaire du produit modulo MMI et du produit partiel PPI a (c+w/2)+2 bits.
L'accumulateur 150 peut stocker de façon divisée un résultat de calcul dans un registre de somme 620, un registre de report 630, et un registre de valeur inférieure 650. Le registre de somme 620 peut être composé de bascules à (c+w/2)+3 bits. Le registre de report 630 peut être composé de bascules à (c+w/2)+4 bits. Le registre de valeur inférieure 650 peut être composé de trois bascules. Le bloc CPA 160 représenté sur la figure 8B reçoit c+1 bits de poids fable ACC_S_REG[c:0] et ACC_C_REG[c:0] provenant chacun des sorties du registre de somme 620, du registre de report 630, et du bit de poids fort ACC_L_REG[2] parmi les bits de sortie du registre de valeur inférieure 650. De plus, les deux bits de poids faible ACC_L_REG[2:0] du registre de valeur inférieure 650 sont fournis à un générateur SPP 170, comme illustré sur la figure 8c.
Dans cet exemple de mode de réalisation, les entrées de l'accumulateur 150 comprennent le produit modulo MMI, le produit partiel PPI, le signal d'inversion de produit modulo NEG_MM, le signal d'inversion de produit partiel NEG_PP, et le signal de commande de décalage SHIFT_ACC pour une entrée de contre-réaction de l'accumulateur 150. L'exemple d'accumulateur 150 peut être intégré à l'architecture du CSA, pour éviter une dégradation des performances dues au retard de propagation du report. Chacun des compresseurs 610-617 peut être constitué de quatre entrées et deux sorties c'est-à-dire qu'il peut être un compresseur 4:2.
La figure 18 illustre un exemple de circuit du compresseur 4:2. Le compresseur 612 a une pluralité d'entrées. Les valeurs d'entrée du compresseur ont un indice de boucle I et les valeurs de sortie ont un indice de boucle de 1+1.
Pour cet exemple, le compresseur 612 peut comporter des additionneurs complets 701 et 702. Le premier additionneur complet 701 reçoit CI, PI et PPI, puis délivre en sortie un premier report d'additionneur complet CO et une première somme d'additionneur complet S0. Le premier report d'additionneur complet CO est délivré en sortie en tant que report de sortie CN, qui devient une entrée CP du compresseur de position binaire de poids immédiatement supérieur k+1 (qui pourrait être le compresseur suivant par rapport au compresseur 612 entre les compresseurs 612 et 613 sur la figure 15). Le second additionneur complet 702 reçoit la première somme d'additionneur complet SO, le produit modulo MMI, et un report CP du compresseur de position de valeur de bit de poids plus faible à 1 bit (c'est-à-dire du compresseur 611), et délivre en sortie un second report d'additionneur complet CO et une seconde somme d'additionneur complet SO. Le second report d'additionneur complet CO est délivré en sortie en tant que bit de report suivant CI+i, utilisé comme report CI qui est appliqué au compresseur de position de valeur de bit plus faible à 1 bit 611. La seconde somme d'additionneur complet SO est utilisée en tant que somme SI qui est appliquée au compresseur de position de valeur de bit de poids plus faible à 2 bits. Le compresseur de poids le plus faible (c'est-à-dire le compresseur 610) reçoit le signal d'inversion de produit partiel NEG_PP en tant qu'entrée du report CP.
La relation entre l'entrée et la sortie du compresseur 4:2 612 peut être résumée par l'équation 2 suivante.
[Équation 2] 2CN + 2CI+I + SI+I = CP + CI + SI + PP1 + MMI En ce qui concerne à nouveau la figure 15, l'additionneur complet 640 reçoit une somme SI[0] délivrée en sortie par le premier compresseur 610, le bit de poids le plus faible MMI[0] du produit modulo, et le signal d'inversion de produit modulo NEG_MM. L'additionneur complet 641 reçoit un bit de somme délivré en sortie par le second compresseur 611, un bit de report délivré en sortie par le premier compresseur 610, et un bit de report délivré en sortie par l'additionneur complet 640. La somme de l'additionneur complet 640 et le report de l'additionneur complet 641 sont stockés dans le registre de valeur inférieure 650.
L'accumulateur 150 accumule un résultat correspondant à une opération de multiplication unité courante, parmi des résultats correspondant à la ligne précédente lors du premier cycle du calcul de multiplication unité. Ce mode opératoire est appelé cycle de correction de valeur initiale et c'est pour cela qu'il comporte les multiplexeurs 600-609.
Une borne d'entrée d'un compresseur est reliée à deux multiplexeurs. A titre d'exemple, deux multiplexeurs 600 et 601 sont reliés au premier compresseur 610 correspondant aux bits de poids faible MMI[0] et PPI[0] des produits modulo et partiel. Le multiplexeur 600 reçoit un bit de somme ACC_S_REG[0] en tant que première entrée et une valeur inférieure ACC_L_REG[0] en tant que seconde entrée, celles-ci étant fournies par son compresseur correspondant à la position du bit de poids plus fort à 2 bits. Le multiplexeur 601 reçoit un bit de somme ACC_S_REG[0] en tant que première entrée et une valeur inférieure ACC_L_REG[2] en tant que seconde entrée, qui sont fournies par son compresseur de position de bit de poids plus fort à 1 bit 611.
Pour le second compresseur 611, le multiplexeur 602 reçoit un bit de somme ACC_S_REG[1] en tant que première entrée et une valeur inférieure ACC_L_REG[1] en tant que seconde entrée, ceux-ci étant fournis par son compresseur de position de bit de poids plus fort à 2 bits. Le multiplexeur 603 reçoit un bit de somme ACC_S_REG[1] en tant que première entrée et une valeur inférieure ACC_L_REG[2] en tant que seconde entrée, celles-ci étant fournies par son compresseur de position de bit de poids plus fort à 1 bit 612.
Quant au troisième compresseur 612, le multiplexeur 604 reçoit un bit de somme ACC_S_REG[2] de son compresseur de poids plus fort à 2 bits en tant que première entrée, et un bit de somme ACC_S_REG[0] du compresseur 612 qui lui est relié en tant que seconde entrée. Le multiplexeur 605 reçoit un bit de report ACC_C_REG[2] de son compresseur de poids plus fort à 1 bit en tant que première entrée et un bit de report ACC_C_REG[0] de son compresseur de poids plus faible à 1 bit (c'est-à-dire du compresseur 611) en tant que seconde entrée.
Les premier et second multiplexeurs reliés au troisième compresseur 612 par l'intermédiaire du dernier compresseur 617 sont réalisés avec la même architecture. Cependant, la première entrée du multiplexeur 608 reliée au compresseur de poids le plus fort 617 est un bit de somme du compresseur 617 connecté à lui-même, tandis que la première entrée du second multiplexeur 609 est un bit de report du compresseur 617 connecté à luimême.
La première entrée du premier multiplexeur 606 reliée au compresseur 616 qui est positionné à une position inférieure à la position de poids le plus fort, est un bit de somme de son compresseur de poids plus fort à 1 bit 617. Les produits modulo et partiel PP1 et MM1 fournis au quatre compresseurs de poids plus élevé à partir des positions de poids fort 617, 616, 615 et 614, sont tous identiques et sont les bits de poids fort de MM' et de PP1.
La figure 16 illustre la configuration de signaux fournis en entrée à des compresseurs lorsque le signal de décalage SHIFT_ACC est à un niveau logique "1". Le signal de décalage SHIFT_ACC est à un niveau logique "0" pendant un cycle suivant immédiatement le cycle de correction de valeurinitiale de l'accumulateur, tandis qu'il est à un niveau logique "1" pendant les cycles restants. Lorsque le signal de décalage SHIFT_ACC est à un niveau logique "1", chacun des premier et second multiplexeurs 600, 602, ... et 608, et 601, 603, ..., et 609 délivre en sortie sa première entrée en tant que sortie de celui-ci, comme illustré sur la figure 16.
Pour tous les cycles, à l'exception du cycle de correction de valeur initiale de l'accumulateur 150, une somme SO[1:0] stockée dans le registre de valeur inférieure 650 est délivrée en sortie. Les valeurs de report, de somme et inférieure fournies par les compresseurs 612-617 sont chacune stockées dans le registre de report 630, le registre de somme 620 et le registre de valeur inférieure 650, et sont envoyées à des boucles de contre-réaction pour les compresseurs 610-617 lors du cycle suivant. Comme les produits partiels et les produits modulo multiples devant être accumulés lors du cycle suivant ont un poids plus élevé de 2 bits que ceux du cycle précédent de 2 bits, ils doivent être fournis en entrée avec une contre-réaction à des positions binaires plus basses de deux bits que celles des positions de stockage précédentes.
La figure 17 illustre la configuration de signaux fournis en entrée à des compresseurs lorsque le signal de décalage SHIFT_ACC est au niveau logique "O". Lorsque le signal de décalage SHIFT_ACC est à un niveau logique "O", chacun des premier et second multiplexeurs 600, 602, ... et 608, et 601, 603, ... et 609, délivre en sortie sa seconde entrée en tant que sortie de celui-ci, comme illustré sur la figure 17.
Pendant le cycle de correction de valeur initiale de l'accumulateur 150 pour chaque boîte, l'accumulateur 150 effectue une opération de correction de la valeur initiale de l'accumulateur 150 en accumulant une valeur qui correspond à une valeur stockée dans le registre à une position binaire donnée, parmi les valeurs résultant de la ligne précédente. A ce stade, les valeurs stockées dans le registre de somme 620, le registre de report 630 et le registre de valeur inférieure 650, peuvent être fournies dans la boucle de contre-réaction en tant qu'entrées de l'accumulateur 150, sans changement des positions binaires.
Comme décrit ci-dessus, le produit partiel est PP1 = {-2A, -A, 0, + A, + 2A} et le produit modulo est MM1 = {SI, -M, 0, +M, +2M}. Pour le cycle de correction de valeur initiale de l'accumulateur 150, on sélectionne respectivement 0 et SI comme produit partiel PP1 et comme produit modulo MM1. Pour tous les cycles restants sauf le cycle de correction de valeur initiale de l'accumulateur 150, les produits partiels PP1 et les produits modulo MM1 sont sélectionnés en conformité avec la méthode de codage indiquée dans les tables de vérité des figures 11 et 14.
Les valeurs -A et -M sélectionnées comme produits partiels et modulo peuvent être obtenues par inversion des bits. Les valeurs +2A et +2M peuvent être obtenues par décalage de A et de M vers la gauche chacun d'un bit, et la valeur -2A peut être obtenue par inversion binaire après décalage de A vers la gauche d'un bit. Les résultats des produits partiels et modulo obtenus au moyen d'un décalage vers la gauche et d'opérations d'inversion binaire, peuvent être appelés nombres en complément à 1. Le multiplieur 10 des exemples de mode de réalisation de l'invention peut par exemple être configuré pour effectuer une opération en utilisant des nombres en complément à 2. Le nombre en complément à 2 est identique au nombre obtenu par addition d'un "1" au nombre en complément à 1. Le signal d'inversion de produit partiel NEG_PP et le signal d'inversion de produit modulo NEG_MM peuvent être utilisés pour représenter des nombres en complément à 1, -A, -2A et -M sous la forme de leurs nombres en complément à 2. En d'autres termes, le signal d'inversion de produit partiel NEG_PP devient un "1" lorsque le produit partiel PP est égal à -A ou -2A, mais devient égal à "0" lorsque le produit partiel PP est égal à 0, +A ou +2A. Le signal d'inversion de produit modulo NEG_MM est mis à "1" si le produit modulo MM1 est égal à - M, mais est mis à "0" lorsque le produit modulo MM' est égal à SI, 0, +M ou +2M.
Le multiplieur de Montgomery des exemples de modes de réalisation de l'invention peut être configuré sous la forme d'une matrice de calcul, comme illustré par la figure 1, pour effectuer un calcul à précisions multiples. Par ailleurs, les données internes de l'exemple de multiplieur de Montgomery peuvent être représentées avec des longueurs binaires optimisées sans débordement des données, afin d'éviter ainsi qu'un nombre trop grand de bits leur soit inutilement affecté. L'analyse mathématique suivante peut indiquer des exemples de gammes de valeurs résultant du calcul pour chaque ligne de la matrice de calcul, celles-ci déterminant donc le nombre de bits exigés pour représenter les résultats de calcul pour chaque ligne. Parmi les lignes de la matrice de calcul représentée sur la figure 1, toutes les lignes, à l'exception de la dernière ligne, utilisent le multiplicande de A, le multiplicateur B et le module M de la façon suivante.
[Équation 3] M: 2n 1 + 1 < M < 2n - 1 A: -M < A < +M B. -2c+w/2-1 B < 2c+ w/2-1 Un résultat intermédiaire So généré à partir de la première ligne (figure 1, ROW_O) est défini par l'équation 4.
[Équation 4] A.B+Q.M So =
R
Dans l'équation 4, R représente une constante égale à 2c+w/2. Comme l'exemple de multiplieur de Montgomery décrit ici est associé à une architecture à radical-4, le multiplieur traite 2 bits du multiplicateur B lors de chaque cycle. De plus, la valeur de Q utilisée lors de chaque cycle est l'une quelconque des valeurs {-1, 0, +1, +2). De plus, les valeurs maximum et minimum de Q dans une ligne donnée peuvent être définies de la façon suivante par l'équation 5.
[Equation 5] Max(Q) = (+2) .20+ (+2) -22+ (+2) .24 + . . + (+2) . 2e+w/22 c+w/2 1 4 2 -1 2 (2c+w/2 _1) 4 1 3 Min(Q) = (-1) .20+(-1) .22+(-1) .24 + . . +(-1) .2c+w/2-2 = 2.
c+w/2 1 4 ] 1 (2c4 i2 _ 1) 4 1 3 Dans les conditions indiquées ci-dessus, les valeurs maximale et minimale du résultat intermédiaire So peuvent 5 être obtenues conformément à l'Equation 6.
[Equation 6] M (2c+w2 _1)+2 w/2 -1).M 1 2 Max(So)= 2c+w3-1 2+'3/ M=6 M M ( 2+w/2-1 _ 1) 1.
Min(S) = 3 0 2 c+wiz-1c+w/2 1) É M 2._ 3ÉM= 5 ÉM Comme le module M est composé de n bits, le nombre de bits nécessaires pour la représentation par un nombre en 15 deçà des limites décrites ci-dessus est égal à n+2 bits, y compris un bit de signe.
Un résultat intermédiaire S1 résultant de la seconde ligne (Figure 1, ROW_l) est obtenu avec le résultat intermédiaire précédent So de la première ligne. Le calcul conduisant à S1 peut être tel que décrit dans l'équation 7 ci-après.
[Equation 7] So+AÉB+QÉM
_
R
Les valeurs maximale et minimale de S1 peuvent être définies par l'équation 8 ci-après.
[Equation 8] M+MÉ(2+wi2-1 -1)+ 3.(2'wiz 1)ÉM Max(S,) = 6 2+w12 7 1 1 2 _' 1 \ 7 =C6.2+wiz+2+3J M 6.2+wi2+1 ÉM=6ÉM -6 ÉM+MÉ( 2+w'2-' -1)_ 3 É(2'+w'2 -1)ÉM Min(SI) = 2+w/2 1 6 2+w/z-12--3-).M=-- 2c'/2+1JÉM= 6ÉM Le nombre de bits permettant de représenter le nombre dans l'intervalle établi par l'équation 8 ci-dessus est aussi égal à n+2 bits. De même, un résultat intermédiaire S2 de la troisième ligne (figure 1, ROW__2) peut également être représenté sur n+2 bits.
Par ailleurs, une valeur obtenue en simple précision, pour laquelle un ensemble unique d'un résultat et d'une ligne existe pour la dernière ligne en multi-précision, peut être représentée sur n+1 bits, y compris un bit de signe. Cette caractéristique peut être vérifiée par le mode opératoire décrit ci-après.
Les intervalles du multiplicande A, du multiplicateur B et du module M peuvent être fixés au moyen de l'équation 25 9 ci-après.
[Equation 9] M: 2n-I+1 < M <2n-1 2cp-I+1 M < 2cp-I A: M <_ A < +M 30 B: M B < +M Le résultat final S peut être résumé de la façon représentée par l'Equation 10.
[Equation 10] A.B+Q.M S=
R
Dans l'équation 10, le paramètre R est une constante égale à 2 (c+w/2)p. Les valeurs maximale et minimale de Q 10 indiquées dans l'équation 10 peuvent être définies par les expressions indiquées dans l'Equation 11.
[Equation 11] Max(Q) = (+2) .2 +(+2) .22+(+2) .24 + (c+w/2)p = 2É 4 2 -1 2.(2(c+w/2)p -1) 4 1 3 Min(Q) = ( 1) .2 +(-1) .22+(-1) _24 + + (+2) . 2 (c+w/2) . p-2. + ( 1) .2(c+w/2) .p-2 (c+w/2)p 4 2 -1 4 1 3 (2(c+w/2)p -1) Par conséquent, les valeurs maximale et minimale du résultat final S peuvent être obtenues conformément à l'équation 12 suivante.
[Equation 12] M (2 _1)+.(2 (c+wl2) p -1) M 2 Max(S) = 2 (c.,./2 (2(w12)p + 3}m= +M M. ( 2 p -1) 1. (2(c+w/2)p -1) É M 3 1 1 Min(S) = 2<<., /2 É M (wlz)p - - = M 2 3/ Le nombre de bits permettant de représenter les nombres se situant dans la gamme des conditions indiquées précédemment est égal à n+1.
Comme indiqué précédemment, dans le mode de fonctionnement multiprécision, un dépassement de capacité des données peut être produit audelà de la gamme de +M pour les résultats intermédiaires déterminés à partir des autres lignes (lignes internes ROW_0 à ROW_2 de la figure 1), mais les résultats intermédiaires concernant la dernière ligne (ROW_3 de la figure 1) sont conditionnés de façon à être proches de la valeur maximale. Cette condition correspond à une valeur de Q sélectionnée lors de chaque cycle, qui est voisine de +2 à proximité de la position de poids fort, et à un signe du multiplicande A qui est identique au signe de la plage de la valeur B du multiplicateur qui est utilisée dans la ligne interne qui lui correspond.
Un résultat de calcul pour chaque ligne est représenté sur n+2 bits. Cependant, comme n est un multiple entier de w et comme la mémoire 40 est dimensionnée sous la forme d'un multiple entier de w, il n'est pas efficace de stocker les deux bits supplémentaires dans la mémoire 40. Par conséquent, conformément aux exemples de modes de réalisation de l'invention, les n bits de poids faible parmi les n+2 bits peuvent être stockés dans la mémoire 40 et les deux bits restants (c'est-à-dire le bit de signe qui est le bit de poids le plus fort (MSB), et le second MSB) sont stockés dans le registre interne (figure 3, SFR 13) du multiplieur de Montgomery 10. Les deux bits de poids supérieur peuvent être appelés SIGN_S MS1B_S. Après avoir terminé le traitement de calcul jusqu'à la dernière ligne, le bit de signe SIGN_S et le second bit de poids le plus fort MS1B_S ont la même valeur. Cependant, après la fin du traitement de calcul concernant les lignes internes, le second bit de poids fort peut être à "1", le bit de signe étant mis à "0".
Le trajet de données 100 du multiplieur de Montgomery, conformément à un exemple de mode de réalisation de l'invention, peut en outre comporter des registres à décalage 106, 115, 116 et 180. La longueur binaire acceptée dans chacun des registres à décalage 106, 115, 116 et 180 est égale à w, et ces bits peuvent être décalés vers la droite dans chaque registre de 2 bits par cycle. Les registres 106 et 115 peuvent être des registres à décalage à entrée parallèle et à sortie série, alors que les registres 116 et 180 peuvent être des registres à décalage à entrée série et à sortie parallèle.
Le produit modulo MM' qui est généré lors de chaque cycle peut n'être assigné au résultat précédent SI que lors du cycle de correction de valeur initiale de l'accumulateur 150. Le MM1 généré lors de chaque cycle peut être sélectionné par la valeur q1M ayant été déterminée par la table de vérité représentée sur la figure 11 pour les autres cycles. Dans le cas présent, qI est l'un des nombres {-1, 0, 1, 2}.
Pour les lignes représentées sur la figure 1, les premiers calculs de multiplication unités CSAO.0, CSA1.0, CSA2.0, et CSA3.0 (appelées ciaprès "Boîte Gen-Q") peuvent être effectuées avec le calcul de g'. La valeur déterminée de qI peut être stockée dans la mémoire 40 afin de réutiliser qi dans des calculs de multiplication unités sur la même ligne. L'enregistreur de Montgomery 110 représenté sur les figures 8A à 8C génère une valeur QO[1:0] avec un signe à deux (2) bits pour tous les cycles, à l'exception du cycle de correction de valeur initiale de l'accumulateur 150 pour les premiers calculs de multiplication unités de la Boîte Gen-Q de chaque ligne, puis stocke les valeurs QO[1:0] dans le registre à décalage 116.
La figure 19 illustre une configuration détaillée du registre à décalage 116, c'est-à-dire QO_SIPO_REG[15:0]. Le registre à décalage 116 déplace des bits de données vers la droite de 2 bits par cycle et stocke QO[1:0], qui est fourni par l'enregistreur de Montgomery 110, aux positions à 2 bits de poids plus élevé. Le registre à décalage 116 transfère ces données (c'est-à-dire QO_SIPO_REG[31:0]) à la mémoire 40 chaque fois qu'une nouvelle donnée d'une longueur de mot y est introduite.
La figure 20 illustre une configuration détaillée du registre à décalage 115, c'est-à-dire QI_PISO_REG[15:0]. La valeur SO stockée dans la mémoire 40 est transférée au registre à décalage 115 par unités ayant la longueur d'un mot w. Les valeurs de poids faible QI[1:0] du registre à décalage 115 sont fournies à l'enregistreur de Montgomery 110. Le registre à décalage 115 reçoit de nouvelles données de la mémoire 40 en réponse à un signal d'horloge lorsque le signal de commande de décalage SFT_QI_PISO est à "0", mais décale ses données vers la droite de 2 bits lorsque le signal de commande de décalage SFT_QI_PISO est à "1".
Pour tous les calculs de multiplication unités restants CSAO.1 CSA0.3, CSA1.1 -- CSA1.3, CSA2.1 CSA2.3 et CSA3.1 CSA3.3 (appelés ci-après "Boîte Gen-S"), à l'exception des premiers calculs de multiplication unités de la Boîte Gen-Q pour chaque ligne, les résultats de multiplication à 2 bits SO[1:0] (qui représentent une somme de l'accumulateur 150) sont générés pour chaque cycle, à l'exception du cycle de correction de valeur initiale de l'accumulateur 150. Les valeurs SO[1:0] sont stockées séquentiellement dans le registre à décalage 180.
La figure 21 illustre une configuration détaillée du registre à décalage 180 permettant de stocker une somme SO[1:0] de l'accumulateur 150. Le registre à décalage 180 déplace ces données vers la droite de 2 bits par cycle en réponse à un signal d'horloge, et stocke des valeurs SO[1:0] de l'accumulateur 150 aux positions à 2 bits de poids plus élevé. Le registre à décalage 180 décale ses données SO_SIPO_REG[31:0] vers la mémoire 40 chaque fois qu'une nouvelle donnée ayant une longueur de mot y est introduite.
La figure 22 illustre un circuit générateur SPP 170 permettant de générer des données itératives de produit partiel SPPI[1:0] utilisées dans l'enregistreur de Montgomery 110. Les données itératives de produits partiels SPPI [ 1: 0] peuvent être déterminées sur la base d'une somme stockée dans l'accumulateur 150, des deux bits de poids faible ACC_S_REG[1:0] des registres de somme 620 et ACC_C_REG[1:0] des registres de report 630, de la valeur ACC_L_REG[2:0] du registre de valeur inférieure 650, des deux bits de poids faible PPI[1:0] du produit partiel et du signal de commande de décalage SHIFT_ACC pour l'entrée de contreréaction de l'accumulateur 150. Les valeurs ACC_S_REG[1:0], ACC_C_REG[1:0] , et ACC_L_REG[2:0] peuvent être sommées par un additionneur à 2 bits 801. La valeur sommée provenant de l'additionneur à 2 bits 801 est sommée avec PP1[1:0] par un additionneur à 2 bits 802. Un additionneur à 2 bits 803 somme PPI[1:0] avec ACC_L_REG[1:0]. Un multiplexeur 804 sélectionne la sortie de l'additionneur 802 lorsque le signal de commande de décalage SHIFT_ACC est à un niveau logique "0", mais délivre en sortie les données de produit partiel itératives SPPI[1:0] en sélectionnant la sortie de l'additionneur 803 lorsque le signal de commande de décalage SHIFT_ACC et à un niveau logique "1". Comme décrit précédemment, les données de produit partiel itératives SPP1[1:0] peuvent être fournies à l'enregistreur de Montgomery 110. Il n'existe pas de limite de taille (ou de longueur) de bits dans les exemples de modes de réalisation de l'invention. Par exemple, les données de produit partiel itératives SPP1 peuvent avoir plus de 2 bits, tout comme d'autres éléments de ce mode de réalisation.
La figure 23 illustre la configuration d'un circuit d'un bloc 160 de calcul (CPA) d'additionneur avec propagation de report (CPA) conformément à un exemple de mode de réalisation de l'invention. Dans cet exemple, c=256 et w=32. Dans le bloc de calcul CPA 160, les valeurs CPAO, CPA1, CPA2 et CPA3 représentées sur la figure 1, peuvent être calculées séquentiellement. Un multiplexeur 901 reçoit des valeurs inférieures ACC_C_REG[255:0] en tant que longueur de plage, parmi des bits de report stockés dans un registre de report 630 de l'accumulateur 150. Un multiplexeur 902 délivre en entrée une somme S[255:0] stockée dans un registre de somme 620 de l'accumulateur 150. Les multiplexeurs 901 et 902 sélectionnent 32 bits séquentiellement depuis le bit de poids faible, parmi 256 bits d'entrée, en réponse à un signal de sélection d'entrée SEL_CPA_IN[2:0]. Les sorties des multiplexeurs 901 et 902 peuvent être stockées respectivement dans des registres 903 et 904. Le signal de sélection d'entrée SEL_CPA_IN[2:0] peut varier de "0000" à "1111". Par conséquent, le bloc 160 permet de traiter un calcul sur 256 bits en effectuant huit cycles CPA itératifs par unités de 32 bits.
Un additionneur à propagation du report 905 additionne une entrée de report C_IN d'un multiplexeur 920 à des valeurs CPA_A_REG[31:0] et CPA_B_REG[31:0] qui sont stockées dans les registres 903 et 904. Une fois une opération d'addition avec sauvegarde du report (CSA) terminée pour chaque ligne, une valeur résultante provenant de l'accumulateur 150 est égale à ACC_S_REG[256:0] + ACC_C_REG[256:0] + ACC_L_REG[2], cette valeur devant être stockée dans la mémoire 40 après avoir été convertie en un nombre unique par sommation au moyen du calcul CPA. Par conséquent, l'entrée de report C_IN lors du premier cycle (c'est-à-dire SEL_CPA_IN[2:0]="000") du calcul CPA est égale à ACC_L_REG[2], tandis que l'autre entrée de report C_IN lors des cycles restants (c'est-à-dire de SEL_SPA_IN[2:0] _ "001" à SEL_CPA_IN[2:0] = "111") est une sortie de report C_OUT du cycle de calcul précédent. La sortie de report C_OUT de l'additionneur à propagation du report 905 peut être stockée dans un registre 906.
Un nouveau bit de signe SIGN_S pour une valeur résultante provenant d'une ligne est obtenu en effectuant une opération OUX avec une sortie de report C_OUT (qui est générée après addition du report ACC_C_REG[255:0] à la somme ACC_S_REG[255:0] au moyen des opérations itératives dans le bloc CPA 160) et avec ACC_C_REG[256] et ACC_S_REG[256]. Le bit de signe SIGN_S peut être transformé en la valeur venant d'être calculée sous le contrôle d'un signal UPD_SIGN_S. Le signal de commande UPD_SIGN_S provoque la transformation du second bit de poids fort MS1B_S en la valeur venant d'être calculée.
La figure 24 illustre une caractéristique consistant à maintenir un demimot de poids le plus fort d'un mot donné dans l'accumulateur 150 tout en passant à un calcul CPA à partir du dernier calcul CSA de chaque ligne dans un mode mufti-précision à nombre pair de multiplications. Dans le cas d'un mode multi-précision à nombre pair de multiplications (c'est-à- dire d'un mode à double précision ou d'un mode à quadruple précision), le dernier demi-mot (c'est-à-dire 16 bits lorsque w=32) des bits de sortie de l'accumulateur 150 est maintenu dans le registre 180 et n'est pas transféré à la mémoire 40, lorsqu'on passe à l'étape de calcul CPA à partir du dernier calcul CSA pour chaque ligne. Cet effet est illustré sur la figure 24. Comme illustré sur la figure 24, le multiplieur fonctionnant en mode à quadruple précision répète quatre fois le cycle de calcul unité CSA. Une longueur de donnée de chaque calcul de multiplication unité peut être définie par l'équation 13 suivante (où c=256 et w=32).
[Equation 13] c'= c+w/2=(c/w)*w+w/2=(256/32)*32+32/2=8*32+16=272 Une sortie du dernier demi-mot (16 bits) du second calcul unité CSA1 combinée ou fusionnée avec le premier demi-mot du troisième calcul unité CSA2 compose un mot complet. Le mot complet est stocké dans la mémoire 40. Par ailleurs, une sortie du dernier demi--mot du quatrième calcul unité CSA3 reste dans le registre 180 et n'est pas transféré à la mémoire 40 en raison du fait qu'il ne reste plus de bloc de calcul unité. Pour placer de façon contrainte la donnée de demi-mot qui reste dans le registre 180 dans la mémoire 40 pendant le calcul CPA, des signaux de commande IS 1ST CPA WORD et IS ODD PREC sont ici utilisés.
En ce qui concerne à nouveau la figure 23, dans le mode de précision à nombre pair de multiplications (IS _ODD_PREC="0"), les 16 bits de poids faible, en tant que résultat fourni en sortie par l'additionneur à propagation de report 905 lors du premier cycle (IS_1ST_CPA_WORD = "1") du calcul CPA, composent un mot complet (à 32 bits) avec les 16 bits de poids fort S0_SIPO_REG[31:16] stockés dans le registre 180. Le mot complet est stocké dans le registre 925. Les 16 bits de poids fort d'un résultat délivré en sortie par l'additionneur à propagation du report 905 sont stockés dans le registre 922.
Lors des cycles restants, les 16 bits de poids faible, parmi les bits de sortie de l'additionneur à propagation du report 905, sont stockés dans le registre 925 et sont fusionnés avec les 16 bits de poids fort ayant été stockés dans le registre 922 au cours du cycle précédent. Les données du registre 925 sont donc stockées dans la mémoire 40 lors de chaque cycle.
La figure 25 est une table de vérité destinée à illustrer la forme de formules logiques pour des signaux d'entrée/sortie donnés de l'enregistreur de Booth 140. Comme décrit précédemment à propos de la figure 14, l'enregistreur de Booth 140 peut être constitué de circuits logiques combinatoires. Les formules logiques établies entre les signaux d'entrée et de sortie de l'enregistreur de Booth 140 peuvent être configurées de la façon illustrée sur la figure 25.
Sur la figure 25, A[1] et A[0] sont les deux bits de poids faible du multiplicande A utilisé dans un calcul de multiplication unité courant. Par conséquent, les deux bits de -A sont {A[1] oux A[0], A[0]}, et les deux bits de poids faible de +2A et -2A sont {A[0], 0).
Lorsqu'un signal de commande de produit partiel forcé FORCE_PP[1:0] est à "11", la valeur du produit partiel PP1 est déterminée par les valeurs des multiplicateurs B1, BO et BR. Dans le cas contraire, lorsque le signal de commande de produit partiel forcé FORCE_PP[1:0] est à "01", "10", et "00", le produit partiel PP1 est respectivement contraint d'être égal à +A, -A et O. Lors du cycle de correction de valeur initiale de l'accumulateur 150 pour chaque calcul de multiplication unité représenté sur la figure 1, la valeur résultante SI provenant de la ligne précédente est "empilée" dans l'accumulateur. Pour que cela se produise, le produit partiel PP1 est sélectionné comme étant égal à "0" et le produit modulo MM1 est sélectionné comme étant la valeur résultante SI provenant de la ligne précédente. Dans le cycle de correction de valeur initiale de l'accumulateur 150, le signal de sélection de produit partiel forcé FORCE_PP[1:0] est mis à "11" pour forcer la valeur du produit partiel PP1 à "0".
Avec le multiplieur de Montgomery 10 des exemples de modes de réalisation de l'invention, un résultat d'exponentiation modulaire peut être représenté par un résidu de Montgomery égal à "XR mod M". Cependant, le résultat souhaité est un résidu normal qui est égal à "X mod M". Par conséquent, le signal de commande de produit partiel forcé FORCE_PP[1:0] peut être utilisé pour transformer le résidu de Montgomery en le résidu normal.
Par exemple, il est possible d'obtenir le résidu normal en reprenant la multiplication de Montgomery et en fixant à "+1" le multiplicateur B et à une valeur résultante le multiplicande A de la multiplication de Montgomery. A cet effet, le signal de commande de produit partiel forcé FORCE_PP[1:0] peut n'être mis à "01" que pendant le premier cycle faisant suite au cycle de correction de valeur initiale lors de chaque calcul unité pour la première ligne de la matrice de calcul, ce qui transforme le produit partiel PP1 en +A. Dans tous les cycles restants, le signal de commande de produit partiel forcé FORCE_PP[1:0] est mis à "11" pour "forcer" le produit partiel PP1 à 0.
Les entrées B1, BO et BR de l'enregistreur de Booth 140 sont fournies par le registre de multiplicateur 106. Se référant à la figure 8C, l'entrée A[1:0] peut être sélectionnée parmi AX_PIPO_REG[1:0] ou AY_PIPO_REG[1:0].
L'entrée SEL_PP_D[1:0] est une version décalée du signal de sélection SEL_PP; le retard est dû à un registre à verrouillage FF1 d'un circuit à retard 141 (également appelé "registre pipeline" 141), comme illustré sur la figure 8B. Le signal de validation de produit partiel EN_PP et la sortie SEL_PP[1:0] de l'enregistreur de Booth 140 sont fournis au générateur de produit partiel 130. Le signal d'inversion de produit partiel NEG_PP est fourni à l'accumulateur 150, et le produit partiel PPI[1:0] est délivré en sortie par l'enregistreur de Booth 140 au générateur SPP 170, comme illustré sur la figure 22.
La figure 26 est une table de vérité illustrant la forme de formules logiques pour des signaux d'entrée/sortie donnés de l'enregistreur de Montgomery 110. L'enregistreur de Montgomery 110 peut également être composé de circuits logiques combinatoires. Des exemples de formules logiques entre les nouveaux signaux d'entrée et de sortie de l'enregistreur de Montgomery 110 sont illustrés sur la figure 26. Sur la figure 26, une méthode de codage de qI (QI[1:0] et QO[1:0]) peut être résumée par l'équation 14 suivante.
[Equation 14] MM = 0 -+ qz = "00" MM = +M -i qi = " 01 " MM = -M qI = "10" MM = +2M -i qI = "11" Sur la figure 26, M1 représente la seconde valeur inférieure du module M. Lorsque le signal de commande de produit modulo forcé FORCE_MM[1:0] est à "11", la valeur du produit modulo MM1 est déterminée par les données de produit partiel itératif SPP[1:0] et M1. Cependant, le produit modulo MMI peut être sélectionné de façon forcée comme étant la valeur résultante SI provenant de la ligne précédente lorsque le signal de commande de produit modulo forcé FORCE_MM[1:0] est à "10". Le produit modulo MM1 peut être généré comme étant une valeur sélectionnée par QI[1:0] lorsque FORCE_MM[1:0] est à "01".
Pour tous les calculs de multiplication unités de la matrice de calcul, la valeur du produit modulo MMI est sélectionnée avec la valeur résultante SI provenant de la ligne précédente lors du cycle de correction de valeur initiale de l'accumulateur 150. Comme il est nécessaire de sélectionner le produit modulo MMI qui peut être adopté pour les données de produit partiel itératif SPP[1:0] et Ml lors du premier calcul unité (c'est-à-dire pour la Boîte Gen-Q) pour chaque ligne de la matrice de calcul, le signal de commande de produit modulo forcé FORCE_MM[1:0] est mis à "00" lors de tous les cycles restants, sauf le cycle de correction de valeur initiale de l'accumulateur 150. Pendant le cycle de correction de valeur initiale, qI est calculé puis est délivré en sortie en tant que QO[1:0], pour être stocké dans la mémoire 40 via le registre 116. Lors des calculs unités "restants" (c'est-à-dire pour la Boîte Gen-S), à
l'exception du premier calcul unité (c'est-à-dire de la Boîte Gen-Q) pour chaque ligne de la matrice de calcul, le produit modulo MMI est sélectionné en réutilisant la valeur (III (c'est-à-dire l'entrée QI[1:0]), ayant été stockée dans la mémoire 40 pendant le premier calcul unité de la Boîte Gen-Q. L'entrée QI[1:0] peut être réutilisée en mettant à "01" le signal de commande de produit modulo forcé FORCE_MM[1:0].
Le trajet des données de multiplieur 100, conformément à un exemple de mode de réalisation de l'invention, permet d'aider au calcul de multiplication normal en plus du calcul de multiplication de Montgomery. Pour le calcul de multiplication normal, le signal de commande de produit modulo forcé FORCE_MM[1:0] peut également être utilisé ici. Cependant, comme une multiplication normale n'utilise pas de module, il n'existe pas de produit modulo MM1. Par conséquent, le signal de commande de produit modulo forcé FORCE_MM[1:0] n'est mis à "10" que pendant le cycle de correction de valeur initiale de l'accumulateur 150 pour chaque calcul unité, ce qui a pour effet de fixer le produit modulo MM' à la valeur résultante SI provenant de la ligne précédente. Au cours des cycles restants, le signal de commande de produit modulo forcé FORCE_MM[1:0] est mis à "00" pour forcer le produit modulo MM1 à 0.
Se référant à présent à la figure 8A, les données de produit partiel itératif SPP[1:0] délivrées en entrée à l'enregistreur de Montgomery 110 sont fournies par le générateur SPP 170. M1 est utilisé dans le premier calcul unité (c'est-à-dire la Boîte Gen-Q), et est sélectionné parmi les bits de poids faible des valeurs de modules M stockées dans le registre 102 et le second bit de poids faible stocké dans le registre 103. De plus, QI[1:0] est constitué des deux bits de poids faible stockés dans le registre 115. L'entrée SEL_MM_D[1:0] est retardée d'un cycle par rapport à SEL_MM[1:0] à travers la bascule 111. La sortie QO[1:0] de l'enregistreur de Montgomery 110 est fournie au registre 116. Le signal de sélection de produit modulo SEL_MM[1:0] et le signal de validation de produit modulo EN_MM sont fournis au générateur de produit modulo 120. Le signal d'inversion de produit modulo NEG_MM est fourni à l'accumulateur 150.
Se référant à la figure 8B, un éliminateur de défaut 114 peut être prévu pour réduire la consommation d'énergie en éliminant les défauts apparaissant sur les signaux de sortie SEL_MM[1:0], EN_MM et NEG_MM. L'éliminateur de défaut 114 peut être composé de registres à verrouillage ou de bascules, et peut être mis en fonctionnement par une horloge ou par une horloge inversée utilisée dans un autre registre ou une autre bascule du multiplieur de Montgomery 10. L'utilisation de l'éliminateur de défaut 114 peut être spécifique de l'application. Si une application nécessite une vitesse de fonctionnement plus élevée plutôt qu'une consommation d'énergie réduite, il est possible de réduire le biais d'un trajet critique en omettant l'éliminateur de défaut 114 dans le multiplieur de Montgomery 10.
Le registre pipeline 141 est prévu pour augmenter la fréquence de fonctionnement au moyen de registres pipelines à 2 étages. Le registre de multiplicateur 106 et l'enregistreur de Booth 140 peuvent être mis en fonctionnement en avance d'un cycle sur les autres blocs.
Un signal de commande USE_X_REG peut commander de façon commune les composants de multiplexeur 142 sélectionnant pour l'enregistreur de Booth, modulo 120, le générateur de multiplexeur 113 et la bascule signal M1 devant être délivré en circuits suivants: le le signal d'entrée A[1:0] le générateur de produit produit partiel 130, le 112 qui sélectionnent le entrée à l'enregistreur de Montgomery 110. Dans le cas présent, du fait de l'opération de type pipeline, le multiplexeur 142 sélectionnant le signal d'entrée A[1:0] de l'enregistreur de Booth 140 est le seul à utiliser directement le signal de commande USE_X_REG alors que les autres circuits 120, 130, 112 et 113 acceptent un signal retardé d'un cycle par rapport au signal de commande USE_X_REG, comme illustré sur la figure 8B.
Comme décrit ci-dessus, les exemples de modes de réalisation de l'invention permettent d'assurer un calcul de multiplication à précision multiple au moyen d'un multiplieur de Montgomery à échelle modulable. De plus, le multiplieur est capable d'effectuer un calcul de multiplication normal et un calcul de multiplication de Montgomery. L'exemple de multiplieur de Montgomery peut être configuré pour transformer un résidu de Montgomery en un résidu normal au moyen d'un signal de commande de produit modulo forcé FORCE_MM[1:0].
Bien que la présente invention ait été décrite en référence à des exemples de modes de réalisation illustrés par les dessins annexés, elle n'est pas limitée à ceux-ci. Les spécialistes de la technique noteront que diverses substitutions, modifications et transformations peuvent être envisagées sans qu'ils s'écartent du cadre des exemples de modes de réalisation de l'invention.

Claims (53)

REVENDICATIONS
1. Multiplieur (10), comprenant: un générateur de produit modulo (120) sélectionnant l'un des modules à n bits -M, 0, M, 2M et un résultat de 5 ligne précédente SI en tant que produit modulo; un générateur de produit partiel (130) sélectionnant un multiplicande parmi l'un des multiplicandes -2A, -A, 0, +A et +2A en tant que produit partiel; et un accumulateur (150) empilant le produit modulo 10 sélectionné et le produit partiel.
2. Multiplieur (10) selon la revendication 1, caractérisé en ce que: M est formé d'une plage binaire étendue en entrée à l'instant courant parmi les modules à n bits; et A est formé d'une plage binaire étendue en entrée à l'instant courant parmi des multiplicandes à n bits.
3. Multiplieur (10) selon la revendication 2, caractérisé en ce que le résultat de ligne précédente est formé des bits correspondant aux plages étendues délivrées en entrée à l'instant courant du multiplicande et du module parmi des résultats de multiplication de la ligne précédente de l'accumulateur (150).
4. Multiplieur (10) selon la revendication 2, caractérisé en ce que le générateur de produit modulo (120) sélectionne le résultat de la ligne précédente en tant que produit modulo lors d'un cycle de correction de valeur initiale de l'accumulateur (150).
5. Multiplieur (10) selon la revendication 4, caractérisé en ce que le générateur de produit partiel (130) met à "0" le produit partiel lors du cycle de correction de valeur initiale de l'accumulateur (150).
6. Multiplieur (10) selon la revendication 4, caractérisé en ce que le cycle de correction de valeur initiale représente un premier cycle d'un calcul de multiplication unité utilisant les bits de plage étendue délivrés en entrée à l'instant courant du multiplicande à n bits et du module à n bits.
7. Multiplieur (10) selon la revendication 5, caractérisé en ce que le cycle de correction de valeur initiale représente un premier cycle d'un calcul de multiplication unité utilisant les bits de plage étendue délivrés en entrée à l'instant courant du multiplicande à n bits et du module à n bits.
8. Multiplieur (10) selon la revendication 1, 10 caractérisé en ce que le module -M est obtenu en inversant le module M.
9. Multiplieur (10) selon la revendication 1, caractérisé en ce que le module 2M est obtenu en décalant le module M.
10. Multiplieur (10) selon la revendication 2, comprenant en outre: un registre de module (102, 103) stockant des bits délivrés en entrée à l'instant courant du module à n bits (M) ; un registre de multiplicande (104, 105) stockant des bits délivrés en entrée à l'instant courant du multiplicande à n bits (A) ; et un registre de multiplicateur (106) stockant des bits délivrés en entrée à l'instant courant d'un multiplicateur 25 à n bits (B).
11. Multiplieur (10) selon la revendication 10, caractérisé en ce que le registre de module (102, 103) et le registre de multiplicande (104, 105) sont chacun mis en oeuvre sous la 30 forme de registres à c'+1 bits, et c' est un entier positif qui représente une longueur binaire d'une plage étendue d'au moins l'un du multiplicande à n bits et du module à n bits, c' étant inférieur ou égal à n.
12. Multiplieur (10) selon la revendication 10, caractérisé en ce que le registre de module (102, 103) comporte en outre une pluralité de sousregistres (200-216) ayant chacun la taille d'un demi-mot, et un registre de signe à 1 bit (220).
13. Multiplieur (10) selon la revendication 12, comprenant en outre un bloc d'interface mémoire (12) pour stocker des données de longueur de mots, caractérisé en ce que: la pluralité de sous-registres (200-216) du registre de module (102, 103) comporte des sous-registres de numéros pairs (200, 202, ..., 216) et des sous-registres de numéros impairs (201, 203, ..., 215), les sous-registres de numéros pairs (200, 202, ..., 216) sont configurés pour stocker des demi-mots de poids faible des données de longueur de mots fournies par le bloc 15 d'interface mémoire (12), et les sous-registres de numéros impairs (201, 203, 215) sont configurés pour stocker des demi-mots de poids fort de données de longueur de mots fournies par le bloc d'interface mémoire (12).
14. Multiplieur (10) selon la revendication 10, caractérisé en ce que le registre de multiplicande (104, 105) comporte en outre une pluralité de sous-registres (200-216) ayant chacun la taille d'un demi-mot, et un registre de signe à 1 bit (220).
15. Multiplieur (10) selon la revendication 14, comportant en outre un bloc d'interface mémoire (12) pour stocker des données de longueur de mots, dans lequel: la pluralité de sous-registres (200-216) du registre de multiplicande (104, 105) comporte des sous-registres de numéros pairs (200, 202, ..., 216) et des sous-registres de numéros impairs (201, 203, .
, 215), les sous-registres de numéros pairs (200, 202, 216) sont configurés pour stocker des demi-mots de poids faible des données de longueur de mots fournies par le bloc 35 d'interface mémoire (12), et les sous-registres de numéros impairs (201, 203, 215) sont configurés pour stocker des demi-mots de poids fort de données de longueur de mots fournies par le bloc d'interface mémoire...CLMF:
16. Multiplieur (10) selon la revendication 10, comprenant en outre: un registre à décalage (116) stockant les bits d'entrée du multiplicateur à n bits en tant que longueur de mots (w) égale ou inférieure à une longueur de plage (c), avec w c <- n, et décalant les données de deux bits.
17. Multiplieur (10) selon la revendication 16, caractérisé en ce que le sélecteur de produit partiel (12-1, 12-3) génère un signal de sélection de produit partiel à partir de trois bits (B0, B1, BR) des bits délivrés en entrée à l'instant courant du multiplicateur à n bits et sélectionne l'un des bits d'entrée A, 2A, -A et -2A du multiplicande à n bits en tant que produit partiel.
18. Multiplieur (10) selon la revendication 17, caractérisé en ce que le multiplicande 2A est obtenu en décalant le multiplicande A.
19. Multiplieur (10) selon la revendication 17, caractérisé en ce que le multiplicande -A est obtenu en inversant le multiplicande A.
20. Multiplieur (10) selon la revendication 17, 25 caractérisé en ce que le multiplicande -2A est obtenu en inversant et en décalant le multiplicande A.
21. Unité de calcul (1), comprenant: une mémoire (40) ; un hôte (20) stockant un multiplicande A, un multiplicateur B et un module M dans la mémoire (40) ; et le multiplieur (10) selon la revendication 1 effectuant un calcul de multiplication de Montgomery avec le multiplicande, le multiplicateur et le module stockés sous le contrôle de l'hôte (20), et stockant un résultat de calcul du calcul de multiplication de Montgomery dans la mémoire (40).
22. Unité de calcul (1) selon la revendication 21, caractérisée en ce que: M est formé à partir d'une plage étendue délivrée en entrée à l'instant courant de bits parmi les modules à 5 n bits, A est formé d'une plage étendue délivrée en entrée à l'instant courant de bits parmi des multiplicandes à n bits, et le résultat de la ligne précédente est formé de bits 10 correspondant aux plages étendues délivrées en entrée à l'instant courant du multiplicande et du module parmi des résultats de multiplication de la ligne précédente de l'accumulateur (150).
23. Unité de calcul (1) selon la revendication 21, 15 caractérisée en ce que le sélecteur de produit modulo (12-1, 12-3) lit le résultat de ligne précédente SI et une partie du module à n bits depuis la mémoire (40) pour sélectionner l'un de SI, -M, 0, M et 2M en tant que produit modulo, et le sélecteur de produit partiel (12-1, 12-3) lit une partie du multiplicande à n bits pour sélectionner l'un de -2A, -A, 0, +A et +2A en tant que produit partiel, le module et les produits partiels sélectionnés étant empilés par l'accumulateur (150).
24. Unité de calcul (1) selon la revendication 21, caractérisée en ce que le multiplieur (10) effectue de façon itérative le calcul de multiplication de Montgomery jusqu'à ce que le multiplicande, le multiplicateur et le module soient lus depuis la mémoire (40).
25. Unité de calcul (1) selon la revendication 21, caractérisée en ce que: chacun du multiplicande, du multiplicateur et du module est à n bits, et le multiplieur (10) traite le multiplicande, le multiplicateur et le module lus sur c' bits lors de chaque cycle d'un calcul de multiplication unité, où c' représente la longueur binaire d'une plage étendue de bits du multiplicande, du multiplicateur et du module.
26. Unité de calcul (1) selon la revendication 25, caractérisée en ce que le multiplieur (10) lit le multiplicateur depuis la mémoire (40) sous la forme d'un bloc de w bits stockés dans un registre (106) dont la longueur est dimensionnée à w bits, w représentant une longueur de mots, traite le multiplicateur stocké dans le registre (106) 10 à w bits sur d bits en séquence, d représentant une longueur de chiffre d'un radical, et lit les w bits suivants du multiplicateur depuis la mémoire (40) après avoir traité les w bits stockés dans le registre (106) à w bits.
27. Unité de calcul (1) selon la revendication 26, caractérisée en ce que le multiplieur (10) comporte en outre une unité de commande générant un signal de commande de produit partiel forcé.
28. Unité de calcul (1) selon la revendication 27, caractérisée en ce que le sélecteur de produit partiel (12-1, 12-3) génère un signal de sélection de produit partiel et un signal de validation de produit partiel à partir de trois bits (B0, B1, BR) des bits délivrés en entrée à l'instant courant du multiplicateur lorsque le signal de commande de produit partiel forcé a une première valeur, et sélectionne l'un de A, 2A, -A, -2A et 0 en tant que produit partiel sur la base des bits délivrés en entrée du multiplicande (A).
29. Unité de calcul (1) selon la revendication 27, 30 caractérisée en ce que le sélecteur de produit partiel (12-1, 12-3) sélectionne le multiplicande (A) en tant que produit partiel afin d'obtenir un résidu normal lorsque le signal de commande de produit partiel forcé a une seconde valeur.
30. Unité de calcul (1) selon la revendication 27, caractérisée en ce que le sélecteur de produit partiel (12-1, 12-3) sélectionne le nombre -A en tant que produit partiel en référence au multiplicande (A) lorsque le signal de commande de produit partiel forcé a une troisième valeur.
31. Unité de calcul (1) selon la revendication 27, caractérisée en ce que le signal de commande de produit partiel forcé a une quatrième valeur lors du cycle de correction de valeur initiale de l'accumulateur (150), et le sélecteur de produit partiel (12-1, 12-3) sélectionne 0 en tant que produit partiel lorsque le signal de commande de produit partiel forcé a une quatrième valeur.
32. Unité de calcul (1) selon la revendication 29, caractérisée en ce que le sélecteur de produit partiel (12-1, 12-3) sélectionne la valeur -A en tant que produit partiel en référence au multiplicande (A) lorsque le signal de commande de produit partiel forcé a une troisième valeur.
33. Unité de calcul (1) selon la revendication 32, caractérisée en ce que le signal de commande de produit partiel forcé a une quatrième valeur lors d'un cycle de correction de valeur initiale de l'accumulateur (150).
34. Unité de calcul (1) selon la revendication 32, caractérisée en ce que le sélecteur de produit partiel (?) sélectionne 0 en tant que produit partiel lorsque le signal de commande de produit partiel forcé a une quatrième valeur
35. Unité de calcul (1) selon la revendication 27, caractérisée en ce que le multiplieur (10) génère des données de produit partiel itératif SPP1 en réponse à des valeurs de report, à des valeurs de somme et à des valeurs inférieures stockées dans l'accumulateur (150), le produit partiel, et à un signal de commande de décalage pour l'entrée de contre- réaction de l'accumulateur (150).
36. Unité de calcul (1) selon la revendication 35, caractérisée en ce que l'unité de commande génère en outre un signal de commande de produit modulo forcé.
37. Unité de calcul (1) selon la revendication 36, caractérisée en ce que le sélecteur de produit modulo génère un signal de sélection de produit modulo pour sélectionner l'un de -M, 0, M et 2M parmi les données itératives SPP1 et une seconde valeur de plus faible poids du module (M) lorsque le signal de commande de produit modulo forcé a une première valeur.
38. Unité de calcul (1) selon la revendication 36, caractérisée en ce que le signal de commande de produit 10 modulo forcé a une seconde valeur lors du cycle de correction de valeur initiale de l'accumulateur (150).
39. Unité de calcul (1) selon la revendication 38, caractérisée en ce que le sélecteur de produit modulo (12-1, 12-3) sélectionne le résultat de ligne précédente en 15 tant que produit modulo lorsque le signal de commande de produit modulo forcé a la seconde valeur.
40. Unité de calcul (1) selon la revendication 39, caractérisée en ce que le signal de sélection de produit modulo est généré en référence à une valeur QI lorsque le signal de commande de produit modulo forcé a une troisième valeur.
41. Unité de calcul (1) selon la revendication 40, caractérisée en ce que le signal de commande de produit modulo forcé a une quatrième valeur lors des cycles restants à l'exception du cycle de correction de valeur initiale.
42. Unité de calcul (1) selon la revendication 41, caractérisée en ce que le sélecteur de produit modulo (12-1, 12-3) sélectionne le multiplicande (A) en tant que produit partiel afin d'obtenir un résidu normal lorsque le signal de commande de produit partiel forcé a la seconde valeur.
43. Unité de calcul (1) selon la revendication 26, caractérisée en ce que chacun du multiplicande, du 35 multiplicateur et du module est à c' bits pour le calcul de multiplication unité, le calcul de multiplication unité étant effectué (n/c)*(n/c) fois pour tous les cycles de calcul.
44. Unité de calcul (1) selon la revendication 43, caractérisée en ce que le multiplieur (10) lit de façon itérative le multiplicande et le module à n bits depuis la mémoire (40) sur une base de w bits, stocke les w bits dans un registre à c' bits (102, 103, 104) dimensionné à une longueur de c' bits, et traite les c' bits du registre à c' bits (102, 103, 104) comme un tout.
45. Unité de calcul (1) selon la revendication 44, caractérisée en ce qu'un premier cycle de calcul de chaque calcul de multiplication unité représente un cycle de correction de valeur initiale de l'accumulateur (150).
46. Unité de calcul (1) selon la revendication 45, caractérisée en ce que le sélecteur de produit modulo sélectionne le résultat de la ligne précédente en tant que produit modulo lors du cycle de correction de valeur initiale de l'accumulateur (150).
47. Unité de calcul (1) selon la revendication 46, caractérisée en ce que le sélecteur de produit partiel (12-1, 12-3) met à "0" le produit partiel lors du cycle de correction de valeur initiale de l'accumulateur (150).
48. Unité de calcul (1) selon la revendication 44, comprenant en outre: un registre de module (102, 103) stockant des bits (c') du module (M) ayant une longueur de plage étendue délivrés en entrée à l'instant courant; un registre de multiplicande (104, 105) stockant des bits du multiplicande (A) ayant une longueur de plage étendue (c') délivrés en entrée à l'instant courant; et un registre de multiplicateur (106) stockant des bits du multiplicateur (B) ayant une longueur de mots (w) délivrés en entrée à l'instant courant.
49. Unité de calcul (1) selon la revendication 48, caractérisée en ce que 2867579 59 le registre de module (102, 103) et le registre de multiplicande (104, 105) sont chacun mis en oeuvre sous la forme de registres à c'+1 bits, et c' est un entier positif qui représente une longueur binaire de plage étendue d'au moins l'un du multiplicande à n bits et du module à n bits, c' étant inférieur ou égal à n.
50. Unité de calcul (1) selon la revendication 48, caractérisée en ce que chacun du registre de module (102, 103) et du registre de multiplicande (104, 105) comporte en outre une pluralité de sous-registres (200216) et un registre de signe à 1 bit (220) chargeant sélectivement une nouvelle valeur en réponse à l'un d'un signal d'horloge et d'un signal de validation de chargement.
51. Unité de calcul (1) selon la revendication 48, caractérisée en ce que.
le registre de multiplicateur (106) est un registre ayant une longueur binaire égale à w, w représentant une longueur de mots, et le registre de multiplicateur (106) décale des données vers la droite ou charge une nouvelle valeur en réponse à l'un d'un signal d'horloge et d'un signal de commande.
52. Multiplieur (10), comprenant: un générateur de produit modulo (120) sélectionnant un produit modulo parmi une pluralité de modules M à n bits sélectionnables, un module donné M étant formé à partir d'une plage étendue délivrée en entrée à l'instant courant de bits parmi les modules à n bits; un générateur de produit partiel (130) sélectionnant un multiplicande parmi une pluralité de multiplicandes A à n bits sélectionnables en tant que produit partiel, un multiplicande donné A étant formé d'une plage étendue délivrée en entrée à l'instant courant de bits parmi les multiplicandes à n bits; et FR 05 02052 18.07.2005 un accumulateur (150) accumulant le produit modulo et le produit partiel pour générer un résultat de multiplication.
53. Unité de calcul (1), comprenant: une mémoire (40) ; un hôte (20) stockant un multiplicande A, un multiplicateur B et un module M dans la mémoire (40) ; et le multiplieur (10) selon la revendication 52, le multiplieur (10) effectuant un calcul de multiplication de Montgomery avec le multiplicande, le multiplicateur et le module stockés sous le contrôle de l'hôte (20), et stockant un résultat de multiplication du calcul de multiplication de Montgomery dans la mémoire (40).
FR 05 02052 18.07.2005
FR0502052A 2004-03-02 2005-03-01 Multiplieur modulaire de montgomery Expired - Lifetime FR2867579B1 (fr)

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020040013855A KR20050088506A (ko) 2004-03-02 2004-03-02 다중 세정도를 지원하는 확장형 몽고메리 모듈러 곱셈기

Publications (2)

Publication Number Publication Date
FR2867579A1 true FR2867579A1 (fr) 2005-09-16
FR2867579B1 FR2867579B1 (fr) 2008-04-18

Family

ID=34909984

Family Applications (1)

Application Number Title Priority Date Filing Date
FR0502052A Expired - Lifetime FR2867579B1 (fr) 2004-03-02 2005-03-01 Multiplieur modulaire de montgomery

Country Status (6)

Country Link
US (1) US7805478B2 (fr)
JP (1) JP4870932B2 (fr)
KR (1) KR20050088506A (fr)
CN (1) CN1702613A (fr)
DE (1) DE102005010764A1 (fr)
FR (1) FR2867579B1 (fr)

Families Citing this family (37)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100458031B1 (ko) * 2003-03-14 2004-11-26 삼성전자주식회사 몽고메리 유형의 모듈라 곱셈 장치 및 방법
US8073892B2 (en) * 2005-12-30 2011-12-06 Intel Corporation Cryptographic system, method and multiplier
DE102007014808A1 (de) * 2007-03-28 2008-10-02 Texas Instruments Deutschland Gmbh Multiplizier- und Multiplizier- und Addiereinheit
WO2009055906A1 (fr) * 2007-11-02 2009-05-07 Certicom Corp. Arithmétique de montgomery signée
KR100946256B1 (ko) * 2007-12-26 2010-03-08 대구대학교 산학협력단 다정도 캐리 세이브 가산기를 이용한 듀얼필드상의확장성있는 몽고매리 곱셈기
KR101590322B1 (ko) * 2009-05-15 2016-02-19 삼성전자주식회사 연산임계경로가 감소된 모듈러 곱셈기 및 연산임계경로 감소방법
KR101248912B1 (ko) * 2009-12-31 2013-03-29 한양대학교 산학협력단 항혈관신생 활성을 가지는 재조합 아데노바이러스
KR20110105555A (ko) * 2010-03-19 2011-09-27 삼성전자주식회사 효율적인 하드웨어 구성을 갖는 몽고메리 승산기
KR101925868B1 (ko) 2012-05-17 2018-12-06 삼성전자주식회사 모듈러 계산 유닛 및 그것을 포함하는 보안 시스템
KR101929984B1 (ko) * 2012-05-17 2018-12-18 삼성전자주식회사 모듈러 곱셈기 및 그것의 모듈러 곱셈 방법
CN103645883A (zh) * 2013-12-18 2014-03-19 四川卫士通信息安全平台技术有限公司 基于fpga的高基模乘器
US9535656B2 (en) * 2014-03-14 2017-01-03 International Business Machines Corporation Pipelined modular reduction and division
KR102132261B1 (ko) * 2014-03-31 2020-08-06 삼성전자주식회사 비교 연산이 필요없이 최종 모듈러 감소를 하는 몽고메리 곱셈 방법 및 곱셈기
CN103970504B (zh) * 2014-05-07 2017-03-29 广东顺德中山大学卡内基梅隆大学国际联合研究院 在ecc中实现位数自适应模乘运算的方法及模乘运算器
CN104090737B (zh) * 2014-07-04 2017-04-05 东南大学 一种改进型部分并行架构乘法器及其处理方法
KR102338863B1 (ko) 2015-09-09 2021-12-13 삼성전자주식회사 연산을 제어하기 위한 장치 및 방법
IL244842A0 (en) * 2016-03-30 2016-07-31 Winbond Electronics Corp Efficient non-modular multiplexing is protected against side-channel attacks
CN106528046B (zh) * 2016-11-02 2019-06-07 上海集成电路研发中心有限公司 长位宽时序累加乘法器
KR102594656B1 (ko) * 2016-11-25 2023-10-26 삼성전자주식회사 보안 프로세서, 이를 포함하는 어플리케이션 프로세서 및 보안 프로세서의 동작 방법
CN108242994B (zh) * 2016-12-26 2021-08-13 阿里巴巴集团控股有限公司 密钥的处理方法和装置
CN108241481B (zh) * 2016-12-26 2022-08-23 航天信息股份有限公司 一种适用于rsa算法的部分求余乘法器设备
CN111680789B (zh) * 2017-04-11 2023-04-28 上海兆芯集成电路有限公司 神经网络单元
RU2653263C1 (ru) * 2017-07-24 2018-05-07 федеральное государственное автономное образовательное учреждение высшего образования "Северо-Кавказский федеральный университет" Арифметико-логическое устройство для умножения чисел по модулю
JP7129857B2 (ja) * 2018-09-07 2022-09-02 ルネサスエレクトロニクス株式会社 積和演算装置、積和演算方法、及びシステム
CN109857368B (zh) * 2018-12-20 2022-07-26 上海大学 一种位数众多、可分组、可重构的多值电子运算器及方法
CN109669670B (zh) * 2018-12-26 2020-09-22 贵州华芯通半导体技术有限公司 用于蒙哥马利模乘中的不均等分块的数据处理方法及装置
AU2020423806B2 (en) * 2020-01-20 2023-06-08 Nippon Telegraph And Telephone Corporation Secure computation apparatus, secure computation method, and program
WO2021149105A1 (fr) * 2020-01-20 2021-07-29 日本電信電話株式会社 Dispositif de calcul sécurisé, procédé de calcul sécurisé et programme
WO2021196096A1 (fr) * 2020-04-01 2021-10-07 华为技术有限公司 Multiplicateur de fusion multimode
US20220121424A1 (en) * 2020-10-21 2022-04-21 PUFsecurity Corporation Device and Method of Handling a Modular Multiplication
CN112328962B (zh) * 2020-11-27 2021-12-31 深圳致星科技有限公司 矩阵运算优化方法、装置、设备和可读存储介质
CN112506468B (zh) * 2020-12-09 2023-04-28 上海交通大学 支持高吞吐多精度乘法运算的risc-v通用处理器
US12079594B2 (en) * 2021-02-22 2024-09-03 Mellanox Technologies, Ltd. Fast precomputation for Montgomery multiplier
CN113032845B (zh) * 2021-03-31 2022-02-11 郑州信大捷安信息技术股份有限公司 一种用于资源受限芯片的EdDSA签名实现方法和装置
CN113296733B (zh) * 2021-04-25 2024-09-03 阿里巴巴创新公司 数据处理方法以及装置
TWI802095B (zh) 2021-11-22 2023-05-11 財團法人工業技術研究院 模數乘法電路與對應之計算模數乘法之方法
KR102734750B1 (ko) * 2023-12-27 2024-11-26 포항공과대학교 산학협력단 가변 rns 모듈러스 변환 연산 장치 및 방법

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0294476A1 (fr) 1986-12-30 1988-12-14 Hughes Aircraft Company Totalisateur a report de totalisation de n bits
FR2726667B1 (fr) * 1994-11-08 1997-01-17 Sgs Thomson Microelectronics Procede de mise en oeuvre de multiplication modulaire selon la methode montgomery
KR100257124B1 (ko) 1997-05-16 2000-05-15 문상재 공통 피승수 모듈라 곱셈을 이용한 고속 멱승 방법
US6356636B1 (en) 1998-07-22 2002-03-12 Motorola, Inc. Circuit and method for fast modular multiplication
GB2352309B (en) * 1999-07-21 2004-02-11 Advanced Risc Mach Ltd A system and method for performing modular multiplication
JP2002236581A (ja) * 2001-02-08 2002-08-23 Matsushita Electric Ind Co Ltd 演算回路、演算方法、及びプログラム記録媒体
FR2822260A1 (fr) 2001-03-14 2002-09-20 Bull Sa Procedes et dispositifs pour accelerer le temps de calcul d'un produit de montgomery d'un multiplication et d'une exponentiation modulaire
US20020172355A1 (en) 2001-04-04 2002-11-21 Chih-Chung Lu High-performance booth-encoded montgomery module
JP2003216034A (ja) * 2002-01-23 2003-07-30 Ail Kk べき乗剰余演算器
JP2003216411A (ja) * 2002-01-23 2003-07-31 Sony Corp 多倍長演算処理装置およびｉｃデバイス
JP2004258141A (ja) * 2003-02-24 2004-09-16 Fujitsu Ltd モンゴメリ乗算剰余の多倍長演算のための演算装置

Non-Patent Citations (5)

* Cited by examiner, † Cited by third party
Title
HEE-KWAN SON ET AL: "Design and implementation of scalable low-power montgomery multiplier", COMPUTER DESIGN: VLSI IN COMPUTERS AND PROCESSORS, 2004. ICCD 2004. PROCEEDINGS. IEEE INTERNATIONAL CONFERENCE ON SAN JOSE, CA, USA 11-13 OCT. 2004, PISCATAWAY, NJ, USA,IEEE, 11 October 2004 (2004-10-11), pages 524 - 531, XP010736818, ISBN: 0-7695-2231-9 *
J-H HONG ET AL.: "Cellular-array modular multiplier for fast RSA public-key cryptosystem based on modified booth's algorithm", IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, IEEE SERVICE CENTER, PISCATAWAY, NJ, US, vol. 11, no. 3, June 2003 (2003-06-01), pages 474 - 484, XP011099280, ISSN: 1063-8210 *
TENCA A F ET AL INSTITUTE OF ELECTRICAL AND ELECTRONICS ENGINEERS: "An efficient and scalable radix-4 modular multiplier design using recoding techniques", CONFERENCE RECORD OF THE 37TH. ASILOMAR CONFERENCE ON SIGNALS, SYSTEMS, & COMPUTERS. PACIFIC GROOVE, CA, NOV. 9 - 12, 2003, ASILOMAR CONFERENCE ON SIGNALS, SYSTEMS AND COMPUTERS, NEW YORK, NY : IEEE, US, vol. VOL. 1 OF 2. CONF. 37, 9 November 2003 (2003-11-09), pages 1445 - 1450, XP010701352, ISBN: 0-7803-8104-1 *
TENCA A F ET AL: "HIGH-RADIX DESIGN OF A SCALABLE MODULAR MULTIPLIER", CRYPTOGRAPHIC HARDWARE AND EMBEDDED SYSTEMS. 3RD INTERNATIONAL WORKSHOP, CHES 2001, PARIS, FRANCCE, MAY 14 - 16, 2001 PROCEEDINGS, LECTURE NOTES IN COMPUTER SCIENCE, BERLIN : SPRINGER, DE, vol. VOL. 2162, 14 May 2001 (2001-05-14), pages 185 - 201, XP001061165, ISBN: 3-540-42521-7 *
WANG P A ET AL: "New VLSI architectures of RSA public-key cryptosystem", CIRCUITS AND SYSTEMS, 1997. ISCAS '97., PROCEEDINGS OF 1997 IEEE INTERNATIONAL SYMPOSIUM ON HONG KONG 9-12 JUNE 1997, NEW YORK, NY, USA,IEEE, US, vol. 3, 9 June 1997 (1997-06-09), pages 2040 - 2043, XP010236637, ISBN: 0-7803-3583-X *

Also Published As

Publication number Publication date
FR2867579B1 (fr) 2008-04-18
US7805478B2 (en) 2010-09-28
JP4870932B2 (ja) 2012-02-08
KR20050088506A (ko) 2005-09-07
CN1702613A (zh) 2005-11-30
US20050198093A1 (en) 2005-09-08
JP2005250481A (ja) 2005-09-15
DE102005010764A1 (de) 2005-09-29

Similar Documents

Publication Publication Date Title
FR2867579A1 (fr) Multiplieur modulaire de montgomery
EP0853275B1 (fr) Coprocesseur comprenant deux circuits de multiplication opérant en parallèle
US5764554A (en) Method for the implementation of modular reduction according to the Montgomery method
EP0712071B1 (fr) Procédé de mise en oeuvre de multiplication modulaire selon la méthode de montgomery
JP3939658B2 (ja) モジュラー乗算を行うための装置、および、モジュラー乗算を行うための算術演算装置
TWI263402B (en) Reconfigurable fir filter
JP2004326112A (ja) マルチプルモジュラス選択器、累算器、モンゴメリー掛け算器、マルチプルモジュラス発生方法、部分掛け発生方法、累算方法、掛け算方法、モジュラス選択器、およびブースレコーダ
KR102496446B1 (ko) 모듈러 연산을 위한 워드 병렬 연산 방법
US7046800B1 (en) Scalable methods and apparatus for Montgomery multiplication
EP2003547A1 (fr) Operateur de reduction modulaire amélioré
EP0939362B1 (fr) Coprocesseur d&#39;arithmétique modulaire permettant de réaliser des opérations non modulaires rapidement
FR2849512A1 (fr) Multiplieur modulaire de montgomery et procede de multiplication correspondant
JP7540501B2 (ja) 秘匿ｍｓｂ正規化システム、分散処理装置、秘匿ｍｓｂ正規化方法、およびプログラム
EP0793165B1 (fr) Coprocesseur d&#39;arithmétique modulaire permettant de réaliser rapidement des opération non modulaires
EP0939363B1 (fr) Procédé de mise en oeuvre d&#39;une multiplication modulaire selon la méthode de Montgoméry
EP0947913B1 (fr) Procédé de réalisation amélioré d&#39;une division entière
CN118819470A (zh) 模乘运算电路、方法、数据处理芯片和电子设备
FR2796736A1 (fr) Procede pour effectuer une multiplication avec accumulation dans un corps de galois
EP0778518B1 (fr) Procédé de production d&#39;un paramètre J0 associé à la mise en oeuvre d&#39;opérations modulaires selon la méthode de Montgomery
JP2007500388A (ja) 長整数乗算器
FR2818765A1 (fr) Multiplicateur modulaire et processeur de cryptage/decryptage utilisant le multiplicateur modulaire
WO2002073395A2 (fr) Procede et appareil de multiplication et/ou de reduction modulaire
JP3904421B2 (ja) 剰余乗算演算装置
EP1455270A2 (fr) Procédé et dispositif de conversion de base dans des corps finis et un multiplicateur
EP1869545B1 (fr) Dispositif implementant la multiplication modulaire de montgomery

Legal Events

Date Code Title Description
PLFP Fee payment

Year of fee payment: 12

PLFP Fee payment

Year of fee payment: 13

PLFP Fee payment

Year of fee payment: 14

PLFP Fee payment

Year of fee payment: 16

PLFP Fee payment

Year of fee payment: 17

PLFP Fee payment

Year of fee payment: 18

PLFP Fee payment

Year of fee payment: 19

PLFP Fee payment

Year of fee payment: 20