Brevet FR3070814A1 (20190308)

REVENDICATIONS1. Dispositif de réduction modulaire pour calculer le reste d'un entier x divisé par un modulo q, ledit entier étant représenté par un mot binaire de 2n bits et le modulo par un mot binaire de n bits, caractérisé en ce qu'il comprend un circuit implémentant un algorithme de réduction modulaire de Barrett généralisé, dit circuit de Barrett (210), une mémoire cache (220) et un circuit de division binaire (230), le circuit de Barrett recevant ledit entier ainsi qu'un résultat d'un pré-calcul (du) ) relatif à une valeur du modulo (q) et une puissance de 2 ( 2'''), le résultat du pré-calcul étant fourni directement par la mémoire cache au circuit de Barrett (220) s'il est déjà stocké en relation avec ladite valeur du modulo et, sinon, étant calculé par le circuit de division binaire (230) avant d'être stocké dans la mémoire cache et fourni au circuit de Barrett.\n<CLM>\1\tDispositif de réduction modulaire selon la revendication 1, caractérisé en ce que la mémoire cache comprend une première partie, dite mémoire d'étiquettes (310), et une seconde partie, dite mémoire de données (320), les première et seconde parties étant adressées par f (q) où f est une fonction de projection de n bits sur m bits avec m\n<CLM>\1\tDispositif de réduction modulaire selon la revendication 1 ou 2, caractérisé en ce que le circuit de division binaire effectue le pré-calcul 11= où 2'" est le q 2'" q ^ 2"" , plus grand entier inférieur ou égal à ou 2'' est ladite puissance de 2 et a est un q entier tel que a n+1. 17\n<CLM>\1\tDispositif de réduction modulaire selon la revendication 3, caractérisé en ce que le circuit de Barrett décale (110) de a+,8 bits le mot binaire représentant x vers les bits de poids faibles, où 16 est un entier tel que 16 -2, multiplie (120) ensuite le mot ainsi décalé par le résultat du pré-calcul, ,u, puis décale (130) à nouveau de a-16 bits le résultat 5 de cette multiplication vers les bits de poids faibles pour obtenir un second mot, ledit second mot étant multiplié (140) par le modulo avant d'être soustrait (150) au mot binaire représentant x pour fournir une valeur provisoire r' du reste, la valeur du reste r étant choisie (170) égale à r' si r'-q est négatif ou nul et égale à r'-q si r'-q est strictement positif. 'o\n<CLM>\1\tDispositif de réduction modulaire selon la revendication 1, caractérisé en ce que la mémoire cache (420) reçoit en outre l'entier x et fournit en sus du résultat de pré-calcul relatif à une valeur du modulo q, une valeur de signe associé au couple (x,q) , cette valeur de signe étant fournie au circuit de Barrett. 15\n<CLM>\1\tDispositif de réduction modulaire selon la revendication 5, caractérisé en ce que la mémoire cache comprend une première partie, dite mémoire d'étiquettes (510), et une seconde partie, dite mémoire de données (520), les première et seconde parties étant adressées par g (x,q) où g est une fonction de projection de 3n bits sur m bits avec 20 m\n<CLM>\1\tDispositif de réduction modulaire selon la revendication 6, caractérisé en ce que le résultat du pré-calcul ainsi que la valeur de signe sont fournis directement par la mémoire cache (420) au circuit de Barrett (410) si le couple (x,q) est stocké dans la mémoire d'étiquettes, et sinon, le résultat du pré-calcul'u, est obtenu par le circuit de 18 division binaire (430) à partir de la valeur du modulo, q, et de la puissance de 2, la valeur du signe, b, étant obtenue à partir de la valeur du modulo, q, de l'entier, x, et du résultat du pré-calcul, le résultat du pré-calcul et la valeur de signe étant stockés dans la mémoire de données à l'adresse à calculer g (x,q) avant d'être fournis au circuit de Barrett. 5\n<CLM>\1\tDispositif de réduction modulaire selon la revendication 2, caractérisé en ce qu'il comprend une seconde mémoire cache (625,725) recevant l'entier x et le modulo q et fournissant une valeur de signe b stockée à une adresse en relation avec le couple (x,q) , cette valeur de signe étant fournie au circuit de Barrett. 10\n<CLM>\1\tDispositif de réduction modulaire selon la revendication 8, caractérisé en ce la seconde mémoire cache (625) comprend une seconde mémoire d'étiquettes et une seconde mémoire de données, ces secondes mémoires d'étiquettes et de données étant toutes deux adressées par h(x,q) où h est une fonction de projection de 3n bits sur m 15 bits avec m\n<CLM>\1\tDispositif de réduction modulaire selon la revendication 9, caractérisé en ce que la valeur de signe est fournie directement par la seconde mémoire cache (625) au circuit de Barrett (610) si la valeur du modulo q est stockée dans la mémoire d'étiquettes et le couple (x,q) est stocké dans la seconde mémoire d'étiquettes, et sinon, la valeur du signe, b , est obtenue à partir de la valeur du modulo, q et de l'entier, x, la valeur de signe 25 étant ensuite fournie au circuit de Barrett.\n<CLM>\1\tDispositif de réduction modulaire selon la revendication 8, caractérisé en ce que la seconde mémoire cache (725) comprend une seconde mémoire de données mais ne 19 comprend pas de mémoire d'étiquettes, un comparateur (750) pour vérifier si la sortie r du circuit de Barrett (710) vérifie la condition 0 r\n<CLM>\1\tDispositif de réduction modulaire selon l'une quelconque des revendications 5 à 11, caractérisé en ce que le circuit de division binaire (430,630,730) effectue le pré- calcul ,u = 2'" où 2n" 2' le inférieur égal à 2"±a q est est plus grand entier ou ou est - q q - i 10 ladite puissance de 2 et a est un entier tel que a n+1.\n<CLM>\1\tDispositif de réduction modulaire selon la revendication 12, caractérisé en ce que le circuit de Barrett (410,610,710) décale (810) de oe+16 bits le mot binaire représentant x vers les bits de poids faibles, où 16 est un entier tel que 16 -2, multiplie 15 (820) ensuite le mot ainsi décalé par le résultat du pré-calcul, du, puis décale (830) à nouveau de a- 16 bits le résultat de cette multiplication vers les bits de poids faibles pour obtenir un second mot, la valeur de signe étant soustraite (835) au second mot avant qu'il soit multiplié (840) par le modulo, le résultat de cette multiplication étant ensuite soustrait (850) à l'entier x pour donner ledit reste, r. 20