Brevet FR2931325A1 — publié le 20091120

-1- Dans le domaine de la cryptographie, la vérification de la primalité d'un nombre est une étape primordiale, commune aux différentes procédures de securisation utilisant des nombres premiers. Les tests de primalité habituellement employés sont compatibles avec les contraintes de temps commercialement acceptables, mais sont cependant probabilistes du fait qu'ils intègrent un risque considéré faible du point de vue mathématique bien que non nul. Le test içi présenté, déclare la primalité de manière rapide et non probabiliste, c'est à dire avec une certitude et cela en se basant sur des congruences mathématiques individuellement vérifiées ou non au sein de combinaisons les associant de diverses manières. Soit (N) le nombre à tester; Les congruences sont . Congruence (A) 20 Congruence (B) Congruence (C) . 25 2" (N-3) ) CN, 1 il ) ù iV-'I L AJJ ( Al22 ); 4 LNj (AL): /1~1LWJ 2 Congruence (D) 5A (�+3)_ 25 L'1 Congruence (E) . 0 [51 Congruence (F) . 30 Congruence (G) 24 (n--3 ) -) LN] Congruence (H) . 6A(ee)~. LA13 y) ~ (t 11 CN] Congruence (I) . 35 -2-Les combinaisons sont Première combinaison Congruences (A) et (F) vérifiées par le nombre à 5 tester. Deuxième combinaison Congruences (A) et (G) vérifiées par le nombre à tester. Troisième combinaison 10 Congruences (C) et (F) vérifiées par le nombre à tester. Quatrième combinaison . Congruences (C) et (G) vérifiées par le nombre à tester. 15 Cinquième combinaison Congruences (F) et (H) vérifiées par le nombre à tester. Sixième combinaisons . Congruences (G) et (H) vérifiées par le nombre à 20 tester. Septième combinaison Congruences (D) et (E) vérifiées par le nombre à tester. Huitième combinaison 25 Congruence (H) non vérifiée et Congruence (I) vérifiée par le nombre à tester. Neuvième combinaison Congruences (B) et (F) vérifiées et Congruence (A) non vérifiée par le nombre à tester. 30 Un nombre est déclaré Premier dès qu'il vérifie une des combinaisons ci-dessus, testées quelque soit l'ordre. Si le nombre n'en vérifie aucune, c'est à dire qu'il 35 vérifie la dixième combinaison : Dixième combinaison Première, Deuxième, Troisième, Quatrième, Cinquième, Sixième, Septième, Huitième et Neuvième Combinaisons -3- non vérifiées par le nombre à tester. Alors, il n'est pas un nombre Premier. Le test pourra titre réalisé au sein d'un logiciel ou implanté sur circuit électronique, en offrant de nombreuses applications cryptographiques. Il sera en mesure d'estimer la valeur des autres tests de primalité ou d'intégrer des logiciels de calculs formels intervenant par exemple dans la génèse de clés de cryptage utilisant des nombres premiers. REVENDICATIONS1) Dispositif pour vérifier la primalité d'un nombre (N) caractérisé en ce qu'il comporte une combinaison de deux congruences mathématiques 2 à la puissance ((N-1)/2) = N-1 modulo (N) et 2 à la puissance (N-3) = (N+1)/4 modulo (N), vérifiées par (N). 2) Dispositif pour vérifier la primalité d'un nombre (N) caractérisé en ce qu'il comporte une combinaison de deux congruences mathématiques 2 à la puissance ((N-1)/2) = N-1 modulo (N) et 2 à la puissance (N-3) = (3xN +1)/4 modulo (N), vérifiées par (N). 3) Dispositif pour vérifier la primalité d'un nombre (N) caractérisé en ce qu'il comporte une combinaison de deux congruences mathématiques 5 à la puissance ((N-1)/2) = N-1 modulo (N) et 2 à la puissance (N-3) = (N+1)/4 modulo (N), vérifiées par (N). 4) Dispositif pour vérifier la primalité d'un 20 nombre (N) caractérisé en ce qu'il comporte une combinaison de deux congruences mathématiques à la puissance ((N-1)/2) = N-1 modulo (N) et 2 à la puissance (N-3) = (3xN +1)/4 modulo (N), vérifiées par (N). 25 5) Dispositif pour vérifier la primalité d'un nombre (N) caractérisé en ce qu'il comporte une combinaison de deux congruences mathématiques : 2 à la puissance (N-3) = (N+1)/4 modulo (N) et 6 à la puissance ((N-1)/2) = N-1 modulo (N), 30 vérifiées par (N). 6) Dispositif pour vérifier la primalité d'un nombre (N) caractérisé en ce qu'il comporte une combinaison de deux congruences mathématiques : 2 à la puissance (N-3) = (3xN +1)/4 modulo (N) et 5 10 15 -5- 6 à la puissance ((N-1)/2) = N-1 modulo (N), vérifiées par (N). 7) Dispositif pour vérifier la primalité d'un nombre (N) caractérisé en ce qu'il comporte une combinaison de deux congruences mathématiques : à la puissance ((N+3)/2) = 25 modulo (N) et (N-1)/2 = 0 modulo (5), vérifiées par (N). 8) Dispositif pour vérifier la primalité d'un nombre (N) caractérisé en ce qu'il comporte une combinaison de deux congruences mathématiques : 6 à la puissance ((N-1)/2) = N-1 modulo (N) et 2 à la puissance ((N-9)/4) = (N-1)/4 modulo (N), dont seule la deuxième est vérifiée par (N). 9) Dispositif pour vérifier la primalité d'un nombre (N) caractérisé en ce qu'il comporte une combinaison de trois congruences mathématiques : 2 à la puissance ((N+3)/2) = 4 modulo (N) et 2 à la puissance (N-3) = (N+1)/4 modulo (N) et 2 à la puissance ((N-1)/2) = N-1 modulo (N), dont seule la troisième n'est pas vérifiée par (N). 10) Dispositif pour établir l'échec de la vérification de la primalité d'un nombre (N) selon les neuf revendications précédentes caractérisé en ce qu'il comporte les combinaisons de congruences mathématiques de celles-ci ne respectant pas la vérification ou l'absence de vérifications de ces congruences dans le sens souhaité par chacune des neuf revendications.