Brevet FR2830641A1 — publié le 20030411

Procédé, dispositif et programme pour élever un argument à une puissance de grand exposant. Le domaine de l'invention est celui des procédés d'élévation à une puissance dans un monoïde fini au moyen d'un processeur capable de traiter des mots de longueur k exprimée en bits. On rappelle qu'un ensemble d'éléments a une structure de monoïde ou est nommé monoïde s'il existe pour cet ensemble une loi de composition interne associative ayant un élément neutre unique. Une loi de composition est interne si appliquée à deux éléments de l'ensemble, elle donne un élément de cet ensemble. La loi de composition interne appliquée à l'élément neutre et à un autre élément de l'ensemble donne à nouveau cet autre élément de l'ensemble. La loi de composition interne est associative si appliquée à n éléments, elle donne le même élément en étant appliquée au premier élément et à l'élément résultant de son application aux éléments suivants qu'en étant appliquée au dernier élément et à l'élément résultant de son application aux éléments précédents. De nombreux éléments du monde réel tels que des images, des signaux de communication, peuvent être traités numériquement par un processeur au moyen de mots informatiques qui codent ces éléments. Par exemple, pour un ensemble d'images, une combinaison de deux images donne une image et une combinaison d'image blanche à une autre image donne à nouveau cette autre image. On trouve parfois dans l'état de la technique la notion de groupe. Au sens de la technique à laquelle s'applique l'invention, un groupe est un monoïde particulier dans lequel tout élément x a un élément symétrique x'tel que la loi de composition interne appliquée à ces deux éléments, dans n'importe quel sens, donne comme résultat l'élément neutre. Un ensemble constitue un monoïde fini si son cardinal, c'est à dire la quantité de ses éléments, est exprimé par un nombre fini. Par exemple l'ensemble des entiers relatifs de l'intervalle fermé [O, N-1] où N est un nombre déterminé, muni d'une loi de composition interne telle que l'addition modulo N, constitue un groupe fini qui est un monoïde fini. Cet ensemble muni d'une loi de composition interne telle que la multiplication modulo N, constitue un ïde fi monoïde fini. On entend par élévation d'un argument x à une puissance d'exposant e dans un monoïde fini, l'application de la loi de composition interne à un nombre entier e d'éléments égaux chacun à l'argument x. L'exposant e est donc ici un nombre entier strictement positif. Par exemple, si la loi de composition interne est l'addition, l'élément résultant d'une élévation d'un argument x à la puissance d'exposant e, est égal à l'addition de e éléments égaux chacun à l'argument x. Par exemple encore, si la loi de composition interne est multiplication, l'élément résultant d'une élévation d'un argument x à la puissance d'exposant e, est égal à la multiplication de e éléments égaux chacun à l'argument x. On entend par élévation au carré d'un argument x, son élévation à une puissance d'exposant 2. On considère qu'un premier élément est multiple d'un deuxième élément lorsqu'il existe un troisième élément tel que la loi de composition interne appliquée au deuxième et au troisième élément, donne le premier élément. De façon connue, la cryptographie utilise des monoïdes finis constitués d'ensembles d'entiers relatifs de l'intervalle fermé [0, N-1], munis de la multiplication modulo N comme loi de composition interne. Knuth, D. E.-The art of computer programming, vol. 2 Seminumerical Algorithms-Addison Wesley, 1981, décrit un algorithme de calcul simple de type carré-multiplication. En notant lel la longueur de l'exposant exprimée en bits et w (e) le nombre de bits non nuls dans cet exposant, cet algorithme nécessite lel-1 carrés et w (e) multiplications dans le monoïde fini. Avec un processeur standard qui peut traiter des mots de k bits, le scrutation de chaque bit de l'exposant, conduit à des calculs avec décalages sur des mots de k bits pour mémoriser l'exposant. En moyenne, la quantité de multiplications dans le monoïde fini, est voisine de lel/2, et la quantité de décalages est voisine de lel (1-1/k). Lorsque l'exposant est grand de façon à sécuriser un traitement cryptographique, la quantité d'opérations effectuées par le processeur, ralentit considérablement le traitement cryptographique. Pour accélérer les calculs, Bergeron et al. - Efficient Computation of Addition Chains-Journal de théorie des nombres de Bordeaux, volume 6, (1994), 21-38, propose de calculer des données auxiliaires comme des chaînes d'additions. La recherche d'une bonne chaîne d'additions nécessite un temps de calcul élevé qui réduit l'avantage de l'accélération sur les calculs d'élévation à une puissance lorsque l'exposant change à chaque élévation de puissance. L'algorithme de type carré-multiplication connaît une amélioration selon Knuth qui consiste calculer des puissances modulaires de l'argument x avec de petits exposants impaires 1, 3,..., 2t-1, puis à scruter l'exposant par blocs de t bits. La valeur t=1 redonne la version non améliorée. Le coût des calculs est de lel carrés et, en moyenne, t+ (1-zut) lel/t multiplications dans un monoïde, plus la scrutation de l'exposant. Une minimisation du coût en nombre de carrés et de multiplications, conduit à des valeurs optimales pour t, fonction de la longueur de l'exposant et du rapport entre le coût d'un carré et celui d'une multiplication dans le monoïde. Dans le cas des monoïdes (Z/nZ *,.), les valeurs de t sont 5 pour lel=512, 6 pour le=768, 6 ou 7 pour le=1024, 7 pour le=2048. Ces tailles de blocs comparées avec la longueur k (8,16, 32,64) de mots standards, montrent que des manipulations complexes de bits au sein des mots et sur des mots différents, accompagnent une utilisation de valeurs optimales de t. Pour éviter des manipulations complexes de bits, pour simplifier le code et diminuer les risques d'erreurs, une solution qui consiste à utiliser une valeur sous optimale t=4, n'apporte pas entière satisfaction en terme de performances. Pour remédier aux inconvénients précédemment mentionnés de l'état connu de la technique antérieure, l'invention a pour objets un procédé, un dispositif et un programme pour élever un argument à une puissance de grand exposant, remarquables par les points suivants. Le procédé pour élever un argument x à une puissance d'exposant e dans un monoïde fini, au moyen d'un processeur capable de traiter des mots de longueur k exprimée en bits, l'exposant e étant codé sur 1 mots de k bits avec 1 supérieur ou égal à 1, comprend deux phases. Une première phase de génération de puissances de l'argument x avec un exposant impair compris entre 1 et 2t-1 où t est un nombre inférieur à k, permet d'obtenir 2t-puissances de l'argument x avec des exposants impairs relativement petit en comparaison de l'exposant e. Une deuxième phase de traitement de chaque mot qui code l'exposant e dans un ordre allant du bit de poids fort jusqu'au bit de poids faible de l'exposant e, permet d'obtenir une valeur y dans un registre, après scrutation du dernier bloc comprenant les bits de poids les plus faibles pour coder l'exposant e, égale à l'argument x élevé à la puissance d'exposant e dans le monoïde fini. Dans la deuxième phase : - le processeur scrute le mot courant à traiter par blocs d'au plus t bits en allant des bits de poids forts vers et jusqu'au bit de poids le plus faible du mot courant ; - pour un premier bloc scruté de premier mot tel qu'il existe dans le bloc scruté un bit non nul de poids le plus faible avec un rang b pris à partir de 1 pour le bit de poids faible du bloc, le processeur charge à partir du dit registre, une valeur y égale à unepuissance générée en première phase dont l'exposant c a pour valeur celle codée par le bit de rang b et les bits de rangs suivants jusqu'au bit de poids fort du bloc scruté, effectue b élévations au carré de ladite valeur y et range le résultat ainsi obtenu comme nouvelle valeur y dans le registre ; - pour chaque bloc scruté suivant, le processeur effectue des élévations au carré de ladite valeur y, en quantité égale au nombre de bits du bloc scruté, et s'il existe dans le bloc scruté un bit non nul de poids le plus faible avec un rang b pris à partir de 1 pour le bit de poids faible du bloc, le processeur effectue une multiplication de la valeur y par une puissance générée en première phase dont l'exposant c a pour valeur celle codée par le bit de rang b et les bits de rangs suivants jusqu'au bit de poids fort du bloc scruté, avant d'effectuer les b dernière élévations au carré de ladite valeur y et de ranger le résultat ainsi obtenu dans ledit registre. Le procédé selon l'invention n'a pas besoin d'un microprocesseur spécialisé mais se contente avantageusement d'un processeur standard capable de traiter des mots de k bits. Contrairement à l'état connu de la technique antérieure, le procédé n'a pas besoin de recourir à des données auxiliaires. On remarque que la quantité totale d'élévations au carré, n'est fixée que par la quantité de bits qui codent l'exposant e. Elle est en particulier indépendante de la longueur k des mots que peut traiter le processeur et de la taille t de chaque bloc scrutée qui peut donc être variable. Il est ainsi possible de choisir des valeurs optimales de t. La quantité de multiplications est égale à la quantité de blocs non nuls qui composent l'ensemble des mots pour coder l'exposant e. De façon la plus simple, en début de deuxième phase, la valeur y est initialisée à 1 dans le registre et pour chaque bloc scruté à partir du premier, le processeur effectue des élévations au carré de ladite valeur y, en quantité égale au nombre de bits du bloc scruté, et s'il existe dans le bloc scruté un bit non nul de poids le plus faible avec un rang b pris à partir de 1 pour le bit de poids faible du bloc, le processeur effectue une multiplication de la valeur y par une puissance générée en première phase dont l'exposant c a pour valeur celle codée par le bit de rang b et les bits de rangs suivants jusqu'au bit de poids fort du bloc scruté, avant d'effectuer les b dernière élévations au carré de ladite valeur y et de ranger le résultat ainsi obtenu dans le registre. Avantageusement lorsque la longueur de l'exposant e est inférieure à un nombre entier de mots, le bit non nul de poids le plus fort du premier mot étant de rang k'pris à partir de 1 pour le bit de poids le plus faible, le premier bloc scruté a pour bit de poids fort, le bit de rang k'dans le premier mot. Ceci évite de scruter des blocs nuls en tête du premier mot pour lesquels des élévations au carré se feraient sur des valeurs unitaires. La valeur t pouvant être choisie quelconque dans le procédé, la valeur t peut être optimisée pour accélérer l'élévation de puissance avec un minimum de ressources en réduisant le nombre d'opérations internes dans le monoïde fini. Chaque mot ou au moins chaque mot au delà du premier mot, est alors découpé en q blocs de taille t et, si k n'est pas un multiple de t, un bloc de taille réduite r inférieure à t. Avantageusement lorsque le premier mot contient k'bits de poids faible utiles pour coder l'exposant e, le premier mot est découpé en q'blocs de taille t et, si k'n'est pas un multiple de t, un bloc de taille réduite r'inférieure à t. La scrutation du bloc de taille réduite peut être faite après q scrutations de blocs de taille t. Selon une première variante intéressante de l'invention, la valeur y est initialisée avec une puissance générée en première phase dont l'exposant c a pour valeur celle codée par le bit de rang b et les bits de rangs suivants jusqu'au bit de poids fort du premier bloc scruté non nul du premier mot. Ceci permet d'éviter t-b élévations au carré d'une valeur unitaire de y pour la scrutation du premier bloc. Selon une seconde variante de l'invention, la scrutation d'un bloc commence par une scrutation de bloc de taille réduite sur les bits de poids fort du bloc jusqu'à trouver un bloc de taille réduite avec tous ses bits nuls et dès qu'un tel bloc est trouvé, la scrutation des blocs suivants s'il en existe, est continuée par bloc de taille t. Ceci permet d'économiser une multiplication lorsque le bloc de taille réduite placé sur les poids faibles du mot est non nul alors qu'il est possible de cadrer un bloc de taille réduite avec tous ses bits à zéro de poids plus fort. Le dispositif pour élever un argument x à une puissance d'exposant e dans un monoïde fini, comprend un processeur capable de traiter des mots de longueur k exprimée en bits, un premier registre pour recevoir l'argument x, un deuxième registre de 1 mots de k bits avec 1 supérieur ou égal à 1 pour recevoir l'exposant e, un troisième registre pour produire l'argument x élevé à la puissance d'exposant e et une mémoire pour contenir des données et des instructions exécutables par le processeur. Plus particulièrement, le dispositif comprend : - un quatrième registre pour contenir des puissances de l'argument x avec un exposant impair compris entre 1 et i-1 où t est un nombre inférieur à k contenu dans la mémoire ; - des instructions contenues dans la mémoire pour traiter chaque mot qui code l'exposant e dans un ordre allant du bit de poids fort jusqu'au bit de poids faible de l'exposant e, agencées pour commander le processeur de façon à ce qu'en exécution : - le processeur scrute le mot courant à traiter par blocs d'au plus t bits en allant des bits de poids forts vers et jusqu'au bit de poids le plus faible du mot courant ; - pour un premier bloc scruté de premier mot tel qu'il existe dans le bloc scruté un bit non nul de poids le plus faible avec un rang b pris à partir de 1 pour le bit de poids faible du bloc, le processeur charge à partir du troisième registre, une valeur y égale à une puissance générée en première phase dont l'exposant c a pour valeur celle codée par le bit de rang b et les bits de rangs suivants jusqu'au bit de poids fort du bloc scruté, effectue b élévations au carré de ladite valeur y et range le résultat ainsi obtenu comme nouvelle valeur y dans le troisième registre ; - pour chaque bloc scruté suivant, le processeur effectue des élévations au carré de ladite valeur y, en quantité égale au nombre de bits du bloc scruté, et s'il existe dans le bloc scruté un bit non nul de poids le plus faible avec un rang b pris à partir de 1 pour le bit de poids faible du bloc, le processeur effectue une multiplication de la valeur y par une puissance contenue dans le troisième registre dont l'exposant c a pour valeur celle codée par le bit de rang b et les bits de rangs suivants jusqu'au bit de poids fort du bloc scruté, avant d'effectuer les b dernière élévations au carré de ladite valeur y et de ranger le résultat ainsi obtenu dans le troisième registre ; de sorte que la valeur y contenue dans le troisième registre après scrutation du dernier bloc comprenant les bits de poids les plus faible pour coder l'exposant e, est égale à l'argument x élevé à la puissance d'exposant e dans le monoïde fini. Le programme recevant d'un premier registre un argument x et d'un deuxième registre de 1 mots de k bits avec 1 supérieur ou égal à 1, k étant une longueur de mot exprimée en bits que peut traiter un processeur, un exposant e pour produire dans un troisième registre l'argument x élevé à une puissance d'exposant e, fait exécuter par le processeur : - dans une première phase, une génération de puissances de l'argument x avec un exposant impair compris entre 1 et 2t-1 où t est un nombre inférieur à k ; - dans une deuxième phase, un traitement de chaque mot qui code l'exposant e dans un ordre allant du bit de poids fort jusqu'au bit de poids faible de l'exposant e, tel que : - le processeur scrute le mot courant à traiter par blocs d'au plus t bits en allant des bits de poids forts vers et jusqu'au bit de poids le plus faible du mot courant ; - pour un premier bloc scruté de premier mot tel qu'il existe dans le bloc scruté un bit non nul de poids le plus faible avec un rang b pris à partir de 1 pour le bit de poids faible du bloc, le processeur charge à partir du troisième registre, une valeur y égale à une puissance générée en première phase dont l'exposant c a pour valeur celle codée par le bit de rang b et les bits de rangs suivants jusqu'au bit de poids fort du bloc scruté, effectue b élévations au carré de ladite valeur y et range le résultat ainsi obtenu comme nouvelle valeur y dans le troisième registre ; - pour chaque bloc scruté suivant, le processeur effectue des élévations au carré de ladite valeur y, en quantité égale au nombre de bits du bloc scruté, et s'il existe dans le bloc scruté un bit non nul de poids le plus faible avec un rang b pris à partir de 1 pour le bit de poids faible du bloc, le processeur effectue une multiplication de la valeur y par une puissance générée en première phase dont l'exposant c a pour valeur celle codée par le bit de rang b et les bits de rangs suivants jusqu'au bit de poids fort du bloc scruté, avant d'effectuer les b dernière élévations au carré de ladite valeur y et de ranger le résultat ainsi obtenu dans le troisième registre ; de sorte que la valeur y contenue dans le troisième registre après scrutation du dernier bloc comprenant les bits de poids les plus faible pour coder l'exposant e, est égale à l'argument x élevé à la puissance d'exposant e dans le monoïde fini. L'invention sera mieux comprise de la description d'un exemple de réalisation qui suit en référence aux dessins annexés dans les quels : - la figure 1 est un schéma de dispositif conforme à l'invention ; - la figure 2 montre des étapes de première phase de procédé selon l'invention ; - les figures 3 et 4 montrent des étapes de deuxième phase de procédé selon l'invention ; - les figures 5 à 7 montrent une première variante de deuxième phase de procédé selon l'invention ; - les figures 8 à 10 montrent une deuxième variante de deuxième phase de procédé selon l'invention. En référence à la figure 1, un dispositif 1 est agencé pour recevoir en entrée un nombre x et un nombre e et pour générer en sortie un nombre y égal à une puissance d'argument x et d'exposant e. Le dispositif 1 comprend un processeur 2 standard prévu pour traiter des mots de longueur k bits en fonction d'instructions et de données contenues dans une mémoire 3. Des registres 4 et 5 sont prévus chacun respectivement pour contenir l'argument x et l'exposant e. Lorsque la longueur lel de l'exposant e exprimée en bits, est supérieure à k, le registre 5 est constitué de 1 mots de k bits de façon à ce que lel soit compris entre (1-1) k et Ik. Un registre 6 est prévu pour contenir la puissance y. Un registre 7 est prévu pour contenir des puissances de l'argument x avec des petits exposants impairs. Le dispositif 1 permet de mettre en oeuvre le procédé décrit en référence aux figures suivantes, en faisant exécuter par le processeur 2, un programme constitué d'instructions et de données contenues dans la mémoire 3 pour effectuer ledit procédé. Dans une première phase du procédé en référence à la figure 2, le processeur 2 génère (2t-1) puissances de l'argument x, rangées chacune dans un mot du registre 7. Le nombre t est une donnée contenue dans la mémoire 3, de valeur inférieure à k. Dans une étape 8, un indice i de mot dans le registre 7, est initialisé à 1. Dans une étape 9, une valeur x, de premier mot du registre 7, est initialisée à la valeur de l'argument x. Dans une étape 10, le processeur 2 calcule le carré xs de l'argument x qui est conservé dans un registre interne du processeur 2 ou en mémoire 3. Dans une étape 11, le processeur 2 teste si la valeur courante de l'indice i est inférieure à 2t-2. Un résultat négatif à ce test termine la première phase du procédé. Un résultat positif à ce test active une succession d'étapes 12 à 14. Dans l'étape 12, la valeur courante x, est chargée dans un registre interne z du processeur 2. Dans l'étape 13, l'indice courant i est augmenté de deux unités. Dans l'étape 14, le processeur 2 multiplie le contenu du registre interne z par le carré X2 et range la valeur xi obtenue, dans le mot du registre 7, d'indice i réactualisé en étape 13. L'étape 14 est bouclée sur l'étape 11, ayant pour effet d'exécuter si t est supérieur à 1, les étapes 12 à 14 pour des valeurs de i en étape 11, allant de 1 à 2-3, i variant par incrément de 2. L'étape 14 est alors exécutée pour des valeurs de i allant de 3 à 2t-1. Selon la loi bien connue sur les intervalles, le nombre P d'exécutions de l'étape 14 est donné par la formule : P = 1 + (2t-1-3)/2 C'est à dire : P = 2t-1~1 Dans la première phase, le processeur 2 a donc calculé un carré et P produits pour obtenir dans le registre 7, n puissances d'exposant impair de l'argument x : X1=X1, xs=x,..., Xn=x", avec n = 2t-1. Dans une deuxième phase du procédé en référence aux figures 3 et 4, le processeur 2 effectue un calcul progressif de la puissance y en scrutant successivement chaque mot du registre 5 qui contient l'exposant e. Dans une étape 15, la valeur de puissance y est initialisée à 1 dans le registre 6. Ensuite, le processeur 2 itère une première boucle d'étapes 17 à 54, indexée par un indice Il variant d'une valeur 1 initialisée en étape 16 à la valeur 1 détectée en étape 54 qui termine la deuxième phase du procédé. Dans l'étape 53 qui précède l'étape 54, l'indice Il est augmenté d'une unité pour scruter le mot suivant du registre 5 ou terminer la deuxième phase si cet indice est supérieur à la longueur 1 de l'exposant e, exprimée en nombre de mots de k bits. Le mot du registre 5 avec pour indice Il = 1 est celui qui contient les bits de poids les plus forts de l'exposant e. Ensuite, chaque mot d'indice supérieur contient des bits de poids plus faible jusqu'au mot d'indice 1 qui contient les bits de poids les plus faibles. Une longueur de l'exposant e égale à un nombre entier de mots de longueur k, représente un cas où le bit de poids le plus fort du premier mot du registre 5, est non nul. C'est sur ce cas simplifié que le procédé est expliqué dans un premier temps. A l'intérieur de la première boucle, le processeur 2 itère une deuxième boucle d'étapes 18 à 35 pour scruter le mot courant d'indice)), par bloc de t bits. La valeur de t constituant une donnée de la mémoire 3, chaque mot de k bits contient une quantité q de blocs avec une longueur de t bits selon la formule : k = q. t + r où r est le reste de la division entière de k par t. Lorsque le reste r est non nul, testé en étape 36, le processeur 2 exécute une séquence supplémentaire d'étapes 37 à 52 semblables aux étapes 18 à 33 pour traiter un dernier bloc avec une longueur de r bits inférieure à t bits. Dans une étape 17, un indice qq de deuxième boucle est initialisé à 1 pour être augmenté d'un incrément unitaire en étape 34 à chaque itération de la deuxième boucle, jusqu'à atteindre la valeur d'indice q du dernier bloc de t bits dont un dépassement détecté en étape 35 fait sortir de la deuxième boucle pour exécution des étapes suivantes. Comme les mots d'indice 11, les blocs d'indice qq à l'intérieur d'un mot, sont scrutés en commençant par le bloc qui contient les bits de poids les plus fort du mot et en continuant par les blocs qui contiennent les bits de poids de plus en plus faibles. Dans l'étape 18, le bloc courant d'indice qq contient t bits qui codent une valeur a traitée par le processeur 2 dans sa scrutation de ce bloc. Dans l'étape 19, le processeur 2 teste si la valeur a est nulle. Un résultat positif déclenche une séquence d'étapes 20 à 23. Un résultat négatif déclenche une séquence d'étapes 24 à 33. Chacune des séquences d'étapes 20 à 23 et 24 à 33 aboutit sur l'étape 34 pour traitement du bloc suivant. La séquence d'étapes 20 à 23 constitue une troisième boucle dans laquelle l'étape 21 est exécutée t fois par le processeur 2 avec un indice de boucle tt variant de 1 en étape 20 à t par augmentation d'un incrément unitaire à chaque exécution de l'étape 22 jusqu'à dépassement détecté en étape 23 qui fait sortir de la troisième boucle. Dans l'étape 21, le processeur 2 charge la valeur y du registre 6, l'élève au carré et range la nouvelle valeur y ainsi obtenue dans le registre 6. Ainsi, dans la séquence d'étapes 20 à 23, le processeur 2 exécute t élévations au carré de la valeur y du registre 6. Dans l'étape 24 pour laquelle la valeur a est non nulle, celle-ci est considérée comme étant le produit d'un nombre impair c par une puissance de 2 d'exposant b. L'exposant b est le rang du premier bit non nul en partant du bit de poids le plus faible dans le bloc courant. En effet, ce premier bit non nul avec la succession de bits nuls de poids plus faibles, codent une puissance de 2 d'exposant b. Ce premier bit non nul avec les bits de poids plus forts dans le bloc courant, codent le nombre impair c. Le nombre impair c et l'exposant b sont alors obtenus par simples masquages sur le bloc courant d'indice qq. La séquence d'étapes 24 à 33, comprend deux boucles. Dans une quatrième boucle, le processeur 2 exécute (t-b) fois l'étape 26 avec un indice de boucle tt variant de 1 en étape 25 à (t-b) par augmentation d'un incrément unitaire à chaque exécution de l'étape 27 jusqu'à dépassement détecté en étape 28 qui fait sortir de la quatrième boucle. Dans l'étape 26, le processeur 2 charge la valeur y du registre 6, l'élève au carré et range la nouvelle valeur y ainsi obtenue dans le registre 6. Ainsi, dans la séquence d'étapes 25 à 28, le processeur 2 exécute (t-b) élévations au carré de la valeur y du registre 6. Dans une cinquième boucle, le processeur 2 exécute b fois l'étape 31 avec un indice de boucle bb variant de 1 en étape 30, à b par augmentation d'un incrément unitaire à chaque exécution de l'étape 32 jusqu'à dépassement détecté en étape 33 qui fait sortir de la cinquième boucle. Dans l'étape 31, le processeur 2 charge la valeur y du registre 6, l'élève au carré et range la nouvelle valeur y ainsi obtenue dans le registre 6. Ainsi, dans la séquence d'étapes 30 à 33, le processeur 2 exécute b élévations au carré de la valeur y du registre 6. Dans une étape 29 à la suite de l'étape 28 en sortie de la quatrième boucle et avant l'étape 30 en entrée de la cinquième boucle, le processeur 2 charge la valeur y du registre 6, la multiplie par la puissance xc d'exposant impair c obtenue dans la première phase, et range la nouvelle valeur y ainsi obtenue dans le registre 6. On constate que l'enchaînement d'étapes précédemment décrit donne bien y comme étant une puissance de x d'exposant e. Dans le cas simplifié où nous nous plaçons pour décrire le procédé dans un premier temps, le bit de poids le plus fort du premier bloc scruté, est non nul. La première valeur de a pour qq =1, est donc non nulle et ce sont les étapes 24 à 33 qui sont exécutées pour ce bloc. Pour ce premier bloc du premier mot, y initialisé à 1 en étape 15, reste à 1 par élévations successives au carré en étape 26 jusqu'à l'étape 28. En étape 29, XC est multiplié par 1. Dans les étapes 30 à 33, xc est élevé b fois au carré. A la dernière itération de la cinquième boucle, on obtient : y = ( (XC) 2) b = xa Pour un bloc d'indice qq, on sait que le bit de poids le plus faible, code une puissance de 2 dont l'exposant est la quantité de bits dans les blocs qui suivent ce bloc. C'est à dire que dans un cas particulier où tous les bits des blocs suivants seraient nuls, la valeur de l'exposant e pour ce seul bit est une puissance de 2 avec pour exposant la quantité de bits de poids plus faibles. Lorsque une valeur y qui résulte des qq itérations précédentes de la deuxième boucle, est telle que y = xn, n est une valeur d'exposant codée sur qq blocs qui correspond à n*25 codée sur (qq+1) blocs avec tous les bits nuls dans le dernier bloc. Lorsque le dernier bloc d'indice qq+1 ajoute la valeur a aux (qq+1) blocs précédents, le nouvel exposant m codé sur (qq+1) blocs, est donné par la formule : m = n*2t + a Lorsque a est nul pour le bloc d'indice qq+1, en étape 20, y = xn. En fin d'exécution de la troisième boucle : y = (xn)2**t C'est à dire y = xm. b Lorsque a est égal à c*2b, pour le bloc d'indice qq+1, en étape 25, y = xn. En fin d'exécution de la quatrième boucle : y = (xn) 2** (t-b) Après exécution de l'étape 29 : y = (x") ) En fin d'exécution de la cinquième boucle : y = ( (x"r r' y = (xn) 2** (t-b) *2**b* (xC) 2**b y = (xn) 2**t* (xa) C'est à dire y = xm. Les propriétés expliquées ci-dessus sont vérifiées de proche en proche jusqu'au dernier bloc d'indice q de sorte qu'en terminant la deuxième boucle en étape 35, la valeur de y contenue dans le registre 6, est une puissance de x dont l'exposant est codé sur q blocs. Lorsque l'indice courant qq dépasse q en étape 35, le procédé se poursuit tel que représenté en figure 4 liée par le repère A. En étape 36, le processeur 2 teste si le reste r est nul. Un résultat positif indique que le mot contient un nombre entier de blocs de longueur t et que ce mot ne contient plus de bits au delà du bloc d'indice q. L'étape 53 est alors directement activée. Un résultat négatif indique que le mot ne contient pas un nombre entier de blocs de longueur t et que ce mot contient encore un bloc réduit d'indice q+1 avec r bits au delà du bloc d'indice q. L'étape 37 est alors activée. Dans l'étape 37, le bloc courant d'indice q+1 contient r bits qui codent une valeur a traitée par le processeur 2 dans sa scrutation de ce bloc. L'étape 38 identique à l'étape 19 active une sixième boucle si la valeur a est nulle et une séquence comprenant une septième et une huitième boucle si la valeur a est non nulle. La sixième boucle est réalisée au moyen d'étapes 39 à 42 semblables aux étapes 20 à 23 à la seule différence près que le test de dépassement de t en étape 23 est remplacé par un test de dépassement de r en étape 42 de sorte que r élévations au carré de y sont effectuées lors d'exécutions de l'étape 40 par le processeur 2. La septième boucle est précédée d'une étape 43 identique à l'étape 24. La septième boucle est réalisée au moyen d'étapes 44 à 47 semblables aux étapes 25 à 28 à la seule différence près que le test de dépassement de t-b en étape 28 est remplacé par un test de dépassement de r-b en étape 47 de sorte que r-b élévations au carré de y sont effectuées lors d'exécutions de l'étape 45 par le processeur 2. En sortie de septième boucle, une étape 48 identique à l'étape 29, précède l'entrée de huitième boucle. La huitième boucle est réalisée au moyen d'étapes 49 à 52 identiques aux étapes 30 à 33 de sorte que b élévations au carré de y sont effectuées lors d'exécutions de l'étape 50 par le processeur 2. Les propriétés vérifiées sur le calcul de y pour les troisième, quatrième et cinquième boucles restent valables pour les sixième, septième et huitième boucle avec y égal à xi après traitement du dernier bloc d'indice q et y égal à xm après traitement du bloc d'indice q+1 qui contient seulement r bits. Dans l'étape 53 activée en sortie de sixième boucle, en sortie de huitième boucle ou directement ou directement après l'étape 36, l'indice courant Il de mot est augmenté d'un incrément unitaire de façon à terminer le procédé lorsque l'indice augmenté Il est détecté supérieur à 1 en étape 54. Tant que l'indice Il testé en étape 54 ne dépasse pas l'indice 1 du dernier mot du registre 5, le procédé est continué par le repère B qui relie la figure 4 à la figure 3 pour réactiver l'étape 17 de façon à scruter le premier bloc du mot suivant. Les propriétés sur le calcul de y expliquée précédemment lors du passage d'un bloc au suivant à l'intérieur d'un mot, restent vérifiées lors du passage du dernier bloc d'un mot au premier bloc d'un mot suivant. Ainsi, la valeur de y contenue dans le registre 6 est égale à la puissance de l'argument x avec l'exposant e codé dans les 1 mots du registre 5. On remarque dans le procédé expliqué ci-dessus que le processeur effectue t élévations au carré à chaque exécution de la troisième boucle, t-b élévations au carré à chaque exécution de la quatrième boucle puis b élévations au carré à l'exécution de la cinquième boucle qui suit, de sorte que le processeur 2 effectue t élévations au carré pour chaque traitement de bloc de longueur t que a soit nul ou non. Simplement, le processeur 2 effectue une multiplication supplémentaire pour un bloc de valeur a non nulle. Dans le traitement d'un mot de q blocs, le processeur 2 effectue q fois t élévations au carré et au plus q multiplications par exécutions de l'étape 29, selon le nombre de blocs de valeur a non nulle. Si le mot contient de plus un bloc réduit de r bits, le processeur effectue encore r élévations au carré et éventuellement une multiplication par exécution de l'étape 48 si la valeur a de ce bloc est non nulle. Au total, pour traiter un mot de longueur k, le processeur 2 effectue qt+r élévations au carré, c'est à dire k élévations au carré et au plus q+1 multiplications. La longueur k est imposée par la longueur des mots que le processeur 2 est prévu pour traiter. La quantité d'élévations au carré égale à k, est indépendante de la valeur de t. Seule la quantité de multiplications est sensiblement inversement proportionnelle à t. La probabilité d'avoir un bloc nul est de 0,5 pour t=1 et diminue considérablement lorsque t augmente. On pourrait penser avoir intérêt à prendre t proche de k pour réduire la quantité de multiplications. Par exemple t=k, ne nécessiterait au plus qu'une multiplication par mot. Cependant dans la première phase, le processeur doit calculer (P+1) produits en quantité égale à une puissance de 2 avec (t-1) pour exposant. La croissance exponentielle de la quantité de multiplications lorsque t approche k, amoindrit rapidement l'avantage de prendre une grande valeur de k en deuxième phase où la quantité de multiplications est seulement proportionnelle à la quantité de mots nécessaire pour coder l'exposant e et à la quantité de blocs dans chaque mot. Considérant ce qui vient d'être exposé, on comprend qu'il existe une valeur optimale de t comprise entre 1 et k pour que le processeur 2 effectue une quantité minimale de multiplications. Riche de l'enseignement qui vient d'être décrit, l'homme du métier peut aisément concevoir un programme d'optimisation en se fondant sur des considérations mathématiques qui ne font pas l'objet de la présente invention. Ce programme peut être préalablement exécuté sur un ordinateur indépendant, la valeur t calculée est alors mémorisée ou téléchargée dans la mémoire 3. Ce programme de calcul de t peut aussi résider dans la mémoire 3 de façon à optimiser la valeur de t en fonction de la longueur de chaque exposant e reçu. Le dispositif calcule la valeur optimale de t au moyen d'une inéquation transcendante paramétrée par k, t et d'un rapport a. La longueur k des mots manipulés par le processeur, est connue. Le rapport a entre le coût d'un carré et celui d'une multiplication dans les monoïdes finis est connu, par exemple au moyen d'une mesure préalable. Il est donc possible d'établir une fois pour toutes, une table pour chaque monoïde fini, chaque table donnant la valeur optimale t pour une plage de longueurs lel d'exposant. Le procédé est maintenant expliqué dans un deuxième temps sur un cas plus général où la longueur lel de l'exposante, n'est pas égale à un nombre entier de mots de longueur k. Le mot de poids fort, c'est à dire le premier mot du registre 5, contient alors une certaine quantité de bits de poids forts nuls avant un premier bit non nul qui avec les bits suivants jusqu'au bit de poids le plus faible de ce premier mot, constitue un ensemble de k'bits avec k' inférieur à k. Cet ensemble de k'bits est alors découpé en q'blocs de taille t et si besoin en un bloc supplémentaire de taille r'où q'et r'sont donnés par la division euclidienne : K'=q't+r' La première itération de la première boucle est spécialement paramétrée pour Il = 1. Dans l'étape 35, le test sur un dépassement de q est remplacé par un test sur un dépassement de q', les étapes 17 à 34 restant identiques par ailleurs. Dans l'étape 36, c'est la valeur nulle de r'qui est testée. Dans l'étape 37, c'est la valeur a codée par le bloc d'indice q'+1 qui est considérée. Dans l'étape 42, le test sur un dépassement de r est remplacé par un test sur un dépassement de r'. Dans l'étape 47, le test sur un dépassement de (r-b) est remplacé par un test sur un dépassement de (r'-b). Les étapes 38 à 41,43 à 46 et 48 à 53, restent identiques par ailleurs. Cette première itération particulière offre l'avantage de trouver une valeur non nulle de a à la première exécution de l'étape 19 et donc, de ne pas exécuter inutilement l'étape 21 dans laquelle le carré de y resterait trivialement à 1 pour des blocs de poids forts avec des bits nuls. Ainsi, le processeur 2 effectue k'élévations au carré pour le premier mot. Les itérations suivantes de la première boucle de 11=2 à 11=1, sont réalisées au moyen des étapes 17 à 54 telles qu'elles ont été décrites dans le cas simplifié, la totalité de chaque mot suivant jusqu'au mot de poids faible étant alors scruté par le processeur 2. Ainsi, la quantité d'élévations au carré, reste égale à la longueur lel de l'exposant e avec : lei = k'+ (1-1) k Le cas général couvre le cas simple avec implicitement k'=k, q'=q et r'=r. C'est pourquoi les notations k', q'et r'seront maintenant utilisées en référence au mot de poids fort qui code l'exposant e, même dans le cas particulier où k' serait égal à k. En référence à la figure 5, une première variante du procédé permet de réduire la quantité de carrés à une valeur inférieure à lel en remplaçant les étapes 15 et 16 par des étapes particulières pour le mot de poids fort du registre 5. La deuxième phase du procédé commence alors par une étape 55 dans laquelle l'indice Il de scrutation des mots du registre 5, est initialisé à 1 pour faire prendre en charge le mot de poids fort par le processeur. Dans une étape 56, l'indice qq de scrutation de blocs dans le mot, est initialisé à 1 pour faire prendre en charge le premier bloc de poids fort non nul par le processeur. Dans une étape 57, le processeur 2 considère une valeur a comme étant celle codée par les bits de ce bloc non nul. Dans une étape 58, semblable à l'étape 24, cette valeur a est considérée comme étant le produit d'un nombre impair c par une puissance de 2 d'exposant b. Dans une étape 59, la valeur de y est directement initialisée à la valeur xc calculée en première phase comme étant la puissance de l'argument x d'exposant c. Ainsi, le processeur 2 effectue sa première élévation au carré sur une valeur de y différente de 1 dans une étape 61, itérée b fois au moyen d'un indice de boucle bb préalablement initialisé à 1 dans une étape 60, incrémenté dans une étape 62 avec test de dépassement dans une étape 63. Au sortir de la boucle réalisée par les étapes 60 à 63, une étape 64 teste si q'est nul. Une réponse positive à ce test, signifie que la chaîne de bits du mot courant dont le bit de poids fort est non nul, a une longueur inférieure à t. Le premier bloc scruté est alors un bloc de taille réduite r'qui est aussi le dernier avant prise en charge du mot suivant. Le procédé continue par une étape 102 représentée en figure 7 tel que le lien de l'étape 64 vers l'étape 102 peut être suivi au moyen du repère C. Une réponse négative à ce test, signifie que la chaîne de bits du mot courant dont le bit de poids fort est non nul, a une longueur supérieure ou égale à t. Le premier bloc scruté est alors un bloc de taille réduite t qui peut éventuellement être suivi d'un autre bloc de taille t ou d'un bloc de taille réduite r', avant prise en charge du mot suivant. Une étape 65 incrémente l'indice courant de bloc dont le dépassement est testé dans une étape 66. Une réponse négative au test de l'étape 65, signifie qu'il existe un bloc suivant de taille t et le procédé continue par une étape 67 représentée en figure 6 tel que le lien de l'étape 66 vers l'étape 67 et visualisé par le repère D. Une réponse positive au test de l'étape 65, signifie qu'il n'existe pas de bloc suivant de taille t et le procédé continue par une étape 85 représentée en figure 7 tel que le lien de l'étape 66 vers l'étape 85 et visualisé par le repère E. Ainsi, le processeur 2 évite des élévations au carré triviales de valeurs unitaires de y tel qu'il pouvait le faire pour le premier bloc traité (t-b) ou (r'-b) fois dans les étapes 26 ou 45. Le procédé est optimisé en ce que la quantité d'élévations au carré est réduite d'autant. Tant qu'il existe des blocs d'indice qq inférieur à q', détecté par une étape de test 84, des étapes 67 à 83 sont réitérées. Les étapes 67 à 83 sont semblables aux étapes 18 à 34. Dans l'étape 67, le bloc courant est considéré comme codant une valeur a testée à zéro dans une étape 68. Une réponse positive au test de l'étape 68 active une étape 70 itérée t fois selon un indice de boucle tt initialisé à 1 en étape 69 et incrémenté en étape 71 jusqu'à dépassement détecté en étape 72. A chaque itération de l'étape 70, le processeur 2 effectue une élévation au carré de y. Une réponse négative au test de l'étape 68 active une étape 73 identique à l'étape 24 précédemment décrite. Ensuite une étape 75 est itérée (t-b) fois selon un indice de boucle tt initialisé à 1 en étape 74 et incrémenté en étape 76 jusqu'à dépassement détecté en étape 77. A chaque itération de l'étape 70, le processeur 2 effectue une élévation au carré de y. Que a soit nul ou non nul, l'étape 70 ou respectivement 75, fait exécuter au processeur 2, une élévation au carré sur une valeur y qui constitue déjà une puissance de l'argument x, suite aux exécutions de l'étape 59 et 61 précédentes. Ceci évite de faire des élévations inutiles au carré de valeurs unitaires. Les étapes 78 à 83 sont identiques aux étapes 29 à 35. Après incrémentation en étape 83 de l'indice de bloc qq, un dépassement de q'testé en étape 84, signifie que q'blocs de longueur t, ont été traités par le processeur 2 dans les étapes 57 à 66 puis 67 à 83 itérées (q'-1) fois. Une réponse positive au test de l'étape 84, active une étape 85 tel que visualisé par le lien E de la figure 6 à la figure 7. Chacune des étapes 85 à 102 de la figure 7 est identique à chacune des étapes 36 à 53 de la figure 4. Dans l'étape 102, l'indice de mot 11, est mis à la valeur 2 pour référencer le deuxième mot du registre 5. Une valeur de 1 supérieure à 2 provoque une réponse négative au test de l'étape 103 qui active l'étape 17 pour poursuivre la deuxième phase du procédé de façon identique à celle décrite précédemment en référence aux figures 3 et 4 pour les mots d'indice Il supérieur à 1. Le repère B visualise le lien de la figure 7 vers la figure 3. En référence à la figure 8, une deuxième variante du procédé effectue, lorsque r est non nul, un découpage du mot en q blocs de taille t et un bloc de taille réduite r de sorte que le bloc de taille réduite n'est pas systématiquement le dernier bloc du mot considéré. Le procédé décrit en référence à la figure 3 est modifié en ce que le passage de l'étape 16 à l'étape 17, est dérouté vers une étape 104 tel que visualisé par le repère J sur la figure 8. Dans l'étape 104, le processeur 2 teste si r est nul pour le mot courant. Une réponse positive ramène au procédé non modifié tel que visualisé par le repère B. Une réponse négative active une étape 105. Dans l'étape 105 et les suivante, un indice qq référence un rang de bit dans le mot d'indice courant Il, tel que qq=1 référence le bit de poids le plus fort, chaque valeur d'indice suivante référence un bit de poids plus faible que la précédente jusqu'à la valeur qq=k qui référence le bit de poids le plus faible. Dans l'étape 105, l'indice qq est initialisé à 1 pour référencer le bit de poids fort. On comprendra que pour le mot de poids fort lorsque 11=1, l'indice qq peut être initialisé au rang du premier bit de poids fort non nul en remplaçant dans la suite k par k', q par q'et r par r'. Dans une étape 106, le processeur applique un masque sur le mot courant pour interpréter une suite de r bits de rang qq à (qq+r-1) comme codant une valeur d. Une étape 107 consiste à tester une valeur nulle de d. Une réponse positive indique qu'un bloc de taille réduite r a été trouvé avec tous ses bits à zéro. Des étapes 108 à 113 sont alors activées pour effectuer r élévations au carré de y. Les étapes 108 à 111 sont identiques aux étapes 20 à 23. Une réponse négative indique qu'un bloc de taille réduite r n'a pas été trouvé avec tous ses bits à zéro. Une étape 114 est alors activée. Pour le cas où un bloc de taille réduite r a été trouvé, l'étape 112 augmente de r, l'indice qq pour se positionner sur le bit qui suit le bit de poids faible du bloc de taille réduite. L'étape 113 teste si le nouvel indice courant qq est supérieur à k. Une réponse positive indique un dépassement qui fait se poursuivre le procédé par le repère H vers une étape 162 décrite ultérieurement en référence à la figure 10. Une réponse négative indique qu'il existe encore des bits de poids faibles dans le mot courant à la suite du bloc de taille réduite r. L'existence de bits de poids faible en quantité nécessairement multiple de t, fait se poursuivre le procédé par le repère F vers une étape 127 décrite ultérieurement en référence à la figure 9. Dans l'étape 114, le processeur applique un masque sur le mot courant pour interpréter une suite de t bits de rang qq à (qq+t-1) comme codant une valeur a. C'est à dire que lorsqu'une chaîne de r premiers bits de poids fort n'est pas détectée nulle en étape 107, un bloc de t bits est considéré dans les étapes 114 à 124. La valeur de a étant nécessairement non nulle du fait que les r bits de poids fort ne sont pas tous nuls, une succession d'étapes 115 à 124 identiques chacune respectivement aux étapes 24 à 33, suit l'étape 114. Comme dans le procédé décrit en référence à la figure 3, les étapes 115 à 124 ont pour fonction de faire exécuter au processeur 2, (t-b) élévations au carré suivies d'une multiplication par une puissance d'argument x obtenue en première phase suivie de b élévations au carré. Pour le cas où un bloc de taille réduite r n'a pas été trouvé, l'étape 125 augmente de t, l'indice qq pour se positionner sur le bit qui suit le bit de poids faible du bloc de taille t. L'étape 126 teste si le nouvel indice courant qq est supérieur à q. t. Une réponse positive indique un dépassement qui fait se poursuivre le procédé par le repère G vers une étape 145 décrite ultérieurement en référence à la figure 10. Une réponse négative indique qu'il existe encore des bits de poids faibles dans le mot courant à la suite du bloc de taille t courant. Après un passage dans l'étape 113, le procédé qui se poursuit selon les repères F et H, ne repasse plus par les étapes 106 à 126. A chaque passage dans l'étape 126, un nombre entier de blocs de t bits a été traité par le processeur 2. Si q blocs ont été traités au passage dans l'étape 125, qq est égal à q. t+1 dans l'étape 126. Tant que q blocs de taille t n'ont pas été traités, l'existence de bits de poids faible en quantité nécessairement supérieure à t, fait se poursuivre le procédé par bouclage sur l'étape 106. En référence à la figure 9, le procédé continue suivant le repère F. Lorsque l'indice qq testé en étape 113, n'est pas supérieur à k, il reste des bits de poids faible dans le mot courant d'indice Il. Comme l'étape 113 fait suite au traitement d'un bloc de taille réduite r, les bits de poids faible constituent nécessairement un nombre entier de blocs de taille t. Dans une étape 127, le processeur applique un masque sur le mot courant pour interpréter une suite de t bits de rang qq à (qq+t-1) comme codant une valeur a. Dans une étape 128, le processeur 2 teste si la valeur a est nulle comme dans l'étape 19. Une réponse positive active des étapes 129 à 132, chacune respectivement identique à chacune des étapes 20 à 23 pour effectuer t élévations au carré de y. Une réponse négative active des étapes 133 à 142, chacune respectivement identique à chacune des étapes 24 à 33 pour effectuer (t-b) élévations au carré de y, suivies d'une multiplication de y par une puissance de x obtenue en première phase, suivie de b élévations au carré de y. A la suite des t élévations au carré selon les étapes 129 à 132 ou des t élévations au carré et de la multiplication selon les étapes 133 à 142, une étape 143 augmente de t, l'indice de rang de bit. Dans une étape de test 144, une valeur de qq supérieur à k, indique que le traitement du mot d'indice courant Il est terminé. Une valeur de qq non supérieure à k, indique qu'il existe encore des blocs de longueur t à traiter dans le mot d'indice courant Il. Une réponse négative au test de l'étape 144 boucle le procédé sur l'étape 127 pour traiter les blocs restants de façon identique à celle décrite en référence à la figure 3. Une réponse positive au test de l'étape 144 active l'étape 161 décrite en référence à la figure 10 tel que visualisé par le lien H de la figure 9 à la figure 10. En référence à la figure 10, le repère G fait suite à une réponse positive au test de l'étape 126 qui signifie que q blocs de taille t ont été traités sans avoir trouvé de bloc de taille réduite r constitué de bits nuls. Il reste alors un bloc de taille réduite r. Dans une étape 145, le processeur applique un masque sur le mot courant pour interpréter une suite de t bits de rang qq à (qq+r-1) comme codant une valeur a pour traiter le bloc de taille réduite restant, de façon identique à celle décrite en référence à la figure 4, au moyen d'étapes 146 à 160, identiques chacune respectivement à chacune des étapes 38 à 52. Suite à une réponse positive au test de l'étape 144,150 ou 160, l'étape 161 augmente l'indice Il d'une unité pour référencer le mot suivant du registre 5 s'il existe. Si le nouvel indice Il testé en étape 162, est supérieur à la longueur 1 de l'exposant e exprimée en nombre de mots, le procédé est fini avec y dans le registre 6, ayant pour valeur la puissance de l'argument x d'exposant e. Sinon, l'étape 162 est bouclée sur l'étape 104 ou 105 pour traiter le mot suivant du registre 5 qui code l'exposant e. Cette deuxième variante, en ne plaçant pas systématiquement le bloc de taille réduite r sur les bits de poids faible à la suite des q blocs de taille t, permet d'économiser une multiplication lorsqu'il existe un bloc de taille réduite r avec tous ses bits nuls avant un bloc de taille t. Cette deuxième variante a pour effet d'augmenter la probabilité d'apparition d'un bloc nul. La deuxième variante du procédé peut être combinée à la première variante par passage direct de l'étape 115 à l'étape 120, suite et seulement suite à la première exécution de l'étape 114. En court-circuitant les étapes 116 à 119 pour la scrutation des t bits de poids fort de l'exposant e, on retrouve les avantages de la première variante expliquée en référence à la figure 5, à savoir ceux d'éviter de faire (t-b) premières élévations au carré triviales d'une valeur unitaire de y. Le procédé est par exemple mis en oeuvre au moyen du dispositif 1 décrit en référence à la figure 1 dans la mémoire 3 duquel réside un programme constitué d'instructions et de données qui codent en langage exécutable par le processeur 2, les étapes précédemment décrites. On comprendra que les étapes telles que décrites en référence aux figures 2 à 10, l'ont été de cette manière pour faciliter la compréhension du procédé. Certaines étapes ou monoïdes d'étapes peuvent être réalisées au moyen de sous programmes judicieusement paramétrés et d'instructions standards d'un langage de programmation. Par exemple, les étapes 11 à 14 sont réalisables au moyen d'une instruction de boucle standard pour effectuer 2t-2 multiplications d'une valeur xi par un carré X2 pour générer une puissance x, +i. Les étapes 20 à 23,39 à 42,69 à 72,88 à 91,108 à 111,129 à 132 ou 147 à 150 sont réalisables au moyen d'un même premier sous programme appelé par une première instruction suite à une réponse positive à un test de valeur nulle respectivement en étape 19,38, 68,87, 107,128 ou 146, paramétré par t, r ou r'selon le cas pour le test de retour de sous programme. Le premier sous programme comprend une instruction de boucle standard pour effectuer t, r ou r'élévations au carré selon la paramétrisation. Ce même premier sous programme permet aussi de réaliser les étapes 25 à 28,44 à 47,74 à 77,93 à 96,116 à 119,134 à 137 ou 152 à 155 en étant appelé par une deuxième instruction en fin respectivement d'étape 24, 43,73, 92,115, 133 ou 151, paramétré par (t-b), (r-b) ou (r'-b) selon le cas pour le test de retour de sous programme. Ce même premier sous programme permet encore de réaliser les étapes 30 à 33,49 à 52,60 à 63,79 à 82,98 à 101,121 à 124,139 à 142 ou 157 à 160 en étant appelé par une troisième instruction en fin respectivement d'étape 29,48, 59,78, 97,120, 138 ou 156, paramétré par b pour le test de retour de sous programme. Les étapes 24 à 33,43 à 52,73 à 82,92 à 101,133 à 142 ou 151 à 160 sont réalisables au moyen d'un même deuxième sous programme appelé par une quatrième instruction suite à une réponse négative au test de valeur nulle respectivement en étape 19,38, 68,87, 128 ou 146, paramétré par t, r ou r' selon le cas. Le deuxième sous programme comprend au moins une cinquième instruction pour déterminer c et b en étape 24,43, 73,92 133 ou 151, suivie de la deuxième instruction pour appeler le premier sous programme, suivie d'une sixième instruction au retour de premier sous programme pour effectuer une multiplication selon l'étape 29,48, 78,97, 138 ou 156, suivie de la troisième instruction pour appeler le premier sous programme, suivie d'une septième instruction au retour de premier sous programme pour effectuer un retour au programme appelant. Ce même deuxième sous programme permet aussi de réaliser les étapes 115 à 124 en étant appelé par une huitième instruction en fin d'étape 114, paramétré part. L'homme du métier peut alors réaliser facilement un programme principal avec les appels de sous programmes adaptés, pour mettre en oeuvre le procédé décrit en référence aux figures 3 et 4,5 à 7 ou 8 à 10. L'invention s'applique particulièrement aux procédés cryptographiques basés l'arithmétique modulaire. Le standard le plus courant, PKCS&num;1 définit une clé secrète RSA comme un ensemble de module et d'exposant, sans possibilité d'ajouter des données, considérées secrètes que le signataire pourrait exploiter dans un algorithme propriétaire, comme des chaînes d'additions. L'invention permet des calculs RSA accélérés en utilisant les seules données de la clé secrète, définies dans la norme. Une application directe est l'implantation d'un module de calcul cryptographique dans des navigateurs utilisant la structure de données définie dans la norme. Les algorithmes à clé publique basés sur le logarithme discret (El Gamal, DSA, Guillou-Quisquater) requièrent des élévations à la puissance, modulaires avec des exposants qui varient à chaque exécution du protocole. L'apport de données auxiliaires telles des chaînes d'additions, est écarté car trop coûteux et non réutilisable avec certitude. L'invention offre une accélération des calculs à coût réduit. L'algorithme d'échange de clé de Diffie-Helmann nécessite deux élévations à la puissance, modulaires à chaque exécution. La sécurité de l'algorithme exige que les exposants changent à chaque exécution. L'invention est appliquée avantageusement pour ces calculs. Les algorithmes cryptographiques récents, basés sur les courbes elliptiques, utilisent des notations additives pour le monoïde fini : une addition remplace la multiplication, un doublement remplace le carré, une multiplication par un entier remplace l'élévation à la puissance et une initialisation à zéro remplace l'initialisation à 1. Cette modification formelle ne change rien à la portée de l'invention qui s'applique alors aux calculs y=e'x, avec e entier et x dans le monoïde fini. L'invention s'applique également aux protocoles cryptographiques basé sur le logarithme discret dans les groupes de classes et aux protocoles utilisant les groupes de tresses.- REVENDICATIONS : 1. Procédé pour élever un argument x à une puissance d'exposant e dans un groupe fini comprenant une loi de composition interne, au moyen d'un processeur (2) capable de traiter des mots de longueur k exprimée en bits, l'exposant e étant codé sur 1 mots de k bits avec 1 supérieur ou égal à 1, caractérisé en ce qu'il comprend : - une première phase de génération de puissances de l'argument x avec un exposant impair compris entre 1 et 2t-1 où t est un nombre inférieur à k ; - une deuxième phase de traitement de chaque mot qui code l'exposant e dans un ordre allant du bit de poids fort jusqu'au bit de poids faible de l'exposant e, dans laquelle : - le processeur (2) scrute le mot courant à traiter par blocs d'au plus t bits - en allant des bits de poids forts vers et jusqu'au bit de poids le plus faible du mot courant ; - pour un premier bloc scruté de premier mot tel qu'il existe dans le bloc scruté un bit non nul de poids le plus faible avec un rang b pris à partir de 1 pour le bit de poids faible du bloc, le processeur (2) charge à partir d'un registre (6), une valeur y égale à une puissance générée en première phase dont l'exposant c a pour valeur celle codée par le bit de rang b et les bits de rangs suivants jusqu'au bit de poids fort du bloc scruté, effectue b élévations au carré de ladite valeur y et range le résultat ainsi obtenu comme nouvelle valeur y dans le registre (6) ; - pour chaque bloc scruté suivant, le processeur (2) effectue des élévations au carré de ladite valeur y, en quantité égale au nombre de bits du bloc scruté, et s'il existe dans le bloc scruté un bit non nul de poids le plus faible avec un rang b pris à partir de 1 pour le bit de poids faible du bloc, le processeur (2) applique la loi de composition interne à la valeur y et à une puissance générée en première phase dont l'exposant c a pour valeur celle codée par le bit de rang b et les bits de rangs suivants jusqu'au bit de poids fort du bloc scruté, avant d'effectuer les b dernières élévations au carré de ladite valeur y et de ranger le résultat ainsi obtenu dans le registre (6) ; de sorte que la valeur y contenue dans le registre (6) après scrutation du dernier bloc comprenant les bits de poids les plus faible pour coder l'exposant e, est égale à l'argument x élevé à la puissance d'exposant e dans le groupe fini. 2. Procédé pour élever un argument x à une puissance d'exposant e selon la revendication 1, caractérisé en ce que, le bit non nul de poids le plus fort du premier mot étant de rang k'pris à partir de 1 pour le bit de poids le plus faible, le premier bloc scruté a pour bit de poids fort, le bit de rang k'dans le premier mot. 3. Procédé pour élever un argument x à une puissance d'exposant e selon la revendication 1 ou 2, caractérisé en ce que le registre (6) est initialisé avec une puissance générée en première phase dont l'exposant c a pour valeur celle codée par le bit de rang b et les bits de rangs suivants jusqu'au bit de poids fort du premier bloc scruté non nul du premier mot. 4. Procédé pour élever un argument x à une puissance d'exposant e selon la revendication 1 ou 2, caractérisé en ce qu'en début de deuxième phase, la valeur y est initialisée dans le registre (6) avec un élément neutre de la loi de composition interne et en ce que pour chaque bloc scruté à partir du premier, le processeur (2) effectue des élévations au carré de ladite valeur y, en quantité égale au nombre de bits du bloc scruté, et s'il existe dans le bloc scruté un bit non nul de poids le plus faible avec un rang b pris à partir de 1 pour le bit de poids faible du bloc, le processeur (2) applique la loi de composition interne à la valeur y et à une puissance générée en première phase dont l'exposant c a pour valeur celle codée par le bit de rang b et les bits de rangs suivants jusqu'au bit de poids fort du bloc scruté, avant d'effectuer les b dernière élévations au carré de ladite valeur y et de ranger le résultat ainsi obtenu dans le registre (6). 5. Procédé pour élever un argument x à une puissance d'exposant e selon l'une des revendications précédentes, caractérisé en ce qu'au moins chaque mot au delà du premier mot, est découpé en q blocs de taille t et, si k n'est pas un multiple de t, un bloc de taille réduite r inférieure à t. 6. Procédé pour élever un argument x à une puissance d'exposant e selon l'une des revendications 2 à 5, caractérisé en ce que le premier mot est découpé en q'blocs de taille t et, si k'n'est pas un multiple de t, un bloc de taille réduite r'inférieure à t. 7. Procédé pour élever un argument x à une puissance d'exposant e selon la revendication 5 ou 6, caractérisé en ce que pour chaque mot, la scrutation d'un bloc commence par une scrutation de bloc de taille réduite sur les bits de poids fort du bloc jusqu'à trouver un bloc de taille réduite avec tous ses bits nuls et dès qu'un tel bloc est trouvé, la scrutation des blocs suivants s'il en existe, est continuée par bloc de taille t. 8. Procédé pour élever un argument x à une puissance d'exposant e selon la revendication 5 ou 6, caractérisé en ce que pour chaque mot, la scrutation du bloc de taille réduite est faite après q scrutations de blocs de taille t. 9. Procédé pour élever un argument x à une puissance d'exposant e selon l'une des revendications précédentes, caractérisé en ce que le groupe fini est un ensemble d'entiers relatifs d'un intervalle fermé [0, N-1] et en ce que la loi de composition interne est la multiplication modulo N d'élément neutre unitaire. 10. Procédé pour élever un argument x à une puissance d'exposant e selon l'une des revendications 1 à 8, caractérisé en ce que le groupe fini est un ensemble d'entiers positifs ou nul de valeur absolue strictement inférieure à un nombre entier N et en ce que la loi de composition interne est l'addition modulo n d'élément neutre nul. 11. Dispositif pour élever un argument x à une puissance d'exposant e dans un groupe fini muni d'une loi de composition interne, comprenant un processeur (2) capable de traiter des mots de longueur k exprimée en bits, un registre (4) pour recevoir l'argument x, un registre (5) de 1 mots de k bits avec 1 supérieur ou égal à 1 pour recevoir l'exposant e, un registre (6) pour produire l'argument x élevé à la puissance d'exposant e et une mémoire (3) pour contenir des données et des instructions exécutables par le processeur (2), caractérisé en ce qu'il comprend : - un registre (7) pour contenir des puissances de l'argument x avec un exposant impair compris entre 1 et 2t-1 où t est un nombre inférieur à k contenu dans la mémoire (3) ; - des instructions contenues dans la mémoire (3) pour traiter chaque mot qui code l'exposant e dans un ordre allant du bit de poids fort jusqu'au bit de poids faible de l'exposant e, agencées pour commander le processeur (2) de façon à ce qu'en exécution : - le processeur (2) scrute le mot courant à traiter par blocs d'au plus t bits en allant des bits de poids forts vers et jusqu'au bit de poids le plus faible du mot courant ; - pour un premier bloc scruté de premier mot tel qu'il existe dans le bloc scruté un bit non nul de poids le plus faible avec un rang b pris à partir de 1 pour le bit de poids faible du bloc, le processeur (2) charge à partir d'un registre (6), une valeur y égale à une puissance générée en première phase dont l'exposant c a pour valeur celle codée par le bit de rang b et les bits de rangs suivants jusqu'au bit de poids fort du bloc scruté, effectue b élévations au carré de ladite valeur y et range le résultat ainsi obtenu comme nouvelle valeur y dans le registre (6) ; - pour chaque bloc scruté suivant, le processeur (2) effectue des élévations au carré de ladite valeur y, en quantité égale au nombre de bits du bloc scruté, et s'il existe dans le bloc scruté un bit non nul de poids le plus faible avec un rang b pris à partir de 1 pour le bit de poids faible du bloc, le processeur (2) applique la loi de composition interne à la valeur y et à une puissance contenue dans le registre (7) dont l'exposant c a pour valeur celle codée par le bit de rang b et les bits de rangs suivants jusqu'au bit de poids fort du bloc scruté, avant d'effectuer les b dernière élévations au carré de ladite valeur y et de ranger le résultat ainsi obtenu dans le registre (6) ; de sorte que la valeur y contenue dans le registre (6) après scrutation du dernier bloc comprenant les bits de poids les plus faibles pour coder l'exposant e, est égale à l'argument x élevé à la puissance d'exposant e dans le groupe fin | 12. Dispositif pour élever un argument x à une puissance d'exposant e selon la revendication 11, caractérisé en ce que la mémoire (3) contient au moins une instruction pour faire scruter par le processeur (2) le premier mot du registre (5) à partir du bit non nul de poids le plus fort de façon que ce bit étant de rang k'pris à partir de 1 pour le bit de poids le plus faible, seulement k'bits du premier mot sont traités. 13. Dispositif pour élever un argument x à une puissance d'exposant e selon la revendication 11 ou 12, caractérisé en ce que le registre (6) est initialisé avec une puissance contenue dans le registre (7) dont l'exposant c a pour valeur celle codée par le bit de rang b et les bits de rangs suivants jusqu'au bit de poids fort du premier bloc scruté non nul du premier mot. 14. Dispositif pour élever un argument x à une puissance d'exposant e selon la revendication 11 ou 12, caractérisé en ce que le registre (6) est initialisé à 1 et en ce que la mémoire (3) contient au moins une instruction pour faire effectuer par le processeur (2) des élévations au carré de ladite valeur y, en quantité égale au nombre de bits de chaque bloc scruté, et s'il existe dans le bloc scruté un bit non nul de poids le plus faible avec un rang b pris à partir de 1 pour le bit de poids faible du bloc, à faire appliquer par le processeur (2) la loi de composition interne à la valeur y et à une puissance contenue dans le registre (7) dont l'exposant c a pour valeur celle codée par le bit de rang b et les bits de rangs suivants jusqu'au bit de poids fort du bloc scruté, avant d'effectuer les b dernière élévations au carré de ladite valeur y et de ranger le résultat ainsi obtenu dans le registre (6). 15. Dispositif pour élever un argument x à une puissance d'exposant e selon l'une des revendications 11 à 14, caractérisé en ce que la mémoire (3) contient au moins une instruction pour découper au moins chaque mot au delà du premier mot, en q blocs de taille t et, si k n'est pas un multiple de t, un bloc de taille réduite r inférieure à t. 16. Dispositif pour élever un argument x à une puissance d'exposant e selon l'une des revendications 12 à 15, caractérisé en ce que la mémoire (3) contient au moins une instruction pour découper le premier mot en q'blocs de taille t et, si k'n'est pas un multiple de t, un bloc de taille réduite r'inférieure à t. 17. Dispositif pour élever un argument x à une puissance d'exposant e selon la revendication 15 ou 16, caractérisé en ce que la mémoire (3) contient au moins une instruction pour commencer sur chaque mot, la scrutation d'un bloc par une scrutation de bloc de taille réduite sur les bits de poids fort du bloc jusqu'à trouver un bloc de taille réduite avec tous ses bits nuls et au moins une instruction pour continuer dès qu'un tel bloc est trouvé, la scrutation du ou des blocs suivants s'il en existe, par bloc de taille t. 18. Dispositif pour élever un argument x à une puissance d'exposant e selon la revendication 15 ou 16, caractérisé en ce que la mémoire (3) contient au moins une instruction pour scruter le bloc de taille réduite après scrutation de q blocs de taille t. 19. Programme pour produire dans un registre (6) un argument x reçu d'un registre (4), élevé à une puissance d'exposant e reçu d'un registre (5) de 1 mots de k bits avec 1 supérieur ou égal à 1, k étant une longueur de mot exprimée en bits que peut traiter un processeur (2), caractérisé pour faire exécuter par le processeur (2) : - dans une première phase, une génération de puissances de l'argument x avec un exposant impair compris entre 1 et 2t-1 où t est un nombre inférieur à k ; - dans une deuxième phase, un traitement de chaque mot qui code l'exposant e dans un ordre allant du bit de poids fort jusqu'au bit de poids faible de l'exposant e, tel que : - le processeur (2) scrute le mot courant à traiter par blocs d'au plus t bits en allant des bits de poids forts vers et jusqu'au bit de poids le plus faible du mot courant ; - pour un premier bloc scruté de premier mot tel qu'il existe dans le bloc scruté un bit non nul de poids le plus faible avec un rang b pris à partir de 1 pour le bit de poids faible du bloc, le processeur (2) charge à partir du registre (6), une valeur y égale à unepuissance générée en première phase dont l'exposant c a pour valeur celle codée par le bit de rang b et les bits de rangs suivants jusqu'au bit de poids fort du bloc scruté, effectue b élévations au carré de ladite valeur y et range le résultat ainsi obtenu comme nouvelle valeur y dans le registre (6) ; - pour chaque bloc scruté suivant, le processeur (2) effectue des élévations au carré de ladite valeur y, en quantité égale au nombre de bits du bloc scruté, et s'il existe dans le bloc scruté un bit non nul de poids le plus faible avec un rang b pris à partir de 1 pour le bit de poids faible du bloc, le processeur (2) effectue une multiplication de la valeur y par une puissance générée en première phase dont l'exposant c a pour valeur celle codée par le bit de rang b et les bits de rangs suivants jusqu'au bit de poids fort du bloc scruté, avant d'effectuer les b dernière élévations au carré de ladite valeur y et de ranger le résultat ainsi obtenu dans le registre (6) ; de sorte que la valeur y contenue dans le registre (6) après scrutation du dernier bloc comprenant les bits de poids les plus faible pour coder l'exposant e, est égale à l'argument x élevé à la puissance d'exposant e dans le groupe fini. 20. Programme pour produire un argument x élevé à une puissance d'exposant e selon la revendication 19, caractérisé en ce qu'il est agencé pour scruter le premier bloc du premier mot à partir du bit non nul de poids le plus fort du premier mot de rang k'pris à partir de 1 pour le bit de poids le plus faible, de sorte que le premier bloc scruté a pour bit de poids fort, le bit de rang k'dans le premier mot. 21. Programme pour produire un argument x élevé à une puissance d'exposant e selon la revendication 19 ou 20, caractérisé en ce qu'il est agencé pour initialiser le registre (6) avec une puissance générée en première phase dont l'exposant c a pour valeur celle codée par le bit de rang b et les bits de rangs suivants jusqu'au bit de poids fort du premier bloc scruté non nul du premier mot. 22. Programme pour produire un argument x élevé à une puissance d'exposant e selon la revendication 19 ou 20, caractérisé en ce qu'il est agencé pour initialiser en début de deuxième phase, la valeur y à 1 dans le registre (6) et en ce que pour chaque bloc scruté à partir du premier, le programme est agencé pour effectuer des élévations au carré de ladite valeur y, en quantité égale au nombre de bits du bloc scruté, et s'il existe dans le bloc scruté un bit non nul de poids le plus faible avec un rang b pris à partir de 1 pour le bit de poids faible du bloc, pour effectuer une multiplication de la valeur y par une puissance générée en première phase dont l'exposant c a pour valeur celle codée par le bit de rang b et les bits de rangs suivants jusqu'au bit de poids fort du bloc scruté, avant d'effectuer les b dernière élévations au carré de ladite valeur y et pour ranger le résultat ainsi obtenu dans le registre (6). 23. Programme pour produire un argument x élevé à une puissance d'exposant e selon l'une des revendications 19 à 22, caractérisé en ce qu'il est agencé pour découper au moins chaque mot au delà du premier mot, en q blocs de taille t et, si k n'est pas un multiple de t, en un bloc de taille réduite r inférieure à t. 24. Programme pour produire un argument x élevé à une puissance d'exposant e selon l'une des revendications 20 à 23, caractérisé en ce qu'il est agencé pour découper le premier mot en q'blocs de taille t et, si k'n'est pas un multiple de t, un bloc de taille réduite r'inférieure à t. 25. Programme pour produire un argument x élevé à une puissance d'exposant e selon la revendication 23 ou 24, caractérisé en ce qu'il est agencé pour commencer pour chaque mot, la scrutation d'un bloc par une scrutation de bloc de taille réduite sur les bits de poids fort du bloc jusqu'à trouver un bloc de taille réduite avec tous ses bits nuls et dès qu'un tel bloc est trouvé, la scrutation des blocs suivants s'il en existe, pour continuer la scrutation par bloc de taille t. 26. Programme pour produire un argument x élevé à une puissance d'exposant e selon la revendication 23 ou 24, caractérisé en ce qu'il est agencé pour scruter le bloc de taille réduite après q scrutations de blocs de taille t d'un mot.