Brevet FR2930696A1 — publié le 20091030

Préambule de la description Domaine concerné La présente invention concerne l'évaluation de la vulnérabilité d'un algorithme de cryptographie faisant appel à une exponentiation modulaire d'une racine primitive d'un nombre premier ; plus particulièrement, l'invention concerne un procédé pour déterminer de manière heuristique la valeur d'un logarithme discret. Problème posé Le problème des logarithmes discrets a une importance industrielle primordiale. La plupart des systèmes cryptographiques à clé publique, notamment l'algorithme DiffieùHellman, sont fondés sur l'hypothèse que les calculateurs numériques ne disposent pas des ressources informatiques suffisantes (capacité mémoire, puissance de calculs) pour résoudre l'équation modulaire en x, a = gP,^x modp ; où, p est un nombre premier comportant un très grand nombre de bits et gp,; une racine primitive de p. Il est exact qu'à ce jour, aucune méthode effective de calcul des logarithmes discrets n'a été proposée ; à l'inverse, il n'est pas établi qu'il est impossible de concevoir de telles méthodes. Autrement dit, la sécurité des systèmes de transaction électronique mettant en oeuvre ces systèmes cryptographiques n'a pas d'autre support que la conviction intime des mathématiciens les plus éminents de notre époque. Une procédure heuristique mettant en évidence la possibilité pratique de déterminer le logarithme discret d'un résidu donné constitue donc un outil d'évaluation de la pertinence de l'hypothèse communément adoptée ; il est essentiel de pouvoir tester les algorithmes cryptographiques couramment mis en oeuvre dans l'industrie dans la perspective d'écarter ceux qui présentent des défaillances. Tel est le problème posé par la présente invention ; sa solution constitue un progrès décisif. Un mathématicien peut à juste titre souligner qu'une approche heuristique ne constitue pas une preuve absolue. Bien qu'une étude théorique soit de nature à établir les fondements mathématiques des résultats obtenus par une voie heuristique, une telle étude sort du champ de la présente description. Il s'agit ici de mettre à la disposition des experts des outils techniques compatibles avec des ressources informatiques raisonnables ; avec les outils techniques selon la présente invention, les experts sont en mesure de juger si le caractère irréversible des exponentiations modulaires est un pari justifié. Par rapport à cet objet, l'exposé des lois mathématiques justifiant le bon fonctionnement de ces outils ne présente qu'un intérêt au plan de la recherche fondamentale ; l'essentiel est de constater que les outils techniques ci-après décrits produisent les effets annoncés et qu'ils mettent à la portée des calculateurs numériques le calcul des logarithmes discrets. Art antérieur L'algorithme � Baby Step Giant Step � conçu par D. Shanks et les perfectionnements de celui-ci sont généralement considérés comme étant les plus performants ; ils requièrent environ O(p^l/2) espaces mémoire et 0(p^1/2) étapes de calcul ; ils dépassent les possibilités des calculateurs numériques contemporains lorsque p est un très grand nombre premier. Pour une valeur du modulo p définie et une racine primitive go donnée, l'algorithme � Baby Step Giant Step � enchaîne des phases de calcul et des phases de test jusqu'à l'occurrence d'une collision ; la valeur de l'exposant varie à chaque étape selon un pas résultant des valeurs obtenues lors des étapes antérieures. Scholie (début) (1) L'algorithme � Baby Step Giant Step � ne met pas en oeuvre les valeurs des résidus a = gp,;^n modp obtenues pour les autres primitives gp,; de p ; a fortiori, cet algorithme fait abstraction de la distribution des résidus pour des valeurs de p différentes de celle pour laquelle on recherche la valeur du logarithme discret. (2) On peut comprendre qu'il soit difficile de concevoir une approche globale prenant en compte la distribution des résidus des puissances n i-èmes de toutes les racines primitives modulo un nombre premier quelconque ; il est difficile d'augurer qu'une telle approche globale peut faciliter le calcul des logarithmes discrets. Pour mesurer le caractère impensable ù au sens propre du terme ù d'une telle approche globale, il suffit de considérer la table des résidus modulo un petit nombre premier de deux chiffres. Même pour des modulo de deux chiffres, la dispersion des résidus paraît déjouer toute tentative pour révéler l'existence d'éventuelles régularités. A fortiori, imaginer une procédure fondée sur la dispersion globale des résidus semble irréaliste. (3) Un problème de même nature est apparu dans le cas de la grande conjecture de Fermat (x 'n + y^n = z^n). Toutes les tentatives connues pour confirmer cette conjecture se sont efforcées de généraliser à l'ensemble des exposants les démonstrations effectives pour certaines de leurs classes d'appartenance ; la démonstration aboutie d'Andrew Wiles ne sort pas de ce cadre. Or, l'auteur a montré qu'une approche globale applicable à toutes les valeurs d'exposants est concevable ; autrement dit, l'auteur a mis en évidence qu'il existe une voie directe pour décrire l'ensemble des éventuelles solutions de l'équation de Fermat. (4) On ne doit pas s'étonner de l'existence de descripteurs permettant de traiter des ensembles comportant de grandes collections d'éléments ; les mathématiques du chaos et des systèmes complexes ont permis de prendre conscience qu'il est possible dans certains cas d'exprimer par des lois simples des relations foisonnantes entre une multitude d'éléments. C'est en ayant présent à l'esprit les nouveaux développements des sciences mathématiques qu'il convient de revisiter les algorithmes concernant le calcul des logarithmes discrets. Scholie (fin) Solution L'invention a pour objet un procédé pour évaluer la vulnérabilité d'un algorithme de cryptographie faisant appel à une exponentiation modulaire d'une racine primitive gP,k d'un nombre premier p. Le nombre premier p est le modulo de l'exponentiation modulaire. L'algorithme de cryptographie dont on cherche à évaluer la vulnérabilité est mis en oeuvre dans un calculateur numérique comportant des ressources informatiques. Le nombre premier p constituant le modulo d'une exponentiation modulaire comporte un si grand nombre de chiffres que la construction d'une table Tp des résidus gp,k^n modp des exponentiations modulaires de la racine primitive modulo le nombre premier p excède lesdites ressources informatiques. Il en résulte que le calculateur numérique mis en oeuvre ne permet pas de calculer un logarithme discret d'un résidu donné d'une exponentation modulaire en procédant à une inversion d'une table Tp des résidus des exponentiations modulaires. Pour mettre en évidence la vulnérabilité de l'algorithme de cryptographie le procédé, selon l'invention, consiste à calculer la valeur d'un logarithme discret en mettant en oeuvre au moyen dudit calculateur numérique les étapes suivantes: • l'objet de la première étape est de sélectionner de manière heuristique des descripteurs ayant des formes quadrangulaires imbriquées ; les descripteurs choisis explicitent la structure de la table des résidus des exponentiations modulaires sans qu'il soit nécessaire de calculer les valeurs numériques de chacun des résidus ; les descripteurs occupent dans la table des résidus des positions liées à la valeur du rang k des racines primitives gp,k ; • l'objet de la deuxième étape de déterminer la position dans la table des résidus du descripteur spécifique relatif à la racine primitive considérée et au résidu dont on cherche à calculer la valeur du logarithme discret. De préférence selon l'invention, dans le cas où (pù1)/2 est impair, on sélectionne des formes quadrangulaires imbriquées se présentant sous la forme de prismes parallélépipédiques. De préférence selon l'invention, dans le cas où (pù1)/2 est pair on sélectionne des formes quadrangulaires imbriquées se présentant sous la forme de parallélogrammes descripteurs. Plus particulièrement dans ce cas, chaque parallélogramme descripteur spécifique a une base ; le procédé selon l'invention est tel que pour déterminer la position du descripteur spécifique dans la table des résidus on repère la position de la base au moyen d'un indice variant de manière modulaire en fonction d'un incrément Sp,k caractéristique du rang k de la racine primitive gp,k considérée. Le modulo selon lequel varie ledit indice caractérisant la position de la base est égal à (p-1)/2. Le calcul de l'indice révèle la position du descripteur spécifique relatif à la racine primitive considérée et au résidu dont on cherche à calculer la valeur du logarithme discret. La valeur du logarithme discret est directement liée à celle de l'indice ainsi calculé. Description détaillée Chapitre I Brisures de symétries et émergence de régularités Puisque l'objectif annoncé est de fonder le calcul des logarithmes discrets sur une connaissance globale de la dispersion des résidus, il convient de mettre en place des descripteurs permettant de suivre l'évolution de la dispersion des résidus lorsque le modulo p augmente. Scholie (début) (1) In fine ce qui compte c'est la dispersion des résidus dans le cas où p comprend au moins une centaine de chiffres ; il peut donc paraître illusoire de s'intéresser à la dispersion des résidus dans des tables de petites tailles ; toutefois, dans le cadre d'une approche heuristique une telle critique est moins fondée. (2) Il va de soit que la dispersion des résidus ne présente pas un caractère aléatoire ; le processus permettant de calculer ceux-ci pour les différentes valeurs des racines primitives pour un modulo p premier déterminé est complètement déterministe ; les résidus occupent des emplacements prédéterminés dans les tables. (3) Il apparaît utopique de vouloir expliciter dans une expression synthétique l'emplacement de tous les résidus. En revanche, on peut s'intéresser à la structure des formes géométriques dessinées par les résidus de même poids et rechercher si ces formes géométriques présentent des caractéristiques communes ; plus précisément, il paraît concevable de décrire et prédire comment ces formes générales évoluent pour différentes valeurs du modulo p, en faisant abstraction des valeurs numériques particulières des résidus. Si un tel objectif est atteint, on est en mesure de proposer une description dynamique de la dispersion des résidus. (4) A cet égard, l'examen des premières tables permet de prendre conscience que des brisures de symétries et l'émergence de régularités se manifestent dans leur généralité de manière évidente même lorsque les tables comportent peu d'éléments. Une telle approche heuristique pose les jalons d'une méthode générale d'analyse. Scholie (fin) Chapitre II Système de représentation des régularités Le suivi des brisures de symétries et de l'émergence des régularités nécessite de formaliser la mise en place d'un système de représentation de celles-ci applicable à des modulo p comportant plusieurs centaines de chiffres. Tel est l'objet du chapitre II. � L'écrin II convient en premier lieu d'expliciter la structure de la table ; ci après également appelée écrin. On utilise la notation indicielle TP pour désigner la table des résidus modulo des puissances n ièmes des racines primitives. Les racines primitives de p sont classées par ordre de poids croissants ; la notation gP,k désigne la k ièmes racine primitive de p. L'exposant n apparaissant dans la congruence a= gp,kAn modp prend des valeurs comprises entre 1 et p ; on vérifie que de manière connue gP k^ l modp = gp,k, gP,k^(p-1) modp = 1 et gp,k^p modp = O. On dispose donc d'un système de deux indices k et n pour définir la case KP,k,,, de la table TP dans laquelle est portée la valeur du résidu correspondant. Par convention, les colonnes de la table TP sont attribuées aux racines primitives gp,k ; la kûième racine primitive gp,k occupe le kûième rang. Les lignes de la table TP sont attribuées aux exposants n ; les lignes n=p-1 et n=p sont omises. Avec ces conventions, la case la plus au nord et la plus à l'ouest de la table est la case L'ensemble des cases de la table constitue l'écrin EP ; la terminologie imagée employée trouve son origine dans la notion de colliers de perles dont la suite de l'exposé fait amplement usage. Lorsque la valeur de p augmente le nombre de colonnes de l'écrin varie ; le nombre de colonnes de l'écrin est égal à (1)(p-1) ; dans cette expression est l'indicatrice d'Euler ou, en langue anglaise, la � totient function �. Le nombre de colonnes de l'écrin ne croît pas nécessairement lorsque p croît. � Notion d'écrin compacte Le nombre de lignes des écrins Ep comportant un nombre déterminé de colonnes varie entre une limite inférieure et une limite supérieure ; lorsque le nombre de ligne atteint la limite inférieure la compacité de l'écrin considéré est maximale ; on qualifie de compacts les écrins présentant cette particularité. � L'axe de symétrie nord-sud Sv et l'axe de symétrie est-ouest SH On place sur l'écrin l'axe de symétrie Sv de direction nord-sud. Le nombre des racines primitives est pair et égal à km.. L'axe de symétrie Sv est mitoyen aux cases d'indice km/2 et (kn,.+2)/2 . On place sur l'écrin l'axe de symétrie SH de direction est ouest partageant l'écrin en deux parties. Comme p est impair, pû2 est impair ; nécessairement, l'axe de symétrie SH passe par le milieu des cases de la ligne médiane d'indice (pûl)/2. Les cases de la ligne d'indice (pû1)/2 sont appelées les cases médianes. Si (pû l )/2 est impair, la demi partie nord de même que la demi partie sud comporte un nombre de lignes pair ; si (pûl)/2 est pair, la demi partie nord de même que la demi partie sud comporte un nombre de lignes impair. On place également sur l'écrin les axes de secondaires SH12 de direction est ouest de la demi partie nord et de la demi partie sud ; ils traversent des lignes de cases ou sont mitoyens à des cases selon que (pû1)/2 est pair ou impair. � Notion de colliers de perles Pour matérialiser la répétition des résidus, on construit pû2 colliers de perles Cp,r. Chaque collier de perles est constitué d'un fil passant par les cases contenant des résidus de poids r identiques ; des perles enfilées sur le fil du collier matérialisent l'emplacement des cases de même poids résiduel. En fait, à la valeur r des résidus spécifiques au collier de perles Cp,r, on substitue l'indice n~ de l'exposant de la première perle du collier C. ; autrement dit, on utilise l'indice ne de la case occupée par la première perle du collier ; l'expression du collier de perles Cp,r devient Cm,. La notation Ep utilisée pour désigner l'écrin associé au nombre premier p est approprié lorsque l'exposé entend mettre l'accent sur les positions relatives des perles matérialisant les résidus de poids identiques. En revanche la notation TP pour désigner la table des résidus est appropriée lorsqu'il y a lieu de mettre l'accent sur les valeurs numériques des résidus. Scholie (début) (1) On visualise ainsi par une forme géométrique spécifique les résidus ayant des poids identiques. A chaque collier de perles CP, de la table TP correspond une valeur d'exposant ne unique, lue dans la colonne de gauche de la table. (2) Les perles sont de couleur noire pour les colliers d'indice ne inférieur à (pû1)/2 (plus précisèment, dans le cas du présent document, les perles sont en pointillés noires) et de couleurs blanches pour les colliers d'indice ne supérieur à (pû1)/2 ; les fils de liaison entre les perles sont dessinés en traits pleins dans les cas des perles blanches et en traits pointillés dans le cas des perles noires. Scholie (fin) � Notion de parure On appelle parure le couple formé des colliers CP,nc et CP(P_1)_äc. On désigne une parure par la notation PP,ne. Quelle que soit la valeur de p, les deux colliers de perles CP.,,, et CP (P_I)ùnc composant une parure PP,nc sont disposés symétriquement par rapport à l'axe de symétrie SH. Ainsi, il suffit de connaître la dispersion des résidus de la partie nord de l'écrin pour connaître celle de la partie sud ; cette observation est triviale ; la symétrie nord-sud des tables de résidus est en soi connue. Dans tous les cas les perles d'une parure située sur une ligne sont en nombre pair, à raison d'une perle noire pour une perle blanche ; ce trait est moins évident ; ce n'est que pour des valeurs de ne particulières que les lignes concernées comportent plus de deux perles. � Notion de descripteur quadrangulaire Le constat selon lequel dans tous les cas les perles noires et blanches apparaissent aux sommets de formes présentant un centre de symétrie permet d'introduire la notion de descripteur quadrangulaire. Ces descripteurs quadrangulaires sont composés de rectangles si le nombre de colonnes de l'écrin est égale à 2 ; ce cas est peu fréquent, la plupart des tables de résidus mises en oeuvre dans les sytèmes cryptographiques comportent plus de deux colonnes. Si le nombre de colonnes de l'écrin est supérieur à 2, les descripteurs quadrangulaires se présentent sous la forme de parallélogrammes imbriqués. � Structure des descripteurs quadrangulaires et parité de (pû1)/2 • Dans le cas où (p-1)/2 est pair : • • Les parures Pp,,,c de rang ne pair sont symétriques par rapport à l'axe Sv ; les descripteurs quadrangulaires gouvernant la structure des parures sont des parallélogrammes ayant pour centre de symétrie le point d'intersection O de l'axe Sv avec l'axe SH. • • Les descripteurs quadrangulaires gouvernant la structure des parures PP äe de rang n, impair sont des parallélogrammes ayant pour centre de symétrie le point d'intersection de l'axe Sv avec l'axe secondaire SH,N nord ou avec l'axe secondaire SH/s sud ; ces centres de symétries secondaires sont ci-après notés ON et Os. Dans le cas où (pûl)/2 est pair, les descripteurs quadrangulaires sont plus particulièrement appelés des parallélogrammes descripteurs. • Dans le cas où (pû1)/2 est impair les formes quadrangulaires se dédoublent ; des formes géométriques prismatiques se déploient; elles ont l'apparence de prismes parallélépipèdiques s'étendant de manière virtuelle (en perspective) en trois dimensions. Scholie (début) (1) On peut suivre la disparition ou l'émergence progressive des prismes parallélépipédiques au fur et à mesure que p décroît ou croît ; une lecture dynamique des écrins révèle des vibrations caractérisées par le basculement puis l'éclatement des prismes parallélépipédiques. (2) Les prismes parallélépipédiques présentent des régularités caractérisées par des symétries centrales. Il en résulte que les temps de calculs des formes parallélépipédiques, de même que ceux des parallélogrammes, ne nécessitent pas de ressources informatiques déraisonnables. (3) La suite de l'exposé concerne essentiellement les cas où on met en oeuvre des parallélogrammes descripteurs ; autrement dit, l'exposé qui suit est limité au cas où (pù1)/2 est pair ; les enseignements qu'il contient sont transposables mutatis mutandis aux prismes parallélépipédiques émergeant dans le cas où (pù1)/2 est impair. Scholie (fin) � Notion de parures conjuguées. Deux parures Pp, et PP,11 sont dites conjuguées si les indices n, et nc' les caractérisant sont tels que : + n,' = (pùl)/2, si ne et nc' ont des valeurs inférieures à (pù1)/2 ou, dans le cas des parures conjuguées du demi écrin sud, tels que : ne + = 3(p-1)/2, si n, et n: ont des valeurs comprises entre (pù1)/2 et pùl. Quel que soit p premier le terme pù1 est pair ; dans tous les cas, connaissant l'indice ne on sait déterminer l'indice conjugué nc'. On utilise la notation PP,nc, pour désigner la parure conjuguée de la parure PP,,,c. Quel que soit p, deux parures conjuguées PP, et PP,,,,, présentent entre elles des régularités inhérentes au caractère pair de pù1. Les parties de deux parures conjuguées respectivement situées au nord de l'axe secondaire SH/N et comprises entre l'axe SH et l'axe secondaire SH,N sont disposées symétriquement (sans inversion de couleurs des perles) par rapport à l'axe secondaire correspondant SH,N. Si (pù1)/2 est pair l'axe secondaire SH/N traversent les cases de la ligne (pù1)/4. Si (pù1)/2 est impair l'axe secondaire SH,N est mitoyen aux cases des lignes [(pùl)/2ù1 ]/2 et [(pù1)/2+1 ]/2 ; autrement dit si (pù1)/2 est impair l'axe secondaire SH,N est mitoyen aux cases des lignes (p-3)/4 et (p+1)/4. De même, les parties de deux parures conjuguées respectivement situées d'une part au sud de l'axe secondaire SH,S et d'autre part entre l'axe SH et l'axe secondaire SHIS sont disposées symétriquement (sans inversion de couleurs des perles) par rapport à l'axe secondaire correspondant S. Si (p-1)/2 est pair l'axe secondaire SH,S traverse les cases de la ligne 3(p-1)/4. Si (p-1)/2 est impair l'axe secondaire SH/S est mitoyen aux cases des lignes 3(pùl)/4ù1 et 3(p-l)/4+l ; autrement dit si (p-1)/2 est impair l'axe secondaire SH/S est mitoyen aux cases des lignes (3p-7)/4 et (3p+1)/4. Chapitre II. Aperçu des régularités dans le cas où (p-1)/2 est pair. Dans le cas où (p-l)/2 est pair d'autres régularités que celles précédemment décrites émergent ainsi que cela va être ci-après exposé. En fait, ces régularités apparaissent de manière voilée ; l'étude numérique suggère certaines régularités complémentaires sans les révéler complètement ; les régularités aperçues fournissent des indications permettant d'orienter la quête ; c'est à ce titre qu'il est avisé de présenter les premiers résultats obtenus avant de chercher à les approfondir. � Bracelets On a vu que dans le cas où (p-1 )/2 est pair, les perles des parures sont disposées symétriquement : • soit par rapport au centre de symétrie O (lorsque ne est pair), • soit par rapport aux centres de symétries ON et OS (lorsque ne est impair) ; corrélativement, les parures sont scindées en bracelets situés dans chaque quart de l'écrin. De même que les perles, les bracelets sont disposés symétriquement par rapport aux centres de symétries ON et Os ou par rapport au centre de symétrie O. � Régularités relatives au nombre de descripteurs Dans le cas où (pû1)/2 est pair le nombre de colonnes de l'écrin est un multiple de quatre ; autrement dit, 4)(pû1) est divisible par quatre. Chaque parure Pp,nc comporte une perle noire et une perle blanche dans chaque colonne ; au total le nombre de perles associées à chaque parure est égal à 2xI (pû1)]. Or, chacun des descripteurs d'une parure consomme quatre perles, deux perles blanches et deux perles noires ; de plus les perles des chacun des descripteurs sont distinctes ; par conséquent, le nombre des descripteurs d'une parure est égal à 1�pû1)1/2 ; les descripteurs d'une parure ont des formes (largeur, hauteur et orientation) et des positions différentes. Les parures d'indice ne pair comportent autant de descripteurs que les parures d'indice ne impair. • Dans le cas où l'indice n~ d'une parure est pair, un premier groupe comprenant [4(pû1)]/4 parallélogrammes descripteurs (d'orientation nordûouest/sudûest) concerne toutes les perles situées dans la quart nord ouest et le quart sud est ; un second groupe comprenant également [�pû1)]/4 parallélogrammes descripteurs (d'orientation nordûest/ sudûouest) concerne toutes les perles situées dans le quart nordûest et le quart sudûouest ; les parallélogrammes descripteurs du premier groupe présente une symétrie miroir d'axe Sv par rapport aux parallélogrammes descripteurs du second groupe. Les parallélogrammes descripteurs de chacun des deux groupes sont symétriques par rapport au centre 0. • Dans le cas où l'indice n~ d'une parure est impair, un premier groupe comprenant 4(pû1) ]/4 parallélogrammes descripteurs concerne les perles situées dans le demi écrin nord ; un second groupe comprenant également [4(pû1)1/4 parallélogrammes descripteurs concerne les perles situées dans la demi écrin sud ; les parallélogrammes descripteurs du premier groupe présente une symétrie miroir d'axe SH par rapport aux parallélogrammes descripteurs du second groupe. Les parallélogrammes descripteurs de chacun des deux groupes sont respectivement symétriques par au centre ON ou OS. � Système de notation des parallélogrammes descripteurs A chaque parure Pp, d'indice ne impair donné correspond [4(pû1)]/4 parallélogrammes descripteurs dans le demi écrin nord et autant dans le demi écrin sud ; sauf mention explicite, on ne considère dans la suite de l'exposé que les parallélogrammes descripteurs du demi écrin nord. Chaque parallélogramme descripteur comporte deux bases d'orientation est-ouest et deux cotés inclinés par rapport aux bases. Parmi les parallélogrammes descripteurs d'une parure donnée situés dans le demi écrin nord, aun seul a son sommet le plus à l'ouest situé dans la colonne d'indice k.. Corrélativement, le sommet le plus à l'est est situé dans la colonne de rang [4(p-1)]/2+1ûk. La base sur laquelle est situé le sommet le plus à l'ouest est appelée la base Ouest. La base sur laquelle est située le sommet le plus à l'Est est appelée la base Est On utilise la notation PDPnc,k pour désigner le parallélogramme descripteur ainsi spécifié ; l'expression � le parallélogramme descripteur de rang k de la parure PP,n~ � vise également le parallélogramme descripteur noté PDP äc.k (étant sous entendu qu'il s'agit du parallélogramme descripteur situé dans le demi écrin nord). Dans la suite de l'exposé on utilise également l'expression concise � descripteur PDP,,,C,k �. Soit un des [4(pû1) 1/4 parallélogrammes descripteurs de la parure PP äe ; soit le sommet le plus à l'Ouest du parallélogramme descripteur considéré ; le sommet le plus à l'Ouest n'est pas nécessairement le sommet le plus au nord du parallélogramme descripteur considéré. L'abscisse k du sommet le plus à l'ouest, comptée selon l'axe Ouest-Est, correspond à l'indice de la colonne où se trouve ce sommet ; l'orgine k=1 des abscisses correspondant à la première colonne de l'écrin. On utilise la notation bP,nc,k pour désigner l'indice de la ligne passant par le sommet le plus à l'Ouest. La base Ouest à l'extrémité de laquelle se trouve le sommet le plus à l'ouest est sur la ligne d'indice bP,,,C,k ; la notation bp,,,C,k renvoie la ligne sur laquelle est située la base ouest du parallélogramme descripteur de rang k de la parure Pm,. Dans la suite de l'exposé, on utilise également l'expression concise �base bp.oc,k � pour désigner la base ouest du descripteur PDP,fc,k. � Coordonnées des sommets des descripteurs PDP,fic,k Soit une parure Pm, d'indice n, donné ; la parure Pp,pc est décrite par [�pû1)1/4 descripteurs PDP,nc,k dans le demi écrin nord et autant dans le demi écrin sud. Le paramètre k prend [4(pû1)]/4 valeurs comprises entre 1 et 4(pû1)1/4 ; à chacune des 14(pû1)1/4 valeurs de k correspond une valeur de l'indice bP,,C k déterminant la base du descripteur PDP,,,C,k de rang k considéré. La connaissance de k et bP,,,C,k détermine la position dans l'écrin EP du sommet le plus à l'ouest de la base ouest du descripteur PDP,fC,k de rang k de la parure Pm,. La valeur de k spécifie de manière univoque la largeur IP.nc.k de la base considérée ; la largeur lp,nc,k de la base ouest du descripteur PDP,nc,k de rang k de la parure Pp,nc ne dépend pas de la valeur de l'indice n, de la parure ; la largeur 1P,nc,k de la base ne dépend que du rang k du descripteur PDP,nc,k. Les valeurs de k, bP,nc,k et lp.nc.k permettent de calculer les coordonnées des quatre sommets Sk,a, Sk,b, Sk,c et Sk,d du descripteur PDp,nc,k de rang k de la parure Pp ne : k, bp nc,k k+ lp nc,k' bp,nc,k 4)(pû1)+1ûk, (pû l )/2û bp nc,k cé(pûl)+1ûk û 1pnck' (p-1)/2- bp,nc,k � Régularités affectant l'appariement des colonnes et des lignes. Ces autres régularités concernent les corrélations entre l'indice k des racines primitives gp,k et l'indice ne des parures. Il existe une correspondance entre certaines lignes d'indice n, de l'écrin et les colonnes d'indice k. Toutes les 10 lignes ne sont pas associées à une colonne. Seules sont appariées les lignes d'indice ne de l'écrin Ep dont la première case Kim, contient un résidu de même poids que la racine primitive gp,k de la colonne d'indice k. Les règles générales peuvent être synthétisées de la manière suivante. Il n'existe aucune ligne paire appariée. Si, par convention, on attribue le symbole 1 aux 15 lignes qui sont appariées et le symbole 0 aux lignes qui ne le sont pas on obtient des séquences du type : 1010100010101. Dans tous les cas, les tronçons nord et sud des séquences énonçant les lignes appariées sont diposés symétriquement par rapport à la ligne (pû1)/2 ; la ligne (pû1)/2 est une ligne paire non appariée. Les deux demis tronçons nord sont disposés symétriquement par rapport à la 20 ligne (pû1)/4 ; de même, les deux demis tronçons sud sont disposés symétriquement par rapport à la ligne 3(pû1)/4. Quelle que soit la parité de (pû1)/4, les lignes (pû1)/4 et 3(pû1)/4 ne sont jamais appariées. Scholie (début) (1) L'écrin Ep comporte moins de colonnes que de lignes ; les règles 25 d'appariement des colonnes et de lignes permettent d'adapter le nombre de colonne au nombre de lignes en écartant certaines d'entre elles ; le nombre de lignes appariées est égal au nombre de colonnes ; le nombre de colonnes est égal à 4(pûl) où la fonction 4 est l'indicatrice d'Euler, ou encore en langue anglaise la � Totient function �. 30 (2) Si les contraintes résultant des valeurs de 1)(pû1) imposent de prévoir d'autres lignes non appariées outre les lignes présentent dans tous les cas, alors Sk,a Sk,b Sk,c Sk,d5 ces autres lignes non appariées s'insèrent en premier lieu aux lignes d'indice 3, (pûl)/4-3, (pû1)/4+3, (pûl)/2û3 ainsi qu'aux lignes symétriques de celles-ci par rapport à la ligne (pû1)/2. Scholie (fin) � Détermination des racines primitives On sait déduire la valeur des racines primitives des règles d'appariement des lignes et des colonnes et des séquences codifiant les lignes appariées. � Notion de parure primitive Certaines parures Ppäc d'un écrin EP présentent un caractère particulier ; les indices de ces parures correspondent à des lignes appariées. Par analogie avec le concept de racine primitive, ces parures sont ci-après appelées des parures primitives ; elles sont notées Pm,. ; l'astérisque � * � permet de distinguer les parures primitives des autres parures primitives ayant un indice de ligne ne quelconque. � Notion de parure primitive générique Parmi toutes les parures primitives, il en existe une pour laquelle la base du descripteur PDP,,,c*,k de rang k est située sur la première ligne n=1 du demi écrin nord. On utilise la notation ne*Nk pour désigner l'indice d'une parure primitive dont le descripteur PDP,flc,k de rang k a sa base sur la première ligne (n=1) du demi écrin nord. Selon une convention d'écriture précédemment énoncée, l'astérisque � * � rappelle que la parure PP nc* considérée est une parure primitive ; la lettre majuscule N apparaissant en exposant après l'astérisque � * � spécifie que la base considérée est sur la ligne n=l la plus au nord du demi écrin nord. De même, parmi toutes les parures primitives il en existe une pour laquelle la base du descripteur PDP,äC*,k de rang k est située sur la dernière ligne n=(p-3)/2 du demi écrin nord. On utilise la notation ne*sk pour désigner l'indice d'une parure primitive dont le descripteur PDP nc,k de rang k a une base sur la dernière ligne n=(pû3)/2 du demi écrin nord. La lettre majuscule S apparaissant après l'astérisque � * � spécifie que la base est sur la ligne n=(pû1)/2 la plus au sud du demi écrin nord. En notation indicielle, on écrit ne*Nk sous la forme •nc*Nk et ne*sk sous la forme •nc*sk De manière cohérente avec ce système de notations, on a : bpne*N,k=1 et bpnc*s,k=(Pû3)/2. Les parures Pp ne*Nk et Pp,nc*sk dont les descripteurs de rang k ont leurs bases sur les lignes bpnc*N,k=1 et bpnc*s,k=(pû3)/2 sont dénommées les parures primitives génériques de rang k nord et sud. Corrélativement, les descripteurs PDpnc*N,k et PDp,ne*s,k de rang k dont les bases ont pour indice bpnc*N,kû1 et bpnc*s,k=(Pû3)/2 sont dénommés dans la suite de l'exposé les descripteurs génériques de rang k nord et sud. Corrélativement, également, les bases bpnc*N,k=l ou bpnc*s,k= (pû3)/2 sont ci-après appelées les bases primitives génériques nord et sud. Scholie (début) (1) Le système de notation utilisé permet de distinguer les bases génériques situées sur la ligne n=1 des bases génériques situées sur la ligne (pû3)/2 de l'écrin Ep. (2) La qualification de générique pour spécifier certaines parures primitives ainsi que certains descripteurs ou certaines bases est appropriée dans la mesure où on sait construire à partir de ceux-ci les autres descripteurs des autres parures primitives ; cette question est plus particulièrement développée dans les paragraphes qui suivent. Scholie (fin) � Parures conjuguées génériques de rang k L'objectif du présent paragraphe est de mettre en évidence la relation liant les indices ne*Nk et ne*ks des deux parures primitives génériques de rang k. Soit deux parures conjuguées Pp,nc et Pp(p_1)/2-nc; on sait que les descripteurs de ces deux parures conjuguées sont disposés symétriquement par rapport à la ligne (p-1)/4. En particulier, si Pp ne* est une parure primitive la parure Pp,(p_1)/2-nc* est également une parure primitive symétrique de la précédente. Si la base du descripteur PDpnc*N,k de rang k est sur la première ligne n=1 de l'écrin alors, la base du descripteur PDp(p_1)/2-ne*N,k de même rang k est disposée symétriquement ; elle est sur la ligne n=(p-3)/2. Par conséquent, si la parure Pp,ne*N est la parure primitive générique nord de rang k alors, la parure conjuguée de celle-ci est la parure primitive générique sud de rang k. De même, si la base du descripteur PDP,,,C*s,k de rang k est sur la dernière ligne n=(pû1)/2 du demi écrin nord alors, la base du descripteur PDP (P-I)/2-ne*S.k de même rang k est disposée symétriquement ; elle est sur la première ligne n=1. Par conséquent, si la parure PP,nc*s est la parure primitive générique sud de rang k alors, la parure conjuguée de celle-ci est la parure primitive générique nord de rang k. Les indices ne*Nk et ne*sk des deux parures génériques de rang k sont donc liés par la relation : ne*Sk+ne*Nk = (pû1)/2. Scholie (début) (1) Si on connaît la parure primitive générique nord, on connaît la parure primitive générique sud et réciproquement. (2) La détermination des indices des deux parures primitives génériques peut donc être limitée à l'une des deux. (3) Cette remarque est mise à profit dans le paragraphe consacré à la détermination des indices des deux parures primitives génériques. Scholie (fin) � Régularités relatives aux bases des descripteurs PDp,,,,k Les bases ouest ainsi que les base est des descripteurs PDP,nc,k d'une parure PP,nc sont corrélées à l'indice ne de la parure considérée. • Dans le cas où l'indice ne d'une parure est impair, toutes les bases des descripteurs PDP,ne,k de la parure considérée ont un indice impair. Lorsque l'indice impair ne d'une parure PP ne correspond à une ligne appariée, toutes les bases des descripteurs PDP.ne,k de la parure considérées sont sur des lignes impaires appariées. Lorsque l'indice impair ne d'une parure correspond à une ligne non appariée, toutes les bases des descripteurs PDP,ne,k de cette parure sont sur des lignes impaires non appariées. • Dans le cas où l'indice ne d'une parure PL, est pair, toutes les bases des descripteurs PDP,ne,k de cette parure ont un indice pair. � Notion de plage • Les lignes impaires non appariées et les lignes paires connexes aux lignes impaires non appariées forment des plages dites autorisées. Lorsque l'indice n~ (pair ou impair) d'une parure est situé dans une plage autorisée toutes les bases des descripteurs PDP,nc,k relatifs à cette parure sont situées dans des plages autorisées. • Les plages situées en dehors des plages autorisées forment des plages dites saturées; les plages saturées sont composées d'une alternance de lignes impaires et de lignes paires situées entre les lignes impaires de la plage saturée considérée. Lorsque l'indice n, (pair ou impair) d'une parure est situé dans une plage saturée toutes les bases des descripteurs PDP nc,k relatifs à cette parure sont situées dans des plages saturées. Scholie (début) (1) Les parures des plages saturées comportent au plus deux perles (une perle blanche et une perle noire) par ligne ; les lignes des plages saturées sont saturées lorsqu'elles contiennent deux perles ; la qualification de plages saturées trouve son origine dans cette situation. (2) Les parures des plages autorisées comportent plus de deux perles par lignes ; la qualification de plages autorisées trouve son origine dans cette situation. (3) Un écrin compact comporte des plages autorisées, d'amplitude trois unités, axées sur les lignes (pù1)/4 et 3(pùl)/4 ; les autres plages d'un écrin compact sont des plages saturées. Dans le cas d'un écrin non compact, la succession des plages autorisées et des plages saturées fragmente l'écrin en bandes présentant des caractéristiques communes. Scholie (fin) � Indices des parures primitives génériques On a vu que les relations d'appariement entre les lignes et les colonnes permettent de déterminer les racines primitives et leurs rangs. Or, il est possible de déduire des valeurs des racines primitives et de leurs rang les indices ne*"k et ne*Sk et des parures primitives génériques nord et sud de rang k ; en effet, par définition une parure primitive générique de rang k est une parure primitive dont le descripteur PDp,nc*,k de rang k a sa base sur la ligne 1 ou sur la ligne (pû3)/2 de l'écrin. Soit la parure primitive générique d'indice ne*, la perle blanche de la colonne k=l située sur la ligne nc* masque le résidu r ; la perle noire conjuguée de la perle blanche masque sur la ligne (pû1)ûne* dans la colonne k=l le résidu r'. Aux résidus r et r' correspondent les racines primitives gp,k=r et gp,k.=r' des colonnes k et k'. Autrement dit, connaissant l'indice n,* d'une parure primitive générique on est en mesure de déterminer les valeurs des primitives gp,k et gp,k, et corrélativement les indices des colonnes k et k' correspondantes. On a vu ci-dessus que cet enchaînement est mis à profit pour déterminer la largeur des bases. Inversement, soit une base ouest générique de rang k ; la perle Ouest correspondant à la case Kk, est soit une perle blanche soit une perle noire ; la perle de la case Kk,, masque le résidu r. On cherche dans la colonne k=1 le résidu r ; il désigne la ligne ne*N. Si ne*N est inférieur à (pû1)/2la perle de la case Kk_1,neN est une perle blanche ; en ce cas, la perle de la case conjuguée Kk=1.(p_1 ne*N est une perle noire masquant le résidu r'. En revanche si ne*Nk est supérieur à (pû1)/2 la perle de la case Kk=1,nC*N est une perle noire; en ce cas, la perle de la case de la case conjuguée Kk_1,(1,_1)_nC*N est une perle blanche masquant le résidu r'. On est ainsi en mesure de déterminer pour chaque base ouest générique de rang k l'indice ne*Nk de la parure primitive générique de rang k. Puisque ne*Nk et n:sk sont liés par la relation n:Nk+n:sk=(pû1 )/2, on sait déduire de la valeur de nc*Nk celle de nc*sk � Emboîtement des descripteurs Le processus d'emboîtement des descripteurs PDp,fC*,k est ci-après décrit dans le cas où la parure d'indice n: impair est une parure primitive ; ce processus d'emboîtement est généralisable, mutatis mutandis, aux parures d'indices pairs ainsi qu'aux parures d'indices impairs non appariées. Les expressions générales des coordonnées des sommets Sa.k, Sb.k, Sc,k et Sd,k sont les suivantes Sak :k,bpnc*k Sb k : k+ lp ne*,k, bp,nc*,k Sc k : 4(pù1)+1ùk, (pù1)12ù bp,nc*,k Sd k : 4(pù1)+l ùk ù lp nc* k, (p-1)/2- bp nc* k Au fur et à mesure que k croît par pas de une unité, le sommet Sk,a le plus à l'ouest du descripteur PDp,nc,k se décale vers l'est par pas de une unité et le sommet Sk,c le plus à l'est se décale vers l'ouest également par pas de une unité ; c'est en ce sens que l'on peut parler d'un processus d'emboîtement des descripteurs. On connaît les lois de variation de lp,nc*,k en fonction de k ; elles sont indépendantes de la valeur de l'indice nc* de la parure considérée ; la largeur lp,nc*,k, des descripteurs PDp,nc*,k ne dépend que du rang k. Il reste à préciser les lois de variations de l'indice bp,nc*,k ; on sait déjà, puisque par hypothèse nc* est impair, que les indices bp,nc*,k des bases sont impairs. On sait en outre que si k=1, b p,nc*,1 = ne* Scholie (début) (1) La base du descripteur PDp,nc*., de rang k=1 de la parure Pp,n*c a pour indice bp,nc*,, = ne*. On doit s'attendre à ce que cette corrélation remarquable entre le rang k du descripteur PDp,nc*,k et la valeur de l'indice bp,nc*,k de sa base, mise en évidence dans le cas où k=1, trouve également un écho lorsque k prend d'autres valeurs. Scholie (fin) � Variations incrémentales des indices des bases des descripteurs L'objectif est d'expliciter les règles de variations des indices bI,,nc*,k des bases des descripteurs PDp,nc*,k de même rang k ; on étudie les variations des indices bp,nc*,k des bases de même rang k en fonction de l'indice nc* des parures primitives Pp,nc*• Une approche heuristique suggère que les indices bp,nc*,k des bases de même rang k varient de manière incrémentale à pas S*p,k constant ; l'astérisque � * � spécifie 30 qu'il s'agit des incréments relatifs descripteurs primitifs PDp,nc*,k. Scholie (début) (1) L'expression � à pas constant � ne livre qu'un premier aperçu des modalités selon lesquelles varient les indices bP,nc*,k des bases de même rang k . En fait, il serait plus approprié de mentionner que les variations sont à pas modulaire constant par plage. (2) L'approche heuristique permet d'entrevoir que le modulo des variations est égal à (p-1)/2. (3) Les développements du chapitre III ci-après visent à approfondir l'expression mathématique des variations incrémentales modulaires des indices bP,,,C*,k des bases. Scholie (fin) Chapitre III. Approfondissement dans le cas où (pû1)/2 est pair. A ce stade de l'exposé, il convient de préciser les lois de variations des incréments 8*p,k de même rang k, en fonction des indices nc* des parures primitives PP ne*. A cet effet, on est conduit à approfondir l'étude des régularités. � Principe du calcul des incréments S*l* L'idée générale qui gouverne le calcul des incréments S*p,k de même rang k est la suivante. On a vu au cours des précédents paragraphes que l'on sait déterminer les indices ne*Nk et ne*sk des parures primitives génériques nord et sud de rang k. Par conséquent, si on est en mesure de concevoir une progression par pas d'amplitude S*p,k permettant de passer de la parure primitive générique nord à la parure primitive générique sud et si on sait décompter le nombre des pas que comporte cette progression alors, on sait établir une relation entre l'incrémen tS*P k de rang k et les valeurs connues des indices ne*r et nc*sk Scholie (début) (1) Il convient de nuancer ce programme ; en effet, ce n'est que dans le cas des écrins EP compacts que l'on peut expliciter de manière simple les variations à pas modulaire constant. (2) Dans le cas général, il est encore possible d'identifier des variations à pas modulaire constant pour les différentes plages saturées fragmentées de l'écrin. (3) Dans la suite de l'exposé, afin d'en simplifier la présentation on suppose que l'écrin EP considéré est un écrin compact. Les résultats exposés sont généralisables mutatis mutandis à d'autres structures d'écrin. Scholie (fin) � Pivotement des descripteurs En gardant en tête cette idée générale, on considère un processus de variation de l'indice nc des parures PP nc* consistant à augmenter celui-ci par pas de deux unités ; l'indice nc croît de 1 à (pû3)/2. Le processus comprend au plus (pû5)/4 étapes ; au terme de (p-5)/4 itérations du processus, on trouve la dernière parure PP,nc*=(p-3)12 ; les positions occupées par les descripteurs de la parure PP,nc*=(p-3),2 sont symétriques de celles qui sont occupées par les descripteurs de la parure PPnc*=1• Au cours de ce processus, les descripteurs PDP,nc*,k des demis écrins nord et sud des parures PP,nc* pivotent autour des centres de symétrie nord ON et sud OS en se déformant. Scholie (début) (1) La déformation géométrique des descripteurs PDP,nc*,k de la parure PP nc* peut être décrite en réduisant l'exposé à la seule évolution de la base Ouest de PDP,nc*,k ; en effet, la symétrie de centre ON permet de construire intégralement le descripteur PDP,nc,k à partir de la base ouest. Scholie (fin) Pour certaines valeurs de k, notamment pour les plus petites valeurs de k ainsi que pour les plus grandes valeurs de k, il apparaît possible de donner une description géométrique des évolutions de la base. En effet, en combinant une translation selon l'axe nord-sud d'amplitude S*P k avec une symétrie miroir par rapport à une ligne Est-Ouest on est en mesure de restituer simplement l'évolution de la base. Scholie (début) (1) Pour les valeurs de k intermédiaires l'enchaînement des opérations géométriques consistant à étirer puis à plier les descripteurs ne restitue pas fidèlement les évolutions des bases. (2) Toutefois, on montre ci-après que les expressions mathématiques que l'on obtient en extrapolant les opérations géométriques s'avèrent appropriées pour décrire les évolutions des bases, y compris pour les valeurs intermédiaires de k. (3) Les opérations géométriques considérées s'apparentent à l'enchaînement d'un processus d'étirement suivi d'un de pliage. Elles renvoient implicitement au fer à cheval de Smale. Dans la suite de l'exposé, on désigne sous le nom de transformations de Smale les processus géométriques, arithmétiques ou algébriques qui conjuguent des étirements et des pliages. Scholie (fin) � Approche heuristique de l'expression mathématique des transformations de Smale L'objectif est de trouver une expression mathématique exprimant l'enchaînement des opérations de translation et de symétrie miroir. A ce stade de l'exposé, la quête est essentiellement heuristique. Il s'avère que les formes mathématiques révélées par cette quête sont suceptibles d'être étendues de manière plus générale. • Dans le cas où (bp=53,nc_l,k+i S*p=53,k) (Pp=53 1)/2, on obtient l'expression : _ o * bp=53,nc*=2i+l,k = (+ Ek,i=) (bp=53,nc=l,k+i b p=53 k) En fait, l'expression bp=s3,nc=2i+l,k = (+ Ek,i=o)�bp=53,nc=1,k+i b*p=53,k) regroupe deux relations distinctes, en utilisant le séparateur °. L'une (bp=53,nc_l,k+i b*p_53,k) renvoie l'indice bp=53,nc*=2i+1,k de la ligne de la base Ouest du descripteur PDp=53,nc*,k de rang k. L'autre (+Ek i=o) spécifie la couleur de la perle Ouest de la base d'indice bp=53,nc*=2i+l,k• Dans cette dernière relation, le symbole Ek,i=o est égal à +1 si la perle de la base ouest du descripteur de rang k de la parure Pp=53,nc*=2i+1=1 d'indice ne*=1 est de couleur blanche ; le symbole Ek,i=() est égal à -1 si la perle de la base ouest du descripteur de rang k de la parure Pp=53,nc*=2i+1=1 d'indice ne*=l est de couleur noire. • De même, dans le cas où (pp=53 1) > (bp=53,nc*=1,k+i b*p=53,k) > (pp=53 1)/2, on obtient l'expression : bp=53,nc*=2i+l,k = (ùEk,i=o) [(Pp=53 1)ù(bp=53,nc*ù1,k+i b p=53,k)] Les deux expressions obtenues permettant de calculer l'indice de la base de PDp,nc=2i+l,k sont généralisables aux autres valeurs de p et synthétisables en une expression unique : bp,nc*=2i+l,k ù (Ek,i=0 wk,i)°[wki(bpnc*=1 k+i b*pk) mod(pù1)12J Dans cette expression : wk i=+ 1, si (pù1)/2>bp ne*=1 k+l b*p k et wk Fù1 si (pù1)>bp ne*=1 k+i S*p k>(pù l )/2 ; Scholie (début) (1) Le terme [wk,i(bp,ne*=l,k+i V*p,k) mod(pùl)12] figurant dans l'expression de bp,ne*=2i+l,k concerne la transformation de Smale ; il comporte : • une translation d'amplitude Ô*p,k ayant pour origine bp ne=1,k, cette translation est traduite par terme bp,ne*=1,k+i S*p k ; il comporte en outre, le cas échéant, • une symétrie miroir par rapport à l'axe SH correspondant au pliage modulaire modulo (pù1)/2. (2) Le terme Ek i-0 wk i explicite, en cas de pliage, l'inversion de couleur des perles de la base. Scholie (fin) � Extension de l'expression arithmétique de la transformation de Smale L'expression de bp ne*=2i+1,k _ bp,nc*=2i+ ,k ù (Ek i=0 wk i) o I wk i(bp ne*=1 k+l S*p k) mod(pù1)/2] n'est applicable que pour autant que bp,ne*=l,k+i Ô*p,k est inférieur à (pù1) ; en effet, pour les valeurs de k et de i telles que bp,ne*_1,k+i S*p,k pù1 la base translatée sort du champ du demi écrin sud. Pour étendre l'expression arithmétique de la transformation de Smale on procède à autant de symétries miroir que nécessaire pour replier la base dans le demi écrin nord. D'une manière générale, soit m entier tel que : m (pù1)/2 il y a lieu de procéder à m pliages ; l'expression de wk i devient wk i=(ù1)^m. Scholie (début) (1) L'expression de bp,ne*=2i+l,k : bp,nc*=2i+l,k ù (�k i=0 Wk i)0 [ Wk,i(bp ne=l k+l b*p k) mod(pù1)/2] complétée par la relation wki=(-1)^m, constitue un progrès dans la mesure où elle élargit le champ d'application de la formule permettant de calculer l'indice des bases ouest ; dans cette expression m est défini par les deux inégalités : m (pù1)/2 Scholie (fin) � Détermination de l'incrément S#p* Précédemment, on a vu comment déterminer l'indice ne*Nk de la parure primitive générique nord de rang k ainsi que l'indice ne*sk de la parure primitive générique sud de rang k ; les bases des descripteurs de rang k de ces parures sont respectivement situées sur la ligne 1 ou sur la ligne (p-3)/2 Corrélativement, on sait calculer la valeur des paramètres i*Nk et i*Sk tels que ne*Nk=2i*Nk+1 et ne*Nk=2i*sk+l. Afin d'alléger l'écriture des relations, on sous-entend dans la suite de l'exposé que les paramètres iN=i*Nk et is=.i*sk sont ceux des parures primitives génériques nord et sud de rang k. On rappelle que dans le cas des écrins étudiés les indices iN et is sont impairs. Par ailleurs, puisque ne*sk+nc*Nk = (p-1)/2, on en déduit que iN + is = (pû5)/4. On a vu que l'expression algébrique de la transformation de Smale bp,nc*=2i+1,k (Ek,i=O wk,i)0[wk,i Ibpn*=1 k+i S*p,k mod(pû1)/21 permet de calculer la base bp,fC*=2i+1,k du descripteur PDp,fC*,k de rang k d'une parure primitive d'indice ne*=2i+1. Si, à ce point de la discussion, on fait abstraction de la couleur des perles on dispose donc de l'équation générale suivante entre les inconnues bp,nc*=1,k et b*p k que l'on cherche à déterminer : bp,nc*=2i+l,k = Wk,i Ibp,nc*=1,k+i 8*p,k I mod(pù1)12 Or, pour i= iN, bp,nc*=21N+l,k = 1 ; d'où la première équation : 1 =ù {ok,iN Ibp,nc*=1,k+1N 8*p,k I mod(pù1)/2} De même, pour i=is, bp,nc*=2is+l,k = (p-3)/2 ; d'où la deuxième équation : (p-3)/2 = {UJk,is Ibp,nc*=1,k+iS 8*p,k I mod(pù1)/2} On dispose donc d'un système de deux équations linéaires modulaires. En formant la différence membre à membre de ces deux équations, on obtient : (p-3)/2ù1 ='Wk,iS Ibp,nc*=1,k+1S 8*p,k Iùwk,iN Ibp,nc*=1,k+1N 8*p,k II mod(pù1)/2 Soit encore : (p-5)/2 = îwk,is Ibp,nc*=1,k+ls 8*p,k Iùwk,iN Ibp,nc*=1,k+1N 8*p,k Il mod(pù1)/2 L'approche heuristique permet de constater que : • d'une part, Wk,i=iN = Wk,i=iS • d'autre part, les termes bp,nc*=1,k+1N 8*p k et bp,nc*=1,k+is 8*p k sont de même signe. D'où: (p-5)/2 = 0k,iN I(iN is) 8*p,k I mod(pù1)/2 Scholie (début) (1) Les deux relations permettant d'obtenir la relation lapidaire ci-dessus trouvent leur origine dans le fait que les parures d'indices ne*Nk=21N+1 et ne*sk=2is+1 sont des parures conjuguées génériques. (2) Le terme bp,nc*=l,k disparaît ; en revanche les valeurs particulières de iN et is subsistent. (3) L'équation modulaire (p-5)/2 = wk,iN I(1Nùls) 8*p,kl mod(pù1)12 permet de déterminer 8p,k. Scholie (fin) � Résolution de l'équation modulaire de 8'p,k Puisque Wk,iN=�l, les solutions de l'équation : wk,iN I(iN is) 8*p k I mod(pù1)/2 = (p-5)/2 sont solutions de l'une ou l'autre des deux équations modulaires : (N 1S) 8*p k mod(pù1)/2 (p-5)/2 On est conduit à résoudre l'une des deux équations diophantines linéaires correspondantes ; on choisit de résoudre l'équation diophantine : (iN-is) S*p,k +[(pû1)/2]gp,k = +(p-5)/2 qp k étant un entier nul, positif ou négatif. Les solutions de l'équation diophantine : (iN-is) S*p k +[(Pû1)/2 ]qp k = û(p-5)/2 s'en déduisent. L'approche heuristique permet de constater que les incréments )b*pk) se présentent sous la forme des produits par 2 des nombres impairs compris entre 1 et (pû1)/2 ; par conséquent, il convient de sélectionner, parmi les valeurs paires de b*p,k solutions de l'équation diophantine, celles qui sont comprises entre (pû1 )/2 et (pûl)/2 qui se présentent sous la forme du produit par deux d'un nombre impair. La méthode permettant de déterminer les solutions d'une équation diophantine linéaire est connue ; il n'y a pas lieu de la rappeler ici. Soit une solution Particulière b*pk_0 et gpk_0 de l'équation diophantine (iNûis) 8*p,k +[(pù1)/2]qp k = +pgcd[(pû1)/2,(1N û is)J On sait que l'expression générale des valeurs de S*pk et qp,k satisfaisant l'équation diophantine considérée est alors la suivante : S*p k t = S*p k_0 + [(pû1)/21t /pgcd[(pû1)/2,(iN is)] gp,k,t = qp,kû0 û (iN is)t/pgcd[(pû1)/2,(iN is)] Dans ces expressions, le paramètre t est un entier nul, positif ou négatif permettant de décrire l'infinité des solutions ; la notation pgcd[(pûl)/2,(iN is)] désigne le plus grand commun diviseur de (pû1)/2 et 0N -4s) ; l'approche heuristique met en évidence qu'un pgcd de valeur égale à 2 est un cas probable ; dans ce cas, l'expression de la solution générale est alors la suivante : b*p,k,t = ô *p k_0+(pû1) t/4 gp,k,t = qp,kù0 ù (iNùis) t/2 On ne retient que les valeurs paires de b*p,k,t comprises entre û(pû1)/2 et +(pû1)/2 se présentant sous la forme du produit par deux d'un nombre impair. Parmi celles-ci figure celle qui décrit de manière univoque l'évolution des descripteurs. � Changement d'origine On obtient une autre expression de l'indice bp,nc=2i+l,k de la base ouest de rang k de la parure primitive Pp,nc*=2i+1 en faisant apparaître l'indice iN de la parure primitive générique nord de rang k : bp ne*=2i+l,k (Ek,i=iN wk,i)0Iwk,i 11+ (i N) b*p k I mod(pù1)/2] avec : m (pù1)/2 L'écrin E53 est un écrin compacte. (C) On sait que la plus petite racine primitive g53,m de l'écrin E53 est égale à 2. On sait calculer, de manière en soi connue, pour tout ou partie des valeurs de n comprises entre 1 et pû2, les résidus g53,R,' n modp. Scholie (début) (1) Même si p est grand lorsque la première racine primitive gp,m est petite, ce qui est en particulier le cas ici puisque g53,.=2, les ressources informatiques nécessaires pour calculer les pû2 résidus sont compatibles avec les calculateurs numériques existant. En fait, il n'est pas toujours nécessaire de calculer pû2 résidus ; ce point est précisé dans la suite de l'exposé. (2) Si p est grand, la capacité mémoire dont il faut disposer pour stocker les pû2 résidus de gp,mAn modp est gigantesque. En fait, il n'est pas nécessaire de conserver en mémoire tous les résidus calculés ; ce point est également précisé dans la suite de l'exposé. (3) Dans le cas de l'exemple numérique considéré le calcul des 51 résidus ne soulève bien entendu aucune difficulté ; la petite valeur numérique p=53 retenue répond au seul objectif de présenter les mécanismes logiques. Scholie (fin) (C) L'objectif est de déterminer le rang k de la racine primitive gp,;=8 servant de base au logarithme discret. En fait, pour les raisons exposées dans le corps du texte, pour les valeurs de n codées par la séquence : 101010101010/0/010101010101/0/101010101010/0/010101010101 tous les résidus gp,n,^n modp obtenus correspondent à des racines primitives. Pour prendre en compte les observations ci-dessus formulées, on classe au fur et à mesure de leurs apparitions les valeurs des résidus gp.n,^n modp correspondant à une racine primitive de p ; plus précisèment l'algorithme permettant d'effectuer ce classement est le suivant : (Cl) On initie le calcul en introduisant la valeur 0 dans un compteur Cpt et en introduisant la valeur 0 dans une zone mémoire Ngi. (C2) On calcule les résidus gp n,^n modp pour les seules valeurs de n codées par la séquence : 101010101010/0/010101010101/0/101010101010/0/010101010101 Si le résidu rn calculé est plus petit ou égal à gp,; on incrémente le compteur Cpt de une unité. De plus, si le résidu rn calculé est égal à go on mémorise dans la zone mémoire Ngi la valeur de n=n; correspondante en effaçant la précédente valeur enregistrée. Enfin, si la valeur de n; est inférieure à (p-l)/2, on mémorise dans une zone mémoire Si que le signe devant être affectée à n; est le signe � + � ; ce qui indique que que la perle du collier Cm, de la parure Pp ni d'indice ni est une perle blanche ; en revanche, si la valeur de ni est supérieure à (p-l)/2, on mémorise dans la zone mémoire Si que le signe devant être affectée à n, est le signe � û � ; ce qui indique que la perle du collier Cp,n; de la parure Pp ni est une perle noire. Puisque, par hypothèse, gp,;≠ gp,n, au terme de l'étape initiale Ngi=O. Scholie (début) (1) Par construction le résidu r~ est une racine primitive différente des valeurs calculées lors des étapes antérieures. (2) Au terme du processus, pour n=p-2, la valeur du compteur Cpt est égale au rang k de la racine primitive gp;. (3) Ainsi, dans le cas considéré les étapes sont les suivantes : (a) : ligne n=1 Cpt =1 ; Ngi =0 (b) : ligne n=3 Cpt=2; Ngi =ni=3 on obtient la racine primitive gp,i=8 pour n=ni=+3 (c) : lignes n=5, n=7, n=9, n=11, n=15 aucun changement Cpt=2 ; Ngi =3 (d) : ligne n=15 Cpt=3; Ngi =3 (e) : lignes n=17 à n=45 aucun changement Cpt=3 ; Ngi =3 (f) : ligne n=47, M=5 ; Cpt=4 ; Ngi =3 (g) : ligne n=49 à n=51 ; aucun changement Cpt=4 ; Ngi =3 In fine, on obtient les résultats suivants : • la valeur du compteur Cpt=4 est égale au rang k de la racine primitive gp,;=8 ; • la mémoire Ngi renvoie la ligne n;=3 correspondant à la racine primitive gp,1=8 ; • la mémoire Si renvoie le signe � + �. (4) L'opération consistant à mémoriser la valeur du nouveau résidu calculé en effaçant la précedente valeur n'est pas indispensable ; elle n'est pas prévue ; toutefois, cette opération peut présenter un intérêt notamment pour certaines valeurs de n aux fins de vérifications. (C3) L'objectif est de déterminer l'indice x de ligne de la case Kk=I X de la première colonne k=1 contenant le résidu a=35. On compare, au fur et à mesure de leurs apparitions, les valeurs des résidus gp,^n modp à la valeur a=35 dont on souhaite déterminer le logarithme discret modulo p=53 en base gp,;=8 ; si la valeur ra du résidu est égale à a=35, on mémorise dans une zone mémoire Na la valeur de n=na correspondante en effaçant, le cas échéant, la valeur précédente figurant dans la mémoire Na. Si la valeur de na est inférieure à (pû1)/2, on mémorise dans une zone mémoire Sa que le signe devant être affectée à na est le signe � + � ; ce qui indique que la perle du collier CI),na de la parure Pp na est une perle blanche ; inversement, si la valeur de na est supérieure à (p-l)/2=26, on mémorise dans la zone mémoire Sa que le signe devant être affectée à na est le signe � û � ; ce qui indique que la perle du collier Cp na de la parure Pp (p-1)ùna est une perle noire. Scholie (début) (1) On suppose que dans le cas particulier considéré la case dans laquelle apparaît le résidu 35 est une case d'une ligne appariée. Dans ce cas, cette phase de l'algorithme peut être traitée simultanément à la phase ci-dessus consacrée à la détermination du rang k de la racine primitive go. En fait cette hypothèse n'a pas un caractère indispensable ; en effet, en augmentant par pas de une unité la valeur de n on trouve nécessairement la valeur na pour laquelle gp,,n^n modp=a ; l'hypothèse considérée est ici retenue afin de mettre plus rapidement en évidence le mécanisme selon lequel fonctionne l'algorithme. (2) Ainsi, dans l'exemple considéré lors des étapes C concernant les lignes n=5, n=7, n=9, n=11, n=15, au passage de la ligne n=9 on trouve le résidu 35 attendu ; la valeur na=9 est stockée dans la mémoire Na ; puisque 9 est inférieure à 26, le signe � + � est mémorisé dans la mémoire Sa. (3) fine, on obtient les résultats suivants : • la mémoire Na renvoie la ligne na=9 correspondant au résidu a=35 ; • la mémoire Sa renvoie le signe � + � ; par ailleurs, comme précédemment, on obtient : • la valeur du compteur Cpt=4 est égale au rang k de la racine primitive go=8 ; • la mémoire Ngi renvoie la ligne n;=3 correspondant à la racine primitive gp;=8. Scholie (fin) � Deuxièmes phases de l'algorithme. Les deuxièmes phases de l'algorithme sont consacrées au calcul de l'incrément b*53.k_4 de rang k=4 en appliquant les règles explicitées dans le cas d'un écrin compacte. • Il convient en premier lieu de déterminer les indices iN et is des parures primitives génériques de rang 4. A cet effet, on considère la parure P53,n1 formée par la combinaison du collier C53,n; et du collier conjugué C53,52_n; ; autrement dit, on considère la parure P5333 ; on a précédemment mémorisé dans la mémoire Si que le signe affectant l'indice n;=3 est le signe � + � ; la perle associée à la parure P533 est une perle blanche. On vient de déterminer que la racine primitive gp,;=8 de rang 4 est appariée avec la ligne n;=3 ; autrement dit, on vient de déterminer que le descripteur PD53,3,4 de la parure P533 a sa base sur la première ligne de l'écrin E53. Par conséquent, l'indice iN de la base générique nord de rang 4 est tel que iN=1, [en effet, puisque 2iN+1=3, iN =1]. Par ailleurs, puisque iN+is=(pû5)/2=12, on en déduit que l'indice is de la base générique sud de rang 4 est tel que is=11 ; le signe spécifiant la couleur des perles associées est le signe � + �, c'est une perle blanche. On mémorise dans des zones mémoires appropriées iN=+l et is=+l 1 • Il convient en second lieu, pour les valeurs algébriques de iN=+l et de is=+11 précédemment calculées, de résoudre les deux équations diophantines : (1N is) 8*p,k +[(p-l)/21gp,k = �(p-5)/2 qp k étant un entier nul, positif ou négatif. On ne retient que les valeurs paires de S*p,k comprises entre û(pû1)/2 et +(pû1)/2 se présentant sous la forme du produit par deux d'un nombre impair. En l'espèce, les deux équations diophantines linéaires sont les suivantes : _ l0Ô*p=53,k=4 + 26gk=4 = �24 En appliquant des règles de résolution en soi connues, il apparaît qu'il existe deux valeurs de b*p_53,k=4 comprises entre -26 et +26 se présentant sous la forme du produit par 2 d'un nombre impair ; on obtient b*p=53,k=4- �18 � Troisièmes phases de l'algorithme. Les troisièmes phases de l'algorithme sont consacrées au calcul de l'indice bp=53,nc*=9,k=4 de la base ouest du descripteur PDp_53,nc*=9,k=4 de rang k=4 de la parure Pp=53,ne=9 de l'écrin Ep=5. Par construction de la procédure algorithmique, on sait que les perles blanches de la parure Pp=53,n,=2;+1=9 masquent le résidu a=35. Dans les relations mathématiques mises en oeuvre on matérialise la correspondance entre l'indice i et le résidu a en affectant l'indice � a � à la lettre � i � ; on écrit ia. On a vu dans le corps de l'exposé que la combinaison des trois relations : bp nc=2ia+l,k (Ek,i=iN Wk,ia)° [0)k,ia 11+ (ia 4N) 8*p,k I mod(p-1)/21 m (pù1)/2 Avec cette valeur de (04,4 l'expression donnant b53,9,4 devient : b53,9,4 = [(+1) (+1)]°[ (+1) 55 mod26] D'où, b53,9,4-+3 On obtient le résultat selon lequel le résidu figurant dans la colonne k=4 de l'écrin E53 sur la ligne b53,9,4 d'indice 3 est masqué par une perle blanche ; puisque ce résidu est masqué par une perle blanche sa valeur est égal à 35 ; par conséquent, 8A3 mod53= 35 ; le logarithme discret de 35 en base 8 est égal à 3. Scholie (début) (1) dans le cas où le calcul révèle l'existence d'une perle noire au lieu d'une perle blanche, cette perle noire masque dans la case située à l'intersection de la colonne 4 et de la ligne 3 le résidu conjugué de 35 ; on en déduit que le résidu de la colonne 4 de valeur égal à 35 est situé à l'intersection de la ligne conjuguée de la ligne 3, c'est à dire à l'intersection de la ligne x=52ù3 et de la colonne 4 dans une telle hypothèse le logarithme discret de 35 serait égal à 49. Scholie (fin) • Dans le cas où b*53,k=4= -18, les trois relations deviennent : b53,9,4 = (+1) w44[w44I1ù (4ù1) 18 1 mod26 26m Avec cette valeur de (044 l'expression donnant b53,9,4 devient : bP,fC=z;+I,k = [(+l) (+l)]°[(+1) 53 mod26] D'où, b53,9,4 =+1 ; l'hypothèse selon laquelle S*53,k=4= -18 conduit à une incohérence, la base b53,9,4 ne peut pas être une base générique de rang k=4 ; en effet, on a vu que la base générique de rang k=4 est telle que b533,4=1 L'hypothèse S*53,k=4= -18 doit être écartée. � Récapitulatif L'enchaînement des trois phases algorithmiques a permis de calculer le logarithme discret a=35 modulo p=53 en base gP,;=8 ; il est égal à 3. La procédure algorithmique mise en oeuvre pour calculer le logarithme discret est généralisable mutatis mutandis pour des valeurs de p comportant plusieurs milliers de chiffres. Les deux processus susceptibles cle consommer des ressources informatiques élevées sont : • ceux concernant le calcul sélectif des résidus gp,,,,^n modp, notamment 30 dans le cas où gpm a une valeur d'importance moyenne par rapport à celle de go, • ceux relatifs à la résolution de l'équation diophantine linéaire permettant de calculer l'incrément S*P k. Les règles gouvernant les régularités facilitent l'établissement des séquences codant les valeurs de n correspondant aux racines primitives de p. Dessins Les figures 1 et 2 illustrent les notions ci-dessus exposées dans le cas particulier (p=53) faisant l'objet de chapitre IV ; • la figure 1 représente plus particulièrement les parallélogrammes descripteurs de la parure Pp=53,ne=3 dont l'une des perles blanches masque la racine primitive gp,k=8 servant de base au calcul du logarithme discret; • la figure 2 représente plus particulièrement les parallélogrammes descripteurs de la parure PP=53,ne=9 dont l'une des perles blanches masque le résidu r=35 dont on cherche à calculer le logarithme discret en base gp,k=B ; Nomenclature des éléments représentés sur la figure 1. (1) : Ecrin EP=53 ; (2) : Bord sud de l'écrin EP=53 ; (3) : Bord est de l'écrin EP=53 ; (4) : Bord nord de l'écrin EP_53 ; (5) : Bord ouest de l'écrin Ep=53 ; (6) : Lignes de l'écrin EP=53 ; notamment lignes n=8, n=11 et n=20 ; (7) : Colonnes de l'écrin EP_53 ; notamment colonnes k=18, k=19 et k=22 ; (8) : Lignes appariées à des colonnes de l'écrin EP=53 ; les lignes appariées sont désignées par des rectangles ; les lignes appariées sont distribuées selon la séquence 101010101010/0/010101010101/0/101010101010/0/010101010101 précédemment explicitée ; en appliquant la procédure ci-dessus décrite on détermine que la ligne n=3 est appariée à la colonne k=4 ; on peut établir de la même façon que les lignes n=25, n=31 et n=25 sont respectivement appariées aux colonnes k=12, k=10 et k=7 ; (9) : Axe de symétrie Sv ; (10) : Axe de symétrie SH ; (Il) : Axe de symétrie secondaire SH/N ; (12) : Axe de symétrie secondaire SwS ; (13) : Centre de symétie O ; (14) : Centre de symétrie ON du demi écrin nord (15) : Centre de symétrie Os du demi écrin sud (16) : Colone k=1 de la table des résidus Tp=53 ; la colone k=1 contient les résidus gp=53,k=1An mod 53 ; gp=53,k=1=2 , (17) : Perle blanche du collier Cp=53,nc=3 masquant le résidu r=8 ; (18) : Perle noire du collier Cp=53,nc=a9 masquant le résidu r=20 ; (19) : Bracelet du quart nord ouest de la parure Pp=53,nc=3 ; (20) : Bracelet du quart nord est de la parure Pp=53,nc-3 ; (23) : Perle blanche à l'intersection de la colonne k=1 et n=3 masquant le résidu r=8 ; [sur la figure 1, le résidu r=8 apparaît en transparence] ; (24) : Rang k=4 de la primitive gp,k=8 servant de base au calcul du logarithme discret ; la valeur k=4 du rang est obtenue en appliquant la procédure décrite ; (25) : Parallèlogramme descripteur Pp=53,nc=3,k=1 de la parure Pp=53,ne=3 ; la perle la plus à l'ouest est une perle blanche ; (26) : Parallèlogramme descripteur Pp=53,nc=3,k=2 de la parure Pp=53,nc=3 ; la perle la plus à l'ouest est une perle noire; (27) : Parallèlogramme descripteur Pp=53,nc=3,k=3 de la parure Pp=53,nc=3 ; la perle la plus à l'ouest est une perle noire; (28) : Parallèlogramme descripteur Pp=53,nc=3,k=4 de la parure Pp=53,nc=3 ; la perle la plus à l'ouest est une perle blanche; (29) : Parallèlogramme descripteur Pp=53,nc=3,k=5 de la parure Pp=53,nc=3 ; la perle la plus à l'ouest est une perle noire ; (30) : Parallèlogramme descripteur Pp=53,nc=3,k=6 de la parure Pp=53,nc=3 ; la perle la plus à l'ouest est une perle blanche; Nomenclature des éléments représentés sur la figure 2 Les éléments identiques portent les mêmes références. (43) : Perle blanche à l'intersection de la colonne k=1 et n=9 masquant le résidu r=35 ; [sur la figure 2, le résidu r=35 apparaît en transparence] ; (44) : Perle noire masquant le résidu r=50 ; [sur la figure 2, le résidu r=50 apparaît en transparence] ; (45) : Parallèlogramme descripteur Pp=53,nc=9,k=1 de la parure Pp=53,äc_9 ; la perle la plus à l'ouest est une perle blanche (46) : Parallèlogramme descripteur Pp=53,nc=9,k=2 de la parure Pp=53,1ic_9 ; la perle la plus à l'ouest est une perle blanche (47) : Parallèlogramme descripteur Pp=53,nc=9,k=3 de la parure Pp=53,nc=9 ; la perle la plus à l'ouest est une perle blanche (48) : Parallèlogramme descripteur Pp=53,nc=9,k=4 de la parure Pp=53,nc=9 ; la perle la plus à l'ouest est une perle blanche; (49) : Parallèlogramme descripteur Pp=53,nc=9,k=5 de la parure Pp=53,nc=9 ; la perle la plus à l'ouest est une perle noire ; (50) : Parallèlogramme descripteur Pp=53,nc=9,k=6 de la parure Pp=53,nc=9 ; la perle la plus à l'ouest est une perle blanche; (51) Indice bp=53,nc=9,k=4 de la base du parallèlogramme descripteur Pp=53,nc=9,k=4 ; la valeur de l'indice bp=53,nc=9,k=4 est calculée en appliquant la méthode exposée au chapitre IV ; bp=53,nc=9,k=4=3 ; (52) : Perle blanche la plus à l'ouest de la base du parallèlogramme descripteur Pp=53,nc=9,k=4 ; la perle blanche est située à l'intersection de la colonne k=4 avec la ligne n=3 définie par l'indice bp=53,ncù9,k=4 ; elle masque le résidu r=35, [sur la figure 2, le résidu r=35 apparaît en transparence] ; (53) : Bracelet du quart nord ouest de la parure Pp=53,nc=9 ; (54) : Bracelet du quart nord est de la parure Pp=53,nc=9 ; (55) : Bracelet du quart sud est de la parure Pp=53,nc=9 (56) : Bracelet du quart sud ouest de la parure Pp=53,nc=9 Revendications1. Procédé pour évaluer la vulnérabilité d'un algorithme de cryptographie faisant appel à une exponentiation modulaire d'une racine primitive gp,k (24) d'un nombre premier p ; ledit nombre premier p étant le modulo de ladite exponentiation modulaire ; ledit algorithme de cryptographie étant mis en oeuvre dans un calculateur numérique comportant des ressources informatiques ; ledit nombre premier comportant un si grand nombre de chiffres que la construction d'une table Tp (1) des résidus gp,k^n modp des exponentiations modulaires de ladite racine primitive modulo ledit nombre premier excède lesdites ressources informatiques ; de sorte que ledit calculateur numérique ne permet pas de calculer un logarithme discret d'un résidu donné (52) d'une exponentation modulaire en procédant à une inversion d'une table Tp (1) des résidus des exponentiations modulaires ; pour mettre en évidence la vulnérabilité dudit algorithme de cryptographie ledit procédé consistant à calculer la valeur (51) d'un logarithme discret d'un résudu donné (52) en mettant en oeuvre au moyen dudit calculateur numérique les étapes suivantes : • l'étape de sélectionner de manière heuristique des descripteurs ayant des formes quadrangulaires (45,46,47,48,49,50) imbriquées explicitant la structure de ladite table Tp (1) des résidus des exponentiations modulaires sans qu'il soit nécessaire de calculer les valeurs numériques de chacun des résidus ; lesdits descripteurs (45,46,47,48,49,50) occupant dans ladite table des résidus des positions liées à la valeur du rang k des racines primitives gp,k ; • l'étape de déterminer la position (24) dans la table des résidus (1) du descripteur spécifique (48) relatif à la racine primitive considérée et au résidu (52) dont on cherche à calculer la valeur (51) du logarithme discret. 2. Procédé selon la revendication 1 ; ledit procédé étant tel que dans le cas où (pù1)/2 est impair on sélectionne des formes quadrangulaires imbriquées se présentant sous la forme de prismes parallélépipédiques. 3. Procédé selon la revendication 1 ; ledit procédé étant tel que dans le cas où (pù1)/2 est pair on sélectionne des formes quadrangulaires imbriquées se présentant sous la forme de parallélogrammes descripteurs (45,46,47,48,49,50). 4. Procédé selon la revendication 3 ; chaque parallèlogramme descripteur spécifique ayant une base ; ledit procédé étant tel que pour déterminer la position du descripteur spécifique (48) dans ladite table des résidus on repère la position (51) de ladite base au moyen d'un indice variant de manière modulaire en fonction d'un incrément Sp,k caractéristique du rang k (24) de la racine primitive gp,k considérée. 5. Procédé selon la revendication 4 ; le modulo selon lequel varie ledit indice caractérisant la position de ladite base étant égal à (p-1)/2.10