FR 2868897 A1 20051014 FR 0403801 A 20040409 B11281 FR PROCEDE ET SYSTEME POUR DETERMINER LES STRUCTURES INVARIANTES DE TRES GRANDS NOMBRES ENTIERS. APPLICATION AUX ALGORITHMES DE CRYPTOGRAPHIE. Préambule de la description Domaine concerné La présente invention concerne un procédé et un système pour déterminer les structures invariantes de très grands nombres entiers. La présente demande concerne également une application du procédé et du système selon l'invention aux algorithmes de cryptographie. Problème posé La mise en uvre de certains algorithmes de cryptographie et/ou de contrôle de l'authenticité d'une entité et/ou de l'authenticité d'un message et/ou de signature de message implique l'utilisation de nombres entiers (notamment de très grands nombres entiers, premiers ou non) possédant des propriétés mathématiques. Aussi, il est parfois nécessaire de disposer de cribles algorithmiques permettant de procéder à des sélections parmi les nombres entiers afin de rechercher ceux qui ont des propriétés mathématiques prédéterminées. Plus particulièrement, ces cribles doivent être conçus pour construire et vérifier que certains nombres entiers et/ou premiers ont des structures prédéterminées. Plus particulièrement encore, ces cribles algorithmiques doivent être conçus pour construire et vérifier que la somme de certains nombres entiers et/ou premiers ont des structures prédéterminées. Définitions (1) Structure d'un nombre entier ou plus généralement d'un élément mathématique On désigne par structure d'un élément mathématique, par exemple structure d'un nombre entier, un descripteur, notamment une forme géométrique, élaborée dans un langage appartenant à un système mathématique de degré d'abstraction supérieur à celui du champ des éléments mathématiques considérés, permettant de décrire des propriétés générales desdits éléments mathématiques indépendantes des valeurs particulières de ceux-ci. (2) Forme développée en puissance de 2 d'un nombre entier A Dans la suite de la description, on appellera forme développée en puissance de deux d'un nombre entier A un 20 descripteur se présentant sous la forme: A = [(0;1) + (0;1)2 + {0;1)22 +... + (0;l)2i +...+ 2m] (2) où, par convention, le symbole (0;1) représente un coefficient multiplicatif prenant la valeur 0 ou 1. Un forme développée en puissance de deux d'un nombre entier constitue une variété de descripteur. On appellera degré d'une forme développée en puissance de 2 l'exposant m du dernier terme 2m de la suite. Le dernier terme 2m est la puissance de 2 immédiatement inférieure à A (par exemple A = 49: 25 = 32 est la puissance de 2 immédiatement inférieure à A, 5 est le degré de forme développée). On peut aisément démontrer qu'il n'existe qu'une seule forme développée pour un nombre entier donné. Nota: Si A est impair le premier terme est égal à 1: A.impair = [1 + (0;1) 2 + (0;1)22 +... + (0;1)21 +...+ 2m] Si A est pair le premier terme est égal à 0: A pair = [(O;1)2 + (0;l)22 +... + (0;1)21 +...+ 2m] Dans le cas où A est pair on peut donc mettre 2k en facteur (m > k >- 1) A pair =2k [1 + (0;1)2 + (0;1) 22 +... + (0;1) 21 +...+ 2m] Le cas des nombres A pair peut donc être réduit au cas des nombres Aimer, en étudiant le membre entre crochet (3) Trous d'un nombre entier impair Dans la suite de l'exposé, on appellera trou d'une forme développée en puissance de 2 d'un nombre entier impair les coefficients (0;1) des puissances de 2 prenant la valeur O. On appelle rang du trou, la position du trou dans la séquence 1 + (0;1) 21 + (0;1)22 +... + (0;1) 21 +...+ 2m. Le rang 1 est attribué au premier coefficient (0;1). Le rang 1 est le rang du terme de (0;1)1.21'. (4) Structure mathématique d'un nombre entier impair On appelle structure mathématique d'un nombre entier impair les rangs des trous. Par exemple A = 25 a pour développement: A = 1 +(0)1.21 + (0)2.22 + 23 + 24 La structure mathématique de A comporte deux trous aux rangs 1 et 2. (5) Invariant de structure mathématique d'un nombre entier impair On appelle invariant de structure mathématique des nombres entiers impairs, les parties des structures mathématiques desdits nombres entiers qui sont conservées par des opérations mathématiques, notamment des multiplications, effectuées sur lesdits nombres entiers. Solution Procédé L'invention concerne un procédé pour contrôler l'authenticité d'une entité et/ou l'authenticité d'un message et/ou la signature de message au moyen de nombres entiers impairs et/ou de nombres premiers. Le procédé comprend l'étape de générer des nombres entiers impairs et/ou des nombres premiers ayant des structures mathématiques prédéterminées présentant des invariants. De préférence selon l'invention, le procédé comprend 5 les étapes suivantes: - l'étape de mettre en oeuvre un descripteur, notamment une foime développée en puissance de deux des nombres entiers ou une forme du type 2vS, - l'étape de sélectionner au moyen dudit descripteur 10 des nombres entiers dont ladite structure mathématique présente au moins un invariant. De préférence selon l'invention, le procédé est tel que l'invariant de structure des nombres entiers ainsi sélectionnés comporte au moins deux trous aux rangs un et deux 15 dudit développement en puissance de deux des nombres entiers. De préférence selon l'invention, le procédé comprend en outre, pour sélectionner au moyen du descripteur des nombres entiers impairs dont la structure mathématique présente ledit invariant: - l'étape d'élever à une puissance paire 2n quelconque un nombre entier impair A quelconque. On obtient ainsi la nième puissance du carré de A: [A2]n. La structure mathématique de [A2]n comprend au moins deux trous aux rangs un et deux. De préférence selon l'invention, le procédé est plus particulièrement conçu pour générer, à partir de deux nombres entiers impairs A et B quelconques, un très grand nombre entier dont la factorisation par deux se présente sous la forme 2kS où S est un nombre impair. A cet effet, le procédé comprend en 30 outre les étapes suivantes: - l'étape de former une puissance 2nième de A égale à [A2]n, n étant un exposant entier quelconque, - l'étape de former une puissance 2nième de B égale à [B2]n, n étant un exposant entier quelconque, 25 - l'étape de former la somme desdites puissances de A et B; On obtient ainsi un nombre entier [A2]n + [A2]n se présentant sous la forme 2kS, où k est soit un exposant non multiple de 2n soit un exposant inférieur à 2n. Cet exposant est en général égal à 1, sauf pour quelques valeurs particulières déterminables de A ou B. S est un nombre impaire n'ayant pas la structure d'une puissance nième paire. De préférence selon l'invention, le procédé est tel que l'invariant de structure des nombres entiers ainsi sélectionnés comporte une suite régulière de puissances de deux croissantes suivie d'au moins un trou. De préférence selon l'invention, le procédé comprend en outre, pour sélectionner au moyen du descripteur des nombres entiers impairs dont la structure mathématique présente ledit invariant, l'étape d'élever à une puissance impaire 2n +1 quelconque un nombre entier impair A quelconque. On obtient ainsi [A2n+1]. La structure mathématique de [A2n+1 ] comprend un invariant constitué par au moins un trou situé au rang m+l, où m désigne le rang précédent le premier trou du développement en puissance de deux de A ou à défaut le degré de A. Le développement des m premiers rangs de [A2n+1] est identique à celui des m premiers rangs de A. De préférence selon l'invention, le procédé est plus particulièrement conçu pour générer, à partir de deux nombres entiers impairs A et B quelconques, un très grand nombre entier dont la factorisation par deux se présente sous la forme 2kS où S est un nombre impair. A cet effet, le procédé comprend en outre les étapes suivantes: - l'étape d'élever A à une puissance 2n+1, [A2n+1], n étant un exposant entier quelconque, - l'étape d'élever B à une puissance 2n+1, [B2'1], n étant un exposant entier quelconque, - l'étape de former la somme desdites puissances de A et B; On obtient ainsi un nombre entier [A2n+1] + [A2n+l] se présentant sous la forme 2kS où k est soit un exposant inférieur à 2n+1 et le plus souvent égal à 1 soit une exposant non multiple de 2n+1 et/ou S est un nombre impair n'ayant pas la structure d'une puissance nième impaire. Système L'invention concerne également un système pour contrôler l'authenticité d'une entité et/ou l'authenticité d'un message et/ou la signature de message au moyen de nombres entiers impairs et/ou de nombres premiers. Le système comprend des moyens de traitement informatique pour générer des nombres entiers impairs et/ou des nombres premiers ayant des structures mathématiques prédéterminées présentant des invariants. De préférence selon l'invention, les moyens de traitement informatique comportent: - des moyens de calcul pour calculer un descripteur, notamment une forme développée en puissance de deux des nombres entiers ou une forme du type 2 S, - des moyens de sélection pour sélectionner au moyen 20 du descripteur des nombres entiers dont la structure mathématique présente au moins un invariant. De préférence selon l'invention, le système est tel que l'invariant de structure des nombres entiers ainsi sélectionnés comporte au moins deux trous aux rangs un et deux du développement en puissance de deux des nombres entiers. De préférence selon l'invention, les moyens de calcul comprennent en outre, pour sélectionner au moyen dudit descripteur des nombres entiers impairs dont ladite structure mathématique présente ledit invariant, des moyens permettant d'élever à une puissance paire 2n quelconque un nombre entier impair A quelconque. On obtient ainsi la nième puissance du carré de A: Win. La structure mathématique de Win comprend au moins deux trous aux rangs un et deux. De préférence selon l'invention, les moyens de traitement informatique sont plus particulièrement conçus pour générer, à partir de deux nombres entiers impairs A et B quelconque, un très grand nombre entier dont la factorisation par deux se présente sous la forme 2kS, où S est un nombre impaire. A cet effet, les moyens de calcul comprennent en outre: - des moyens pour former une puissance 2nième de A égale à [A2]n, n étant un exposant entier quelconque, - des moyens pour former une puissance 2nième de B égale à [B2]n, n étant un exposant entier quelconque, - des moyens pour former la somme desdites puissances de A et B. On obtient ainsi un nombre entier [A2]n + [A2]n se présentant sous la forme 2kS, où k est soit un exposant inférieur à 2n le plus souvent égal à 1 soit une exposant non multiple de 2n, sauf pour quelques valeurs particulières déterminables de A ou B et/ou S est un nombre impair n'ayant pas la structure d'une puissance nième paire. De préférence selon l'invention, le système est tel que l'invariant de structure des nombres entiers ainsi sélectionnés comporte une suite régulière de puissances de deux croissantes suivie d'au moins un trou. De préférence selon l'invention, les moyens de calcul comprennent en outre, pour sélectionner au moyen dudit descripteur des nombres entiers impairs dont ladite structure mathématique présente ledit invariant, des moyens pour élever à une puissance impaire 2n +1 quelconque un nombre entier impair A quelconque. On obtient ainsi [A2n+i]. La structure mathématique de [A2n+i] comprend un invariant constitué par au moins un trou situé au rang m+l, où m désigne le rang précédent le premier trou du développement en puissance de deux de A ou à défaut le degré de A. Le développement des m premiers rangs de [A2nn] est identique à celui des m premiers rangs de A. De préférence selon l'invention, les moyens de traitement informatique sont plus particulièrement conçus pour générer, à partir de deux nombres entiers impairs A et B quelconques, un très grand nombre entier dont la factorisation par 2 se présente sous la forme 2kS où S est un nombre impair. A cet effet, les moyens de calcul comprennent en outre: - des moyens pour élever A à une puissance 2n+1, n étant un exposant entier quelconque, - des moyens pour élever B à une puissance 2n+1, n étant un exposant entier quelconque, - des moyens pour former la somme desdites puissances de A et B. On obtient ainsi un nombre entier [A2n+1] + [A2n+1] se présentant sous la forme 2kS où k est soit un exposant inférieur à 2n+1 le plus souvent égal à 1 soit non multiple de 2n +1 et où S est un nombre impair n'ayant pas la structure d'une puissance nième impaire. Définitions et notions mathématiques à la base de l'invention On comprendra mieux le procédé selon l'invention si préalablement les concepts mathématiques qui sont à la base de celle-ci sont explicités. Forme développée en puissance de 2 d'un nombre entier On peut aisément montrer que tout nombre entier A peut 25 être représenté sous la forme A = [(O;1) + (0;1)2 + (0;1)22 +... + {0;1)21 +...+ 2m] où, par convention, le symbole (0;1) représente un coefficient multiplicatif prenant la valeur 0 ou 1. On appellera une telle représentation la forme développée en puissance de deux d'un nombre. On appellera degré d'une forme développée en puissance de deux l'exposant m du dernier terme de la suite (2m est la puissance de deux immédiatement inférieure à A (exemple A = 49: 25 = 32 est la puissance de 2 immédiatement inférieure à A, il n'y a qu'une puissance de 2 remplissant cette condition). [A2n+1] [ B2n+1] Nota: Si A est impair le premier terme est égal à 1: A impair = [1 + (0;1)2 + (0;1)22 +... + (0;1)21 +...+ 2m] Si A est pair le premier terme est égal à 0: A pair = [(0;1)2 + (0;1)22 +... + (0;1)21 +... + 2m]) Dans le cas où A est paire on peut donc mettre 2k en facteur (k >1) A pair =2k [1 + (0;1)2 + (0;1)22 +... + (0;1)21 +...+ 2m] (4') On peut donc réduire le cas de A pair au cas de A 10 impair, en analysant le nombre entre crochet: Trou d'un nombre entier. Dans la suite de l'exposé on appellera trou d'une forme développée en puissance de deux les coefficients (0;1) des puissances de deux prenant la valeur O. On appelle rang du trou, la position du trou dans la séquence (0;1)2 + (0;1)22 +... + (0;1) 21 +...+ 2m. Le rang 1 est attribué au premier coefficient (0;1) facteur de 2. Le terme du rang 0 est égal à 1. Apparition et migration d'un trou Les opérations arithmétiques, multiplication et élévation à une puissance font apparaître et migrer les trous dans le développement en puissance de deux d'un nombre entier (a) L'élévation au carré d'un nombre entier impair fait apparaître des trous On peut aisément démontrer que l'élévation au carré 25 d'un nombre entier impaire fait apparaître des trous. Si le nombre A ne comporte pas de trou, l'élévation au carré de ce nombre fait apparaître des trous. Les trous apparaissent au début du développement en puissance de 2. Si le degré de A est m, A2 comporte m+l trous situés entre le rang 1 et le rang m + 1. Le degré de A2 est 2m + 1. Si le nombre A comporte un trou au rang m+l, l'élévation au carré de ce nombre fait apparaître des trous. Les trous apparaissent au début du développement en puissance de 2. Si le rang du trou est m + 1, A2 comporte m+1 trous situés entre les rangs 1 et m+l. Ainsi, quelque soit la structure de A, les trous de [A2] apparaissent toujours aux mêmes emplacements. (b) Généralisation au cas d'une puissance paire quelconque [A2]n de [A2] Les résultats ci-après mentionnés ont été démontrés par récurrence. Il convient de distinguer le cas où l'exposant n est du type n = p.2 du cas où l'exposant n est du type n = (2p+1).2 où p désigne un entier. Premier cas n = p.2 Dans le premier cas, on forme la suite des [A2] 2, [A2] 4, [A2]6... Dans ce premier cas on constate que le nombre de trous augmente d'une unité chaque fois que l'exposant v de n = 2 augmente d'une unité. Ainsi le nombre de trous passe de m+l (v=0) à m+2 (v=1). En revanche, entre chaque incrémentation de v le nombre de trous reste constant ou fluctue. Autrement dit on peut écrire [A2]n dans le cas où n = p.2 sous la forme: [A2]n = 1 + 0 + (0;1).2m+1+ (0;1).2m+2+ (0;1).2m+3+ ... Deuxième cas n = (2p+1).2 Dans le deuxième cas on forme la suite des [A2] 1, [A2] 3, [A2] 5... Dans ce deuxième cas on constate que le nombre de trous est constant, quelque soit la valeur de p, il est égal à m+l. Autrement dit on peut écrire [A2]n dans le cas où n = (2p+1).2 sous la forme: [A2] n = 1 + 0 +.2'1+2+ 2m+3 + Synthèse. L'invariant Quelque soit le cas considéré, on constate donc que le nombre de trous est au moins égal à m+ l. Par ailleurs, comme m 30 1, le nombre de trous est au moins égal à 2. AE peut donc s'exprimer sous la forme générale suivante quelque soit la valeur de l'exposant E: AE = 1 + 0 +0 + (0;1).23+ (0;1) 24 +... Par ailleurs on sait qu'il existe au moins un rang 35 pour lequel le coefficient (0;1) est égal à 1. Dans la suite 10 de l'exposé on désignera par ma le premier rang de AE pour lequel le coefficient (0;1) est égal à 1. (c) L' élévation au cube d'un nombre entier impair fait apparaître des trous On peut aisément démontrer que l'élévation au cube d'un nombre entier impair fait apparaître des trous. Si le nombre A de degré m ne comporte pas de trous ou si le nombre A de degré d comporte un trou au rang m +1 l'élévation au cube de ce nombre fait apparaître des trous. On trouve É entre les rangs 0 et m le développement de A, suivi É au rang m+l d'un trou au rang m+l, suivi É du teinte 2m+2 au rang m+2, ensuite É à partir du rang 2m+3 au moins deux trous. Cas particulier où m = 0 Dans le cas où m=0 (n impair) le début du développement de A3 comporte un trou au rang 1. (d) Généralisation au cas d'une puissance impaire quelconque (A'] de [A] Les résultats ci-après mentionnés ont été démontrés par récurrence. Dans le cas où A de degré m ne comporte pas de trous, le début du développement de A2n+1 est le même que celui de A, il comporte un trou au rang m+l. Dans le cas où A de degré d comporte un trou au rang m+l, le début du développement de A2n+1 est le même que celui de A, il comporte un trou au rang m+l. Cas particulier où m = 0 Dans le cas où m=0, un trou supplémentaire peut 30 apparaître au début du développement Somme des puissances nièmes des carrés Win et [B2]' de deux nombres entiers A et B On a vu que les développements en puissance de deux des puissances nièmes [A2]n et [B2]n des carrés [A2] et [B2] de deux nombres entiers A et B quelconques ont une structure du type [A2]n = 1 + 0 + 0 + (0,1) 23 + ... Cette structure constitue un invariant indépendant de la valeur du nombre considéré ou indépendant de la puissance énième considérée. On dispose donc d'un outil puissant pour étudier la somme ou la différence des puissances nièmes des carrés [A2]n et [B2]n de deux nombres entiers A et B. La somme [A2] n + [B2] n peut donc s'écrire sous la 10 forme: [A2]n + [B2]n 2 + 0 + 0 + [(O,l)a3+(O,l)b3] 23 + [(O,l)a4+(O,l)b4] 24 +... On peut donc mettre le nombre premier 2 en facteur dans [A2] n + [B2] n [A2]n + [B2]n 21[ 1 + [ (O,l)a3+(O,l)b3] 22 + [ (O,l)a4+(O,l)b4] 23 +... Le nombre entre crochet est donc un nombre impair. L'exposant du facteur premier 2 est égal à 1. Nota: É Si (0,1)a3 = 1 et si (0,1)b3 = 1 le crochet s'écrit alors [ 1 + 2. 22 + ...DTD: É Si (0,1)a3 = 1 et si (0,1)b3 = 0 ou si (0,1)a3 = O ou si (0,1)b3 = 1 le crochet s'écrit alors [ 1 + 22+ É Si (O,1)a3 = O et si (O,l)b3 = O le crochet s'écrit alors [ 1 + [(0,1), 4+(0,1)b4].24+ La structure 2 + 0 + 0 + dont on a démontré l'existence joue un rôle capital. En effet si au lieu de cette structure nous avions obtenu la structure: 2 + (0,1).2 +(0,1)22 + (0,1).23 la somme [A2]n + [B2]n aurait pu faire apparaître, pour certaines valeurs de A et B, des combinaisons du type: 2 +[(O,l)a+(O,l)b].2 + [(O,l)a2+(O,l)b2] 22 + [(O,l)a4+(O,l)b4] 23 +... 25 2868897 13 par exemple telles que: 2 + 2 + 22 +23 + que l'on sait réduire par régression. Autrement dit [A2]' + [B2] n aurait pu se présenter sous la forme [A2]n + [B2]n = 24[ 1 + [(0,1)a3+(0,1)b3] 22 + [(O,1)a4+(0,1)b4] 23 +... La suite de la démonstration par l'absurde aurait échoué sauf à déterminer la valeur de q. Cas particulier m = 0 [A2] n=1 + 0 +(0;1)a222 +...+ (O;l)a224 [B2] n=1 + 0 +(0;1)b222 +...+ (0;1)b224 [A2]n + [B2]n = 21[ 1 + [(O,l)a2+(O,l)b2] 2 + ... Somme des puissances nièmes impaires [A2 +1] et [Bain] de deux nombres entiers A et B On a vu que les puissances nièmes impaires [A2n+1] et [B2n+1] de deux nombres entiers A et B présentent les caractéristiques de structure suivantes: A2'+1 = 1 + 2 + 22 + ... + 2ma + 0 + 2 ai + ... où ma désigne le degré de A ou le rang du terme A précédent le premier trou (on traitera à part le cas où ma = 0) 20, où ai désigne le rang du premier terme non nul suivant le ou les premiers trous B2'+1 = 1 + 2 + 22 + ... +2mb + 0 +2bi+... où mb désigne le degré de B ou le rang du terme de B précédent le premier trou (on traitera à part le cas où mb = 0), où bi désigne le rang du premier terme non nul suivant le ou les premiers trous. Supposons ma > mb. Formons A2n+1 + B2n+1 A2n+1 + B2n+1 = 1 + 2 + 22 + ... + 2mb-1 + 2 b + 2mb+1 +... + + 0 + 2 a1 +... 1 + 2 + 22 + ... + 2mb-1 + 2mb + 0 + 2bi + ... Soit encore en supposant 2al > 2bi. (le cas où 2bi > 2ai ne change pas le suite de l'exposé) : A2n+1 + B2n+1 = 2 + 22 +23 + 24 + ... + 2.2mb + 2mb+1 + 0 + 2n'a + 0 + 2bi + ...+ 0 + 2a1+... Soit encore A2n+1 + B2n+1 = 2. [1 + 2 +22 + 23 + + 2mb + 2mb + 0 + 2 1 + 0 + 2bi-1 + + 0 + 2ai-1 + ] Soit encore en après simplification: 2. [1 + 2 +22 + 23 + ... + 2mb-1 + 0 + 2mb+1 + 0 + 2-1 + 0 + 2bi-1 + ...+ 0 + 2ai-1 + ...] Le nombre entre crochet est un nombre impair. L'exposant du facteur premier 2 est égal à 1. Cas particulier ma = mb Dans le cas particulier où ma = mb, A2n+1 + B2n+1 prend la forme particulière suivante A2n+1 + B2n+1 = + 2 + 22 + ... + 2mb-1 + 2mb + 0 + 0 + 2ai +... 1 + 2 + 22 + ... + 2mb-1 + 2mb + 0... + 2bi + ... Sous cas du cas ma = mb 2ai 2ai (on supposera gaz > 2ai) Dans le cas où 2ai,E 2ai A2n+1 + B2n+1 s'écrit comme suit: A2n+1 + B2n+1 +2 +22+...+2mb-1+2mb+0 +...+...+2d1+... + 2 + 22 + ... + 2mb-1 + 2mb + 0 + ...+ 2bi + ... Soit encore: +.+ A2n+1 + B2n+1 = 2 [1 + 2 + 22 + 2ai-bi +...] Le nombre entre crochet + 2mb-1 + 2mb+ ... + 2bi-1 [1 est un nombre impaire. L'exposant du facteur premier 2 est égal à 1. Sous cas du cas ma = mb: 2ai = 2bi Le cas où 2ai = 2bi ne change rien à l'exposé Cas particulier ma ou mb = 0 Dans le cas où ma = 0 (mb 0), les expressions de A2n+1 et B2n+1 prennent des valeurs particulières ' A2n+1 = 1 + 0 + (0,1) a222 + (0,1)a323 +... + 2ai + + 2da où ai désigne le rang du premier terme non nul suivant le ou les premiers trous, où di désigne le degré de A2n+1, B2n+1 = 1 + 2 + (0,1)b222 + (0,1)b323 +... +2 + 0 + 2bi +...+2b où mb désigne le degré de B (ou le rang du terme de B précédent le premier trou), où bi désigne le rang du premier terme non nul suivant le ou les premiers trous, où db désigne le degré de B. Sous cas du cas particulier ma ou mb = 0; ai # bi On supposera ai > bi, (le cas où 2bi > 2ai ne change pas le suite de l'exposé). dans ce cas A2'+1 et B2n+1 s'écrivent de la manière suivante: A2n+1 = 1 + 0 + (0,1) a222 + (0,1) a323 +... + 2ai + + 2da B2'+1 = 1 + 2 + (0,1) b222 + (0,1) b323 +... +2n'b + 0 + 2bi +... + D'où l'expression de A2n+i + B2n+1 A2n+1 + B2n+1 = 2 + 2 + [ (0, 1) a2 + (0, 1) b2] 22 +[(0,l)a3 + (0, 1) b3] ... + 2'b + 0 + 2bi +...+ 2ai + ... +2b + ... + 2da On constate que dès qu'au rang i: (0,1)ai = (0, 1)bi, la chaîne A2n+1 + B2n+1 prend alors la forme suivante: 2 + 2 + 22 + 23... + 2i-1 + 0 + [ (0,1) ai+i + (0,1) bi+1] 2i+1 + 2 5...+ 2 + 0 + 2b + 2bi +...+ 2ai + ... +2db + ... + 2da Soit encore: A2n+1 + B2n+1 = 22 + 22 + 23 +... + 2i-1 + 0 + [ (0, 1) ai+i + (0,1) bi+1] 2i+1 + ...+ 2 + 0 + 2 + 2bi +...+ 2ai + ... +2ib + ... + 2da Nota: une telle forme sera au plus composée des termes suivants: A2n+1 + B2n+1 22+22+23+...+2 +0+2b+2bi+...+2ai+...+2b+... + 2da Revenons à la forme générale A2n+1 + B2n+1 = 22 + [(0,l).2 + (0,l)b2]22 + [(0,1)a3 + (0,1)b3]... + 21"b + 0 + 2bi +...+ tai + ... +2db + ... + 2da Le processus de fusion des couples de puissance paire successifs crée à chaque étape une puissance de deux impaire, en effet: 22+22->23 Toutefois, ce processus d'émergence d'une puissance de deux impaire n'est possible que si le second terme en 22 suivant le premier terme en 22 existe. S'il n'existe pas, la chaîne s'arrête au premier couple de puissance paire 22. Autrement dit. A2n+1 + B2n+1 = 22 [Impaire] ; A2n+1 + B2n+1 = 2' [Impaire], avec v = 2. La puissance impaire 23 ainsi formée s'annule avec le 15 terme en 23 suivant pour former une nouvelle puissance paire: 23 + 23 -> 24 Toutefois, ce processus d'annulation n'est possible que si le terme en 23 suivant le couple de puissances paires 22 + 22 + 23 existe. S'il n'existe pas la chaîne s'arrête au deuxième couple de puissance paire 22. Autrement dit: A2n+1 + B2'+1 = 2' [Impaire], avec v = 8 De proche en proche on constate que l'on obtient la succession des puissances de deux [2][2]^P. Autrement dit la structure de v est de la forme: v=2P Autrement dit v est paire (on peut montrer que p = i) A2n+1 + B2n+1 = 2V [1+ [ (0, 1) ai+1 + ( 0, 1) bi+ 1] 2 + ...+ 2 db-i + avec v = 2i. Différence des puissances nièmes des carrés [A2]n et [B2]n de deux nombres entiers A et B On a vu que les développements en puissance de deux des puissances nièmes Win et [B2] n des carrés [A2] et [B2] de deux nombres entiers A et B quelconques ont une structure du type. [A2]n = 1 + 0 + 0 + (0,1)23 + ... Cette structure constitue un invariant indépendant de la valeur du nombre considéré ou indépendant de la puissance énième considérée. La différence [A2]n - [B2]n peut donc s'écrire sous la forme: [A2]n- [B2]n = 2f(2n) [Impair] On sait calculer f(2n) à partir de ma et mb, f(2n) est soit un exposant inférieur 2n, soit un exposant non multiple de 2n. [Impair] est un nombre impair n'ayant pas la structure d'une puissance nième impaire. Différence des puissances nièmes impaires [A'] et [Bn+i] de deux nombres entiers A et B On a vu que les développements en puissance de deux des puissances nièmes impaires [A2'+1] et [B2n+1] de deux nombres entiers A et B peuvent s'écrire sous la forme [A2n+1] = 1 + 2 + 22 +... + 2' + ... [B2n+1] = 1 + 2 + 22 +... + 2 + ... On a supposé que [e+1] > [B2n+1] Dans ces expressions, on a désigné par ma le premier rang du développement de [A2n+i] précédent un trou. De même, on a désigné par mb le premier rang du développement de [A2'+1] précédent un trou. On suppose également, pour faciliter la suite de l'exposé que ma > mb. On sait calculer ma ou mb en fonction de n à partir du développement en puissance de deux de [A2'+1] ou de [B2n+1] 25 Formons [A2n+1] - [B2n+1] , on obtient alors une expression de la forme [e+1] - [B2n+1] = 2f(2n+1) [Impair] ; où f (2n+1) est soit un exposant inférieur à 2n+1 le plus souvent égal à 1, soit non- multiple de 2n +1 et où [Impair] est un nombre impair n'ayant 30 pas la structure d'une puissance nième impaire. Cas particulier où ma ou mb = 0 Lorsque ma ou mb = 0, la méthode exposée ci-dessus dans le cas de la somme des puissances paires est transposable au cas de la différence des puissances impaires. Application de la méthode ci-dessus décrite au second théorème de Fermat La méthode décrite dans la présente demande de brevet a été appliquée auplan industriel pour contrôler l'authenticité d'une entité et/ou l'authenticité d'un message et/ou la signature de message au moyen de nombres entiers impairs et/ou de nombres premiers. Afin de mettre en évidence la puissance de cette méthode, elle sera ci-après appliquée à l'étude du second théorème de Fermat. Selon la conjecture de Fermat (aujourd'hui démontrée par Andrew Wiles au terme de sept ans de recherche mathématique) l'équation en X, Y et Z: Xn + Yn = Zn n'a pas de solution pour n supérieur à 2. Supposons qu'il existe trois nombres A, B, C satisfaisant cette équation, par définition: An+Bn=Cn (1) Il va être établi en mettant en oeuvre les invariants mis en évidence dans la présente description et en raisonnant 20 par l'absurde qu'un telle hypothèse est impossible. Valeurs particulières de A, B et C inacceptables Par hypothèse n>2. É On doit écarter le cas où A = B= 1. En effet, il n'existe pas de valeur de C telle que, 25 quelque soit n > 2, ln + 1n = Cn (1) É On peut vérifier que pour A=l et B = 2, il n'existe pas de valeur de C telle que ln + 2n = Cn (1) En effet, si C = 1, on constate que 1 + 2n > 1. En effet, si C = 2, on constate que 1 + 2n > 2n. En effet, si C = 3, on constate que 1 + 2n 3, on constate que 1 + 2n Les développements mathématiques ci-après écartent les couples (A=1, B=1) et (A=1 et B = 2). Propriétés des sous ensembles de facteurs premiers Sa{Pai} r Sb{Pbi} , Sc{Pci} Supposons qu'il existe trois nombres A, B, C satisfaisant l'équation Xn + Yn = Zn. Par construction: An + Bn = Cn Après décomposition de A, B et C en facteurs premiers puis simplification on obtient trois nombres entiers a, b et c satisfaisant l'équation an + bn = en où a Le facteur premier 2 est un élément de l'un des sous-ensembles Sa, Sb ou Sc L'hypothèse retenue an + bn = en conduit au tableau suivant des parités: a Pair Pair Pair Pair Impair Impair Impair b Pair Pair Impair Impair Pair Impair Impair c Pair Impair Pair Impair Impair Pair Impair (1) (1) (1) (2) 10 2868897 20 (1) Ce cas de figure est impossible. En effet, ainsi que cela vient d'être établi, le facteur premier 2 ne peut être un élément que de l'un des sous-ensembles Sa { Pai} ou Sb { Pbi} OU Sc{ Pci} . (2) Ce cas de figure est impossible. En effet, la somme de deux nombres impairs est paire. Ce tableau fait apparaître qu'il est possible de mettre en facteur dans a ou b ou c le nombre premier 2, élevé à une puissance k >- 1. On peut donc, selon le cas, écrire 10 l'hypothèse retenue sous l'une des formes suivantes: 2kn. aln + bn = en (avec al, b et c premiers avec 2) an + 2kn.bin = en (avec a, bl et c premiers avec 2) an + bn = 2kn. ci" (avec a, b et et premiers avec 2) La suite de la démonstration a pour objet de démontrer que, quelque soit a, b ou c, les équations en x: 2X. ai" + bn = en (avec al, b et c premiers avec 2) an + 2' = en (avec a, bl et c premiers avec 2) an + bn = 2'.c1" (avec a, b et et premiers avec 2) ont des solutions en x inférieures à n ou des solutions en x qui ne sont pas un multiple de n. Alternativement, ou de manière cumulative, la suite de la démonstration a pour objet de démontrer que al' ou bin ou cln ne présentent pas les invariants de structure des puissances nièmes d'un nombre. Si tel est le cas, les formes: 2kn. ain + bn = en an + 2kn.bin = en an + bn = 2kn. cln sont incompatibles avec les solutions des équations 2X. aln + bn = en an + 2X = en an + bn = 2".c1" puisque dans leurs cas: - les exposants de deux ont une valeur inférieure à n, ou ne sont pas des multiples de n et/ou - les structures de al' ou bin ou c1n ne sont pas celles d'une puissance nième d'un nombre. On aura ainsi démontré par l'absurde qu'il n'existe pas de nombres a, b et c et par conséquent de nombres A, B, C 5 satisfaisant la relation: An + Bn = Cn Nota: on peut vérifier aisément que l'étude des équations 2x. al" + bn = en an + 2x. b1n = en an + bn = 2x. cin peut être réduite à celle des équations du type an + bn = 2x.cln (El) an - bn = 2x.cin où par définition a > b (E2) Etude de l'équation El an + bn = 2x.cln (El) Cas où n est impair On a vu que les puissances nièmes impaires [A2n+1] et [B2n+1] de deux nombres entiers A et B présentent des 20 caractéristiques de structure dont la caractéristique d suivantes: A2"+1 = 1 + 2 + 22 + ... + 21"a + 0 + 2'i+ ... + 2 da où ma désigne le degré de A ou le rang du terme A précédent le premier trou (on traitera à part le cas où ma = 0) 25 où ai désigne le rang du premier terme non nul suivant le ou les premiers trous où da désigne le degré de A2n+1 B2n+l = 1 + 2 + 22 + ... + 2mb + 0 + 2bl + ... +2'b où mb désigne le degré de B ou le rang du terme de B précédent le premier trou (on traitera à part le cas où mb = 0), où bi désigne le rang du premier terme non nul suivant le ou les premiers trous, où db désigne le degré de B2n+1 On a vu précédemment que la somme de A2n+1 et B2n+' s'exprime sous les formes ci-après rappelées dans le cas général où ma ou mb 0, puis dans le cas particulier où ma ou mb = 0, Cas général: ma ou mb I 0 A2n+1 + B2n+1 = 2 [Impair] On a vu que si A et B et C sont solutions de l'équation de Fermat, alors l'équation, an + bn = 2x.cin (avec a, b et et premiers avec 2) a nécessairement une solution en x inférieure à n ou 10 une solution en x qui n'est pas un multiple de n. Or pour 2n+1 > 2, on trouve que a2n+1 + b2n+1 = 2.[Impair] La contradiction établissant la démonstration par l'absurde du théorème de Fermat est ainsi mise en évidence Cas particulier: ma ou mb = 0 On a vu que dans le cas où ma ou mb = 0, la structure de A2n+' + B2n+1 est du type. A2n+1 + B2n+1 = 2 [Impair] ; avec 2 paire où v=2p et p = i; i étant le rang pour lequel les coefficients (0,1)aj et (0,1)b, du développement en puissance de deux de A2n+' + B2n+1 sont pour la première fois égaux. Par conséquent, si a, b et c sont une solution de l'équation de Fermat (an + bn = 2'c' n) et sont tels que ma ou mb = 0, c'est à dire tels que la structure de a2n+1 + b2n+' soit du type 2 [Impair], 2 [Impair] doit être égal à 2k(2n+1).c'2n+1 Cette relation implique que v soit un multiple de 2n+1 (v = k. (2n+1)) . Or, on a vu que la structure de a2n+1 + b2n+''implique que v soit pair, v ne peut donc pas être un multiple de l'exposant impair (2n+1) de a2n+1 et b2n+1. On a donc mis en évidence une incohérence entre l'hypothèse de départ [22'c'2] et la structure mathématique caractéristique de A2n+1 + B2n+1: A2n+1 + B2n+1 = 2 V [ 1+ [ (0, 1) ai+1 + ( 0, 1) bi+1] 2 + ...+ 2db-i + .. . + 2da-i] où v est paire. On a donc démontrer le second théorème de Fermat dans le cas où ma ou mb sont nuls. Cas où n est paire On a précédemment démontré que la somme [A2] n + [B2] n peut s'écrire sous la forme: [A2]n + [B2]n = 21[ 1 + [ (0,1)a3+(O,l)b3] 22 + [ (0,1)a9+(O,l)b9] 23 +... Le nombre entre crochet est donc un nombre impair. L'exposant du facteur premier 2 est égal à 1 (v = 1). L' équation en x: an + bn = 2X. cin (avec a, b et c1 premiers avec 2) a donc nécessairement des solutions en x inférieures à n. La contradiction établissant la démonstration par l'absurde est ainsi mise en évidence On peut également étudier le cas où n est pair en se ramenant au cas où n est impair. En effet: Si A, B et C sont une solution de: X2n + Y2n = Z2n alors: A2n+ B2n = C2n Par conséquent: [A2] n+ [B2]n = [C2]n Pour n = 2p+1 cette relation s'écrit: [A2] 2p+1+ [B2] 2p+1 = [02] 2p+1 On en déduit que [A2], [B2] et [C2] sont une solution de X2n+1 + Y2n+1 = Z2n+1 Or, il a été précédemment établi que cette équation n'a pas de solution. Par conséquent, A, B, C ne peuvent pas être 30 solution de: X2n + Y2n = Z2n On démontre donc ainsi par l'absurde que si X2n+1 + Y2n+1 = Z2n+1 n'a pas de solution, alors X2n + Y2n = Z2n 15 20 n'a pas de solution. Etude de l'équation E2 an - bn = 2x.cin où par définition a > b (E2) Cas où n est paire On a vu que les développements en puissance de deux des puissances nièmes [A2]n et [B2]n des carrés [A2] et [B2] de deux nombres entiers A et B quelconques ont une structure du type [A2] n = 1 + 0 + 0 + (0,1) 23 + ... Cette structure constitue un invariant indépendant de la valeur du nombre considéré ou indépendant de la puissance énième considérée. La différence [A2]" - [B2] n peut donc s'écrire sous la forme: [A2]n _ [B2]n = 2f(2n) [Impair] On sait calculer f(2n) à partir de ma et mb, on peut montrer que f(2n) est inférieur à 2n ou que f(2n) est non multiple de 2n Or, on a précédemment démontré que l'hypothèse retenue implique l'une des formes suivantes: 2) 2) 2k2n. a12n + b2n = c2n a2n + 2 k2nÉb12n = c2n a2n + b2n = 2k2n C12n (avec al, b et c premiers avec (avec a, b1 et c premiers avec (avec a, b et et premiers avec 2) Puisque f(2n) = 1 + 2 + 22 +...+ 2 mb +... On a supposé que [A2'+1] > [B2n+1] . Dans ces expressions, on a désigné par ma le premier rang du développement de [A2n+1] précédent un trou. De même, on a désigné par mb le premier rang du développement de [A2n+1] précédent un trou. On suppose également, pour faciliter la suite de l'exposé que ma > mb. On sait calculer ma ou mb en fonction de n à partir du développement en puissance de deux de [A2n+1] ou de [B2n+1]. Formons [A2n+1] _ [B2n+1] , on obtient alors une expression de la forme [A2n+1] - [B2n+1] = 2f(2n+1) [Impair] ; avec f (2n+1) Or, on a précédemment démontré que l'hypothèse retenue implique l'une des formes suivantes: 2k(2n+1) . al(2n+1) + b(2n+1) = c(2n+1) (avec al, b et c premiers avec 2) a (2n+1) + 2k (2n+1) . bl (2n+1) = c (2n+1) (avec a, bl et c premiers avec 2) a(2n+1) + b(2n+1) = 2k(2n+1) c1(2n+1) (avec a, b et et premiers avec 2) Puisque f(2n+1) est inférieur à 2n +1 ou est non multiple de 2n + 1, la contradiction établissant la démonstration par l'absurde est ainsi mise en évidence. Cas particulier où ma ou mb = 0 Lorsque où ma ou mb = 0, la méthode exposée ci-dessus dans le cas de la somme des puissances paires est transposable au cas de la différence des puissances impaires. Appendice mathématique 1. Puissances du carré d'un nombre A (a) Elévation au carré d'un nombre A Cas général m # 0 Un nombre entier impair A de degré n comportant un trou au rang m +1 peut se mettre sous la forme A = 1+ 2 + ... + 2' + 0 + 2m+2...+ 2n Posons [A] = Al + A2 avec Al = [1 +2 + 22 +...+ 2m] et A2 = [2m+1...+ 2n] Formons [A2] = [A1]2 + [A2]2 + 2 [Al] . [A2] Soit encore [A2] = [1+2+22+...+2m]2+ [2m+2 + ...+ 2n]2 + 2. [1 + 2 + 22 +...+ 2m] . [2m+2 + ...+ 2n] Soit encore [A2] = [1 + 2 + 22 +...+ 2m] 2 + [22m+4] . [1 + ...+ 2n-m-2] 2 + [2m+3] . [1 + ...+ 2n-m-3] . [1 + 2 + 22 +...+ 2m] On peut démontrer aisément que: [1 + 2 + 22 +...+ 2m] 2 = 1+ 2m+2 + 2m+3 +...+ 2 +2n"+1 De même: [22111+4] . [1 + ...+ 2n-m-2] 2 = [221[1+4 [ 1+ 2n-m + 2n-m+l +... +22n- 2m+3] Par ailleurs: 2. [1 + 2 + 22 +...+ 2m] É [2m+2 + ...+ 2n] = [ 2m+3] . [1 + ...+ 2n-m-3]. [1+2+22+...+ 2m] Une étude particulière de [1 + ...+ 2n-m-3] [1 + 2 + 22 + .+ 2m] permet d'obtenir le résultat suivant: 1+ 0 + 2n-m-2 + 2n-m-1 + 2 n-m + 2 n-m+1 +...+ 2n-2 On obtient finalement pour [A2] le développement suivant [A2] = 1 + 0 +2m+2 + + 22m+1 + 0 +22m+3+ 22m+4 + 0 +2n+m+1 + 2n+m+2 + 2n+m+3 +0 + _+ 2n+m+5 + ...+ 2n+2m+1 + 0 + 2n+2m+3 +22n +7 Il a donc été établi que si le nombre A de degré n comporte un trou au rang m+1, l'élévation au carré de ce nombre fait apparaître des trous. Les trous apparaissent au début du 30 développement en puissance de 2. Si le rang du trou est m + 1, A2 comporte m+l trous situés entre les rangs 1 et m+1...DTD: Dans le cas d'un nombre A ne comportant pas de trou on obtient un résultat présentant le même invariant: A2 = 1 + 2m+2 + 2m+3+...+ 22m+1 Cas particulier m = 0 Dans ce cas le nombre A peut se mettre sous la forme suivante A= 1+ 0 + [(0;1)a222 +... ] Formons [A2] = A.A 1 + 0 +(0;1)a222 +...+ (0;1)a224 Il a donc été établi que si le nombre A de degré n comporte un trou au rang 1, l'élévation au carré de ce nombre fait apparaître au moins un trou au rang 1. (b) Puissances successives des carrés Win d'un nombre 10 entier A impair Cas particulier de l'élévation au carré d'un nombre déjà élevé au carré : [A2]2 On rencontre notamment un tel cas lorsque l'on multiplie le carré A2 d'un nombre A de degré m ne comportant pas de trou par le carré A2 de ce même nombre (élévation à la puissance 4) A2 = 1 + 2m+2 + 2m+3+...+ 22m+ 1 Par hypothèse le nombre entier A2 de degré 2m+1 comporte m+l trous situés entre le rang 1 et le rang m+l A2= Al + A2 où Al=1 A2 = 2m+2 + ... +2m+1 (le nombre A2 ne comporte pas de trou) 2 5 Formons A2. A2 = [A1 + A2] 2 = Al2 + 2. A1A2 + A22 = 1 + 2.A2 + A22 Etudions séparément les deux termes 2.A2, A22 É 2.A2 = 2 [2m+2 + ... +22m+1] . [1] 2.A2 [2m+3 + ... +22m+2] É A22 = [2m+2 + ... +22m+1]2 A22 = 221E+4 + 0 + 24m+3 Formons: [ A2] 2 = A2. A2 = 1 + 2. A2 + A22 On obtient le résultat suivant: [A2] 2 = 1 + 0 + 2m+3 + ... + 22m+2 + 0 + 2"4 + 0 +2"3 35 Ainsi donc m + 2 trous apparaissent entre les rangs 1 et m + 2, un trou apparaît au rang 2m + 3 et 2m -1 trous apparaissent entre les rangs 2m +5 et 4m + 2. Il a donc été établi qu'en multipliant le carré A2 d'un 5 nombre A ne comportant pas de trou par le carré A2 de ce même ce nombre A on obtient m + 2 trous apparaissant entre les rangs 1 et m + 2, un trou au rang 2m + 3 et 2m -1 trous apparaissant entre les rangs 2m +5 et 4m + 2 Exemples A=7=1+2+22 B = A2 = 49 = 1 + 24 + 25 B. B = A4 = 2401 = 1 + 25 + 26 + 28 + 211 A4 comporte quatre trous aux rangs 1, 2, 3, 4 et un trou après le rang 6 Cas particulier de la multiplication du carré d'un nombre déjà élevé au carré par ce nombre élevé carré : [A2]3. On a vu que [A2] = 1 + 2m+2 + 2m+3+...+ 22m+1 [A2]2 + 0 + 2m+3 + ... + 22m+2 + 0 + 22m+4 + 0 +24m+3 Formons A2. [A4] = [A2]3 Posons A2 = Al + A2 Avec Al = 1 et A2 = [2-2 + 2m+3+,..+ 22m+1] Posons [A2]2= B1 + B2 Avec B, = 1 et B2 = 2m+3 + ... + 22-+2 + 0 + 22m+4 + 0 +24m+3 25 [A2]3= 1 + A2 + B2 + A2B2 On obtient pour [A2]3 [A2]3 = Soit encore [A2] 3 = 1 + 0 + 2m+2 + 0 + 22m+3 + 22m+4 + 0 + 0+ 0 + 26-+6 Il a donc été établi que le cube du carré A2 d'un nombre A ne comportant pas de trou comporte m+l trous entre les rangs 1 et m+l et m 1 trous entre le rang m + 3 et 2m + 2 et au moins un trou aux rangs 2m+5 et suivants. Exemples A = 7 = 1 + 2 + 22 B = A2 = 49 = 1 + 24 + 25 B.B = A4 = 2401 = 1 + 25 + 26 + 28 + 211 B.B.B= A6 = 117649 = 1 +0 + 24 + 0 + 27 + 28+ 29 + 211 + 214 +215 + 216 A6 comporte trois trous aux rangs 1, 2 et 3 et deux trous après le rang 4. Cas particulier de la multiplication du carré d'un nombre déjà élevé au cube par ce nombre élevé carré : [A2]4. On a vu que [A2] + [1 + 2m+2 + 2m+3+...+ 22[11+1] [A2] 3 = 1 + 0 + 2m+2 + 0 + 22m+3 + 22m+4 + 0 + 0 26m+6 [A2] 4 = [A2]3. [A2] Posons A2 = Al + A2 Avec Al = 1 et A2 = [2m+2 + 2n+3+ .+ 22'1] Posons [ [A2] 3] = Bl + B2 Avec Bl = 1 et B2 = 2m+2 + 0 + 22m+ 3 + 22m+4 + 0 + 0+ ... ?... + 26m+ [A2] 4 = [A2] 3. [A2] = 1 + A2 + B2 + A2B2 Soit encore [A2] 4 = 1 + 22m+2 +22m+3+ 0 +2 +5 + 22m+6 + + 28m+4 Il a donc été établi qu'en multipliant le carré A2 d'un nombre A ne comportant pas de trou par le cube [A2] 3 du nombre A2, autrement dit en élevant A2 à la puissance 4: [A2]4, on 25 obtient 2m+1 trous entre les rangs 1 et 2m + 1, un trou au rang 2m + 4...DTD: Rappelons qu'en multipliant le carré A2 d'un nombre A ne comportant pas de trou par le carré [A2] de ce nombre, autrement dit élevant A2 à la puissance 2: [A2]2, on obtient m+2 trous entre les rangs 1 et m + 2 et un trou au rang 2m + 3 et 2m-1 trous entre les rangs 2m+5 et 4m +2 [A2] 2 = 1 + 0 + 2m+3 + ... + 22m+2 + 0 + 22m+4 + 0 +24m+3 Cas particulier de la multiplication de la puissance 4 du carré d'un nombre élevé au carré par le nombre élevé carré. On a vu que A2 = [1 + 2m+2 + 2m+3+...+ 22m+11 [A2] 4 = 1 + 0+ 22m+2 +22m+3+ 0 +22m+5 + 22m+6 +... [A2] 5 = [A2 J4. [A2] Posons A2 = Al + A2 Avec Al = 1 et A2 = [2m+2 + 2m+ 3+...+ 22m+1] Posons [A2] 4 = B1 + B2 Avec B1 = 1 et B2 = 22111+2 +22m+3+ 0 +22m+5 + [A2] 5 = 1 + A2 + B2 + B2A2 Soit encore [A2] 5 = 1 + 0 + 2m+2 + ... +22m+3+ 0 +22' Il a donc été établi qu'en multipliant le carré A2 d'un nombre A ne comportant pas de trou par la puissance 4, [A2]4, du nombre A2, autrement dit en élevant A2 à la puissance 5: [A2] 5, on obtient m+l trous entre les rangs 1 et m + 1, un trou au rang 2m + 4. [A2] 2 = 1 + 0 + 2m+3 + ... + 22m+2 + 0 + 22m+4 + 0 +24m+3 Ainsi donc m + 2 trous apparaissent entre les rangs 1 20 et m + 2, un trou apparaît au rang 2m + 3 et 2m -1 trous apparaissent entre les rangs 2m +5 et 4m + 2 Il a donc été établi qu'en multipliant le carré A2 d'un nombre A ne comportant pas de trou par le carré A2 de ce même ce nombre A on obtient m + 2 trous apparaissant entre les rangs 1 et m + 2, un trou au rang 2m + 3 et 2m -1 trous apparaissant entre les rangs 2m +5 et 4m + 2 Synthèse Cas des puissances impaires [A2], [A2] 3 et [A2]5 de [A2] Rappelons que si le nombre A ne comporte pas de trou, le carré, l'élévation au carré [A2] de ce nombre fait apparaître des trous. Les trous apparaissent au début du développement en puissance de 2. Si le degré de A est m, A2 comporte m+1 trous situés entre le rang 1 et le rang m + 1: [A2] 1 = 1+ 0 + 2m+2 + 2m+3 +... +22m+1 2 8m+4 +21 m+9 + 22m+6 +... +23m+3 +... ?...+ 2 8m+4 22m+6 Rappelons que le cube du carré A2 d'un nombre A ne comportant pas de trou, comporte m+1 trous entre les rangs 1 et m+l et m - 1 trous entre le rang m + 3 et 2m + 2 et au moins un trou aux rangs 2m+5 et suivants. [A2] 3 = 1 + 0 + 2m+z + 0 + 22m+3 + 22n+ + 0 + 0+ 0... + 26m+6 Rappelons que [A2]5, comporte m+l trous entre les rangs 1 et m + 1, un trou au rang 2m + 4: [A2] 5 = 1 + 0 + 2m+2 + + 22m+3+ 0 +2am+5 + 22m+6 + +23ni+3 + +210m+9 Une étude des développements selon les puissances de deux de [A2], [A2]3 et [A2]5 fait apparaître des similitudes: dans tous les cas on observe l'apparition de m+1 trous entre le rang 1 et le rang m+l. Comme m est au moins égal à 1, on peut affirmer que les puissances impaires du type [A2], [A2] 3 et [A2] 5 comporte au moins un invariant constitué par deux trous aux rangs 1 et 2. Cas des puissances paires [A2] 2 et [A2] 4 Rappelons que [A2] 2 = 1 + 0 + 2m+3 + ... + 22m+2 + o + 22m+4 + 0 +24m+3 comporte m + 2 trous entre les rangs 1 et m + 2, un trou au rang 2m + 3 et 2m -1 trous apparaissant entre les rangs 20 2m +5 et 4m + 2 Rappelons que [A2] 4 = 1 + 0 + 22E1+2 +22m+3+ 0 +22i1+5 + 22m+6 +... ... 28i+4 comporte 2m+1 trous entre les rangs 1 et 2m + 1 et un trou au rang 2m + 4. Comme m est au moins égal à 1, on peut affirmer que 25 les puissance paires du type A2]2 et [A2]4 comportent au moins un invariant constitué par deux trous aux rangs 1 et 2 Généralisation aux puissances successives [A2]' du carré d'un nombre A de degré m On peut généraliser ces résultats et démontrer que les 30 puissances paires et impaires du carré A2 d'un nombre A de degré m comportent au moins deux trous aux rangs 1 et 2. Cas des puissances impaires de [A2] Cette proposition est vraie pour [A2] 1 = 1+ 0 + 0 + ... Supposons qu'elle soit vraie pour [A2]2p+1, démontrons 35 qu'elle est également vraie pour [A2] 2p+3. Par hypothèse [A2]2P+1 = 1+ 0 + 0 +... On a vu que [A2] 2 = 1 + 0 + 2m+3 + ... + 22-'2 + 0 + 22-'4 + 0 +24"+3 [A2] 2p+3 = [A2] 2p+1. [A2] 2 Par conséquent la multiplication de [A2] 2p+ 1 par [A2] 2 ne modifie pas l'état des trous des rangs 1 et 2 [A2] 2p+3 = 1 + 0 + 0 +... On a donc établi que [A2]2p+3 comporte également deux 10 trous aux rangs 1 et 2. On a donc établi par récurrence que toute puissance impaire de [A2] comporte m+l trous entre les rangs 1 et m+1. Cas des puissances paires de [A2] On vu que: [A2] = 1+ 0 + 2m+2 + 2m+3 +22m+1 On a vu que [A2] 2p+1 pouvait s'écrire sous la forme [A2] 2p+1 = 1+ 0 + 0... Fo!mons: [A2] 2p+1. [A2] _ [A2] 2 (p+l) La multiplication de [A2] 2p+1 par [A2] 2 ne modifie pas 20 l'état des trous des rangs 1 et 2. Par conséquent, il est possible d'écrire [A2]2'' ) sous la forme [A2] 2(p+l) = 1 + 0 + 0+ ... On a donc établi que, quel que soit p, [A2] 2(p+1) 25 comporte deux trous aux rangs 1 et 2. Nota 1: Les résultats ci-dessus peuvent être généralisés aux nombres entiers comportant des trous. Nota 2: Sim=O Dans ce cas le nombre A peut se mettre sous la forme 30 suivante A= 1+ 0 + [ (0;1)a222 +... ] [A2] n =1 + 0 +(0;1)e22 +...+ (0;1) a229 Il a donc été établi que si le nombre A de degré n comporte un trou au rang 1, l'élévation du carré de ce nombre à 35 une puissance quelconque conserve au moins un trou au rang 1. 2. Puissances impaires d'un nombre A (a) Elévation au cube [A3] d'un nombre A Etude du cas général (m # 0) L'hypothèse retenue est la suivante: A est de degré m 5 et ne comporte pas de trous ou A comporte un trou au rang m+l. On étudiera à part le cas où m = 0 [A] = 1 + 2 +22+...+2m+... Posons [A2] = 1 + A2 avec A2 = [2m+2 + ... +22m+1] = [2m+2] . [1 + ... + 2m-1] Formons A3 = [A2] .A A3 = [1 + A2].[A] = A + A. A2 On obtient: A3 = 1 +...+ 2m +0 +2m+2 + 0 + 22111+2 + 0 +22m+4 + ...+ 23m+2 Il a donc été établi que si le nombre A ne comporte pas de trou, l'élévation au cube de ce nombre fait apparaître des trous. Un trou apparaît au rang m+l, m-1 trous apparaissent entre les rangs m+3 et 2m+1, un trou apparaît au rang 2m+3. Le degré de A3 est égal à 3m+2. Etude du cas particulier m = 0 Dans ce cas particulier A prend la forme suivante: [A] = 1 + 0 +... [A2] = 1 + 0 + ( 0, 1) 22 + ... Formons A3 = [A2].A A3 = 1 + 0 + (0,1) 22 (b) L'élévation à la puissance cinquième d'un nombre entier impair ne comportant pas de trou fait apparaître des trous On a vu que l'élévation au cube d'un nombre entier impaire A de degré m peut se mettre sous la forme [A3] = 1 +...+ 2m +0 +2m+2 + 0 + 22m+2 + 0 +22m+4 + 23m+2 On a vu que l'élévation au carré [A2] d'un nombre entier impair de degré m ne comportant de trou peut se mettre sous la forme [A2] = 1+ 2m+2 +...+22m+1 Formons A5 = [A3] . [A2] 25 30 35 20 25 30 35 Posons [A3] = 1 + Al avec Al = [2 + ... + 2m + 0 +2m+2 + 0 + 22"+2 + o + 2n"+4 + ...+ 23m+2] Posons [A2] = 1 + A2 avec A2 = [2m+2 + 2m+ 3 +...+ 22m +22m+1] A5 = 1 + Al + A2 + A1. A2 Soit encore A5 = 1 + + 2 + + 2m + 0 + 2m+2 + 0 +22m+2 +0 + 22m+4 + ...+ 23m+2 [2 +...+2m+ 0 +... + ...+ 23m+2] . É [2m+2 + 2m+3 +...+ 22m +2zr"+1] Soit encore A5 = 1 + + 2 + + 2m + 0 +221"+3+ [2 + ... + 2m + 0 +... + ...+ 23m-F2] É [ 2m+2 + 2m+3 +...+ 22m +22m+1] Soit encore A5 = 1 + + 2 + + 2m + 0 +221n+3+ 22m+4 + ...+ 2[1 + ... + 2m-1 + 0 +... 22m+3 + ... + 23m+1] . [2m+2] . [1 +...+2m-1] Soit encore A5 = 1 + 2 + + 2m + 0 +22ri+3+ 22m+4 + ... + 23m+2 [2m+3] [[1 + ... + 2m-1]2 + [2m+1 + 0 +22m+1 + 0 + 22m+3 + ...+ 23m+1] . [1 +...+2m-1] ] Soit encore A5 1 + 2 + +2 m+0+ 2 2 - ' 3 +2 2 ' 4++ + 2m+3. [1 + 2m+1 + 2m+2 +...+22m-1] + + 2m+3. [1 +... +2m-1] . [ 2m+1 +0 +22m+1 + 0 + Soit encore A5 = + 2m+2 + 2m+3 +...+ 22m +22m+1 + 2m+2 + 0 +22m+2 + 0 + 22'4 + 2 3m+2 2m+2 + 0 +22m+2 + 0 + 22m+4 + 22m+4 23m+2 2m+1 + 0 +22m+1 + 0 + 23m+2 22m+3 + ...+ 23m+1] 2 3m+2 1+...+2m+0+ + 0 + 22m+3 + 22m+4 + ... + + 2m+3 + 0 + 0 + 22+4 + 22m+ 5 +...+2 +2 + + 2m+3. [1 +... +2m-1] . [ 2m+1 +0 +22m+1 + 0 + 22m+3 + ...+ 23+1] Soit encore A5 =- 1 + ... + 2m + 0 + 2'1+3 + 0 + 221"+3 + 0 + 23m+2 + 231"+4. [1 +... +2m-1] . [1 + 0 +22 + 23 + 24+ 0 + 22m] Il a donc été établi que si le nombre A ne comporte 10 pas de trou, l'élévation à la puissance 5 de ce nombre fait apparaître des trous. Deux trous apparaissent aux rangs m+l et m+2, m-1 trous apparaissent entre les rang 2m+4 et 3m+1, etc... On retiendra que l'élévation à la puissance 5 d'un nombre A fait apparaître deux trous aux rangs m+l et m+2. Ces 15 deux trous constituent les invariants des puissances cinquièmes. Etude du cas particulier m = 0 Dans ce cas particulier [A3] prend la forme suivante: [A3] = 1 + 0 + (0,1) 22 Dans ce cas particulier [A2] prend la forme suivante: [A2] = 1 + 0 + (0,1) 22+ ... On en déduit la valeur particulière de [A3] [A2] = [A5] [A5] =1+0+ (0,1) 22 (c) Généralisation On a établi que pour m 0 l'élévation au cube d'un 25 nombre ne comportant pas de trous fait apparaître un trou au rang m. Supposons que cette propriété soit vraie pour A2n+1 A2n-1 = 1 +...+ 2m +0 + (0,1) 2m+2 Formons A2'''-1.A2 = A2n+1 A2 = 1+ 2m+2 +...+22m+1 A2n+1 = 1 +...+ 2111 +0 + (0,1) 2m+2 + 2m+2 +...+ 2 m+2 +0 + (0,1) 22m+4 Soit encore: A2n+1 = 1 +...+ 2m +0 + (0,1) 2m+2 On a donc démontré par récurrence que la propriété est vraie pour A2n+1 Nota 1: Dans le cas où m = 0, quelque soit n, on peut démontrer par récurrence que [A2n+1] = 1 + 0 + (0,1) 22 Nota 2: On démontre que l'on obtient les mêmes résultats que ci-dessus dans le cas d'un nombre entier impaire comportant un trou au rang m. Il a donc été établi que si le nombre A de degré n comporte un trou au rang m+l, l'élévation une puissance quelconque de ce nombre fait apparaître ou conserve un trou au rang 1. REVENDICATIONS Procédé 1. Procédé pour contrôler l'authenticité d'une entité et/ou l'authenticité d'un message et/ou la signature de message au moyen de nombres entiers impairs et/ou de nombres premiers; ledit procédé comprenant l'étape de générer des nombres entiers impairs et/ou des nombres premiers ayant des structures mathématiques prédéterminées présentant des invariants. 2. Procédé selon la revendication 1; ledit procédé comprenant les étapes suivantes: - l'étape de mettre en oeuvre un descripteur, notamment une forme développée en puissance de deux des nombres entiers ou une forme du type 2'S - l'étape de sélectionner au moyen dudit descripteur des nombres entiers dont ladite structure mathématique présente 15 au moins un invariant. 3. Procédé selon la revendication 2; ledit procédé étant tel que ledit invariant de structure des nombres entiers ainsi sélectionnés comporte au moins deux trous aux rangs un et deux dudit développement en puissance de deux desdits nombres entiers. 4. Procédé selon la revendication 3; ledit procédé comprenant en outre, pour sélectionner au moyen dudit descripteur des nombres entiers impairs dont ladite structure mathématique présente ledit invariant, - l'étape d'élever à une puissance paire 2n quelconque un nombre entier impair A quelconque; de sorte que l'on obtient ainsi la nième puissance du carré de A: [A2] n; de sorte que la structure mathématique de [A2]n 30 comprend au moins deux trous aux rangs un et deux. 5. Procédé selon la revendication 4; ledit procédé étant plus particulièrement conçu pour générer, à partir de deux nombres entiers impairs A et B quelconques, un très grand nombre entier dont la factorisation par 2 se présente sous la forme 2k.S où S est un nombre impair; ledit procédé comprenant en outre les étapes suivantes: - l'étape de former une puissance 2nième de A égale à [A2]n, n étant un exposant entier quelconque, - l'étape de former une puissance 2nième de B égale à [B2]n, n étant un exposant entier quelconque, - l'étape de former la somme desdites puissances de A et B; de sorte que l'on obtient ainsi un nombre entier [A2]n+ Win se présentant sous la forme 2kS, où k est soit un exposant inférieur à 2n le plus souvent égal à 1, soit un exposant non multiple de n sauf pour quelques valeurs particulières déterminables de A ou B et où S est un nombre impair n'ayant pas le plus souvent la structure d'une puissance nième paire. 6. Procédé selon la revendication 2; ledit procédé étant tel que ledit invariant de structure des nombres entiers ainsi sélectionnés comporte une suite régulière de puissances de deux croissantes suivie d'au moins un trou. 7. Procédé selon la revendication 6; ledit procédé 20 comprenant en outre pour sélectionner au moyen dudit descripteur des nombres entiers impairs dont ladite structure mathématique présente ledit invariant, - l'étape d'élever à une puissance impaire 2n +1 quelconque un nombre entier impair A quelconque; de sorte que l'on obtient ainsi [A2n+1] ; de sorte que la structure mathématique de [A2'+1] comprend un invariant constitué par au moins un trou situé au rang m+l, où m désigne le rang précédent le premier trou du développement en puissance de deux de A ou à défaut le degré de A; de sorte que le développement des m premiers rangs de [A2n+1 ] est identique à celui des m premiers rangs de A. 8. Procédé selon la revendication 7; ledit procédé étant plus particulièrement conçu pour générer, à partir de deux 35 nombres entiers impairs A et B quelconques, un très grand nombre entier dont la factorisation par 2 se présente sous la forme 2kS où S est un nombre impair; ledit procédé comprenant en outre les étapes suivantes: - l'étape d'élever A à une puissance 2n+1, [A2n+1], n 5 étant un exposant entier quelconque, - l'étape d'élever B à une puissance 2n+1, [B2'+1], n étant un exposant entier quelconque, - l'étape de former la somme desdites puissances de A et B; de sorte que l'on obtient ainsi un nombre entier [A2n+1] + [A2n+1] se présentant sous la forme 2kS où k est un exposant soit égal à 1, soit inférieur à 2n+l, soit non multiple de 2n+1, sauf pour quelques valeurs particulières déterminables de A ou B et où S est un nombre impair n'ayant pas la structure d'une puissance nième impaire. Système 9. Système pour contrôler l'authenticité d'une entité et/ou l'authenticité d'un message et/ou la signature de message au moyen de nombres entiers impairs et/ou de nombres premiers; ledit système comprenant des moyens de traitement informatiques pour générer des nombres entiers impairs et/ou des nombre premiers ayant des structures mathématiques prédéterminées présentant des invariants. 10. Système selon la revendication 9; lesdits moyens 25 de traitement informatiques comportant: - des moyens de calcul pour calculer un descripteur, notamment une forme développée en puissance de deux des nombres entiers ou une forme du type 2 S, - des moyens de sélection pour sélectionner au moyen 30 dudit descripteur des nombres entiers dont ladite structure mathématique présente au moins un invariant. 11. Système selon la revendication 10; ledit système étant tel que ledit invariant de structure des nombres entiers ainsi sélectionnés comporte au moins deux trous aux rang un et deux dudit développement en puissance de deux desdits nombres entiers. 12. Système selon la revendication 11; lesdits moyens de calcul comprenant en outre pour sélectionner au moyen dudit descripteur des nombres entiers impairs dont ladite structure mathématique présente ledit invariant, - des moyens permettant d'élever à une puissance paire 2n quelconque un nombre entier impair A quelconque; de sorte que l'on obtient ainsi la nième puissance du 10 carré de A: [A2]'; de sorte que la structure mathématique de [A2]n comprend au moins deux trous aux rangs un et deux. 13. Système selon la revendication 12; lesdits moyens de traitement informatique étant plus particulièrement conçu pour générer, à partir de deux nombres entiers impairs A et B quelconque, un très grand nombre entier dont la factorisation par 2 se présente sous la forme 2kS où S est un nombre impair; lesdits moyens de calcul comprenant en outre: - des moyens pour former une puissance 2nième de A 20 égale à [A2]n, n étant un exposant entier quelconque, - des moyens pour former une puissance 2nième de B égale à [B2]n, n étant un exposant entier quelconque, - des moyens pour former la somme desdites puissances de A et B; de sorte que l'on obtient ainsi un nombre entier [A2]n+ Win se présentant sous la forme 2kS, où k est un exposant soit inférieur à 2n le plus souvent égal à 1, soit non multiple de 2n, sauf pour quelques valeurs particulières déterminables de A ou B et/ou S est un nombre impair n'ayant pas la structure d'une puissance nième paire. 14. Système selon la revendication 10; ledit système étant tel que ledit invariant de structure des nombres entiers ainsi sélectionnés comporte une suite régulière de puissances de deux croissantes suivi d'au moins un trou. 15. Système selon la revendication 14; lesdits moyens de calcul comprenant en outre pour sélectionner au moyen dudit descripteur des nombres entiers impaires dont ladite structure mathématique présente ledit invariant, des moyens pour élever à une puissance impaire 2n +1 quelconque un nombre entier impair A quelconque; de sorte que l'on obtient ainsi [A2n+1] ; de sorte que la structure mathématique de [A2'+1] comprend un invariant constitué par au moins un trou situé au 10 rang m+l, où m désigne le rang précédent le premier trou du développement en puissance de deux de A ou à défaut le degré de A; de sorte que le développement des m premiers rangs de [A2'+1] est identique à celui des m premiers rangs de A. 16. Système selon la revendication 15; lesdits moyens de traitement informatique étant plus particulièrement conçus pour générer, à partir de deux nombres entiers impairs A et B quelconques, un très grand nombre entier dont la factorisation par 2 se présente sous la forme 2kS où S est un nombre impair; 20 lesdits moyens de calcul comprenant en outre: - des moyens pour élever A à une puissance 2n+1, [A2n+1 ], n étant un exposant entier quelconque, - des moyens pour élever B à une puissance 2n+1, [B2n+1 ], n étant un exposant entier quelconque, - des moyens pour former la somme desdites puissances de A et B; de sorte que l'on obtient ainsi un nombre entier [e+1] + [A2n+1] se présentant sous la forme 2kS où k est un exposant soit inférieur à 2n+1 le plus souvent inférieur ou égal à 1, soit non multiple de 2n+1 sauf pour quelques valeurs particulières déterminables de A ou B et/ou S est un nombre impair n'ayant pas la structure d'une puissance nième impaire.