☎️ 👩‍🚀 😗 Algorithmes de recherche de nombres premiers ✳️ 🤦 🥤

«Le plus grand nombre premier est 2 ^32582657 -1 . Et j'affirme fièrement que je me suis souvenu de tous ses nombres ... sous forme binaire. "
Karl Pomerance

Un nombre naturel est appelé premier s'il n'a que deux diviseurs différents: un et lui-même. La tâche de trouver des nombres premiers hante les mathématiciens depuis très longtemps. Pendant longtemps, ce problème n'a eu aucune application pratique directe, mais tout a changé avec l'avènement de la cryptographie à clé publique. Cet article décrit plusieurs façons de rechercher des nombres premiers, à la fois d'intérêt purement académique et utilisés aujourd'hui en cryptographie.

Tamis d'Ératosthène

Tamis d'Eratosthène - un algorithme proposé par le mathématicien grec ancien Eratosthène. Cette méthode vous permet de trouver tous les nombres premiers inférieurs à un nombre donné n . L'essence de la méthode est la suivante. Prenez un ensemble de nombres de 2 à n . Biffez tous les nombres divisibles par 2, sauf 2. De l'ensemble (nous éliminons), nous passons au prochain nombre «non éliminé» - 3, encore une fois biffons tout ce qui est divisible par 3. Nous passons au prochain nombre restant - 5, et ainsi de suite jusqu'à ce que nous nous arrivons à n . Après avoir effectué les étapes ci-dessus, seuls les nombres premiers resteront dans la liste d'origine.

L'algorithme peut être légèrement optimisé. Étant donné que l'un des diviseurs du nombre composé n est obligatoire

l e q s l a n t s q r t n

$\ leqslant \ sqrt {n}$ , l'algorithme peut être arrêté après la suppression des nombres divisibles par

s q r t n

$\ sqrt {n}$ .

Illustration de l'algorithme de Wikipedia:

La complexité de l'algorithme est

O (n l o g n l o g)

$O (n \ log \ n log)$ en même temps, pour stocker des informations sur les numéros qui ont été barrés, il est nécessaire

O (n)

$O (n)$ mémoire.

Il existe un certain nombre d'optimisations pour réduire ces indicateurs. Une astuce appelée factorisation des roues consiste à inclure dans la liste initiale uniquement les nombres premiers avec les premiers nombres premiers (par exemple, moins de 30). En théorie, il est proposé de prendre les premiers simples jusqu'à environ

S q r t l o g n

$\ Sqrt {\ log n}$ . Cela réduit la complexité de l'algorithme

l o g l o g n

$\ log \ log n$ fois. De plus, la soi-disant segmentation est utilisée pour réduire la consommation de mémoire. L'ensemble initial de nombres est divisé en segments de taille

l e q s l a n t s q r t n

$\ leqslant \ sqrt {n}$ et pour chaque segment, le tamis d'Ératosthène est appliqué séparément. La consommation de mémoire est réduite à

O (s q r t n)

$O (\ sqrt {n})$ .

Tamis Atkin

Un meilleur algorithme pour trier les nombres composites a été proposé par Atkin et Bershtein et a été appelé Atkin's Sieve . Cette méthode est basée sur les trois propriétés suivantes des nombres premiers.

bien 1

Si n est un nombre positif qui n'est pas un multiple du carré d'un nombre premier et tel que

n e q u i v 1 (m o d 4)

$n \ equiv 1 (\ mod 4)$ . Le n - simple si et seulement si le nombre de racines de l'équation

4 x^{2} + y^{2} = n

$4x ^ 2 + y ^ 2 = n$ bizarre.

Propriété 2

Si n est un nombre positif qui n'est pas un multiple du carré d'un nombre premier et tel que

n e q u i v 1 (m o d 6)

$n \ equiv 1 (\ mod 6)$ . Alors n est premier si et seulement si le nombre de racines de l'équation

3 x^{2} + y^{2} = n

$3x ^ 2 + y ^ 2 = n$ impair.

établissement 3

Si n est un nombre positif qui n'est pas un multiple du carré d'un nombre premier et tel que

n e q u i v 11 (m o d 12)

$n \ equiv 11 (\ mod 12)$ . Alors n est premier si et seulement si le nombre de racines de l'équation

3 x^{2} - y^{2} = n

$3x ^ 2-y ^ 2 = n$ bizarre.

La preuve de ces propriétés est fournie dans cet article .

Au stade initial de l'algorithme, le tamis Atkin est un tableau A de taille n rempli de zéros. Pour déterminer les nombres premiers, tous

X, y < s q r t n

$X, y <\ sqrt n$ . Pour chacune de ces paires est calculé

$inline$ ,

3 x^{2} + y^{2}

$3x ^ 2 + y ^ 2$ ,

$inline$ et la valeur des éléments de réseau

A [4 x^{2} + y^{2}]

$A [4x ^ 2 + y ^ 2]$ ,

A [3 x^{2} + y^{2}]

$A [3x ^ 2 + y ^ 2]$ ,

A [3 x^{2} - y^{2}]

$A [3x ^ 2-y ^ 2]$ augmente d'une unité. À la fin de l'algorithme, les indices de tous les éléments du tableau qui ont des valeurs impaires sont soit des nombres premiers, soit des carrés d'un nombre premier. À la dernière étape de l'algorithme, les carrés des nombres restants dans l'ensemble sont barrés.

De la description de l'algorithme, il en résulte que la complexité de calcul du tamis de Atkin et jusqu'à utilisation de la mémoire

O (n)

$O (n)$ . Lors de l'utilisation de la factorisation et de la segmentation des roues, l'estimation de la complexité de l'algorithme est réduite à

O (n / l o g l o g n)

$O (n / \ log \ log n)$ , et la consommation de mémoire jusqu'à

O (s q r t n)

$O (\ sqrt {n})$ .

Chiffres de Mersenne et test de Luke-Lemer

Bien sûr, avec de tels indicateurs de complexité, même le tamis optimisé Atkin ne peut pas être utilisé pour rechercher de véritables nombres premiers. Heureusement, il existe des tests rapides pour vérifier si un nombre donné est premier. Contrairement aux algorithmes tamis, ces tests ne sont pas conçus pour trouver tous les nombres premiers, ils ne sont en mesure de dire avec une certaine probabilité, si un certain nombre est premier.

L'une de ces méthodes de test est le test de Luc-Lemer . Il s'agit d'un test de simplicité déterministe et inconditionnel. Cela signifie que la réussite du test garantit la simplicité du numéro. Malheureusement, le test est conçu pour un type particulier de chiffres

$inline$ où p est un nombre naturel. Ces chiffres sont appelés nombres de Mersenne.Le test de Luke-Lemer affirme que le nombre de Mersenne

M_{p} = 2^{p} - 1

$M_p = 2 ^ p-1$ premier si et seulement si p est premier et

$ M_

$$ M_$ divise

(p - 1)

$(p-1)$ e terme de la séquence

S_{k}

$S_k$ définir récursivement:

S_{1} = 4, S_{k} = S_{k - 1}^{2} - 2

$S_1 = 4, S_k = S_ {k-1} ^ 2-2$ pour

k > 1

$k> 1$ .

Pour le nombre

M_{p}

$M_p$ p bits de long, la complexité de calcul de l'algorithme est

d i s p l a y s t y l e O (p^{3})

${\ displaystyle O (p ^ {3})}$ .

En raison de la simplicité et le déterminisme du test, le plus grand nombres premiers connus - le nombre de Mersenne. Le plus grand nombre premier connu aujourd'hui est

$2 $ ^ {82 589 933} -1 $$ , sa notation décimale se compose de 24 862 048 chiffres. Vous pouvez admirer cette beauté ici .

Théorème de Fermat et test de Miller-Rabin

Peu de nombres premiers de Mersenne sont connus, donc la cryptographie à clé publique nécessite une manière différente de rechercher des nombres premiers. L'une de ces méthodes est le test de simplicité de Fermat . Il est basé sur le petit théorème de Fermat, qui déclare que si n est un nombre premier, alors pour tout a qui n'est pas divisible par n , l'égalité

a^{n - 1} e q u i v 1 p m o d n

$a ^ {n-1} \ equiv 1 {\ pmod {n}}$ . La preuve du théorème peut être trouvée sur Wikipedia .

simplicité d' essai agricole - test de probabilité qui est plusieurs valeurs d' une itération, si au moins l'un d'eux l'inégalité

a^{n - 1} n o t e q u i v 1 p m o d n

$a ^ {n-1} \ not \ equiv 1 \ pmod n$ , Le nombre entier n - le composite. Sinon, n est probablement premier. Plus le nombre de valeurs utilisées dans le test est élevé, plus la probabilité que n soit premier est élevée.

Malheureusement, il existe des nombres composites n pour lesquels la comparaison

a^{n - 1} e q u i v 1 p m o d n

$a ^ {n-1} \ equiv 1 {\ pmod {n}}$ est valable pour tous mutuellement premiers avec n . Ces numéros sont appelés numéros Carmichael . Les nombres composés qui réussissent le test de Fermat sont appelés pseudo-simples Fermat. Le nombre de Fermat pseudo-simple est infini, donc le test de Fermat n'est pas le moyen le plus fiable pour déterminer les nombres premiers.

Test de Miller-Rabin

Des résultats plus fiables peuvent être obtenus en combinant le petit théorème de Fermat et le fait que pour un p premier, il n'y a pas d'autre racine de l'équation

x^{2} e q u i v 1 p m o d p

$x ^ 2 \ equiv 1 \ pmod p$ Mais 1 et -1. Le test de Miller-Rabin énumère plusieurs valeurs de a et vérifie que les conditions suivantes sont remplies.

Soit p un nombre premier et

P - 1 = 2^{s} d

$P-1 = 2 ^ sd$ , alors pour toute une au moins une des conditions est vraie:

$a ^ {d} \ equiv \ pm1 {\ pmod {p}}$
Il y a un entier r <s tel que $a ^ {2 ^ {r} d} \ equiv -1 {\ pmod {p}}$

Par le théorème de Fermat

a^{p - 1} e q u i v 1 p m o d p

$a ^ {p-1} \ equiv1 \ pmod p$ , et depuis

p - 1 = 2^{s} d

$p-1 = 2 ^ sd$ de la propriété des racines de l'équation

X^{2} e q u i v 1 p m o d p

$X ^ 2 \ equiv 1 \ pmod p$ il s'ensuit que si nous trouvons un tel que l'une des conditions n'est pas remplie, alors p est un nombre composite. Si l' une des conditions est remplie, le nombre d'un témoin appelé la simplicité du nombre n de Miller et entier auto n - le plus facile probablement.

Plus il y a de témoins de la simplicité, plus la probabilité que n soit premier est élevée. Selon le théorème de Rabin, la probabilité qu'un nombre choisi au hasard a soit témoin de la simplicité du nombre composite est approximativement

1 / 4

$1/4$ .

Par conséquent, si nous vérifions k nombres aléatoires a , la probabilité de prendre le nombre composite comme premier

e n v i r o n (1 / 4)^{k}

$\ environ (1/4) ^ k$ .

La complexité de l'algorithme

O (k l o g^{3} p)

$O (k \ log ^ 3p)$ où k est le nombre de contrôles.

En raison de sa vitesse et de sa grande précision, le test de Miller-Rabin est largement utilisé dans la recherche de nombres premiers. De nombreuses bibliothèques cryptographiques modernes lors de la vérification grand nombre de simplicité utilisent uniquement ce test et, comme le montre Martin Albrecht dans son travail , cela ne suffit pas toujours.

Il a pu générer de tels nombres composites qui ont réussi le test de simplicité dans les bibliothèques OpenSSL, CryptLib, JavaScript Big Number et bien d'autres.

Test Luc et essai Baillie-PSW

Pour éviter les vulnérabilités liées aux situations où un nombre composite généré par un attaquant est présenté comme premier, Martin Albrecht suggère d'utiliser le test Baillie - PSW . Malgré le fait que le test Baillie - PSW soit probabiliste, à ce jour, aucun nombre de composés n'a réussi à réussir ce test. Pour avoir trouvé un tel nombre en 1980, les auteurs de l'algorithme ont promis une récompense de 30 $. Le prix n'a pas encore été réclamé.

Un certain nombre de chercheurs ont vérifié tous les chiffres jusqu'à

2^{64}

$2 ^ {64}$ et nous n'avons trouvé aucun numéro composite, le dernier test Baillie-PSW. Par conséquent, pour les nombres moins

$2 $ ^ {64} $$ le test est déterminé.L'essence du test est de vérifier de manière cohérente le nombre lors d'un temps d'arrêt par deux méthodes différentes. L'une de ces méthodes déjà décrites ci-dessus un test de Miller-Rabin. Le second est le test de Luke pour une forte pseudo-simplicité .Test Luke sur une forte pseudosimplicityLes séquences de Luke sont des paires de séquences de récurrence

\ {U_ {n} (P, Q) \}, \ {V_ {n} (P, Q) \}

$\ {U_ {n} (P, Q) \}, \ {V_ {n} (P, Q) \}$ , Décrite par l'expression:

{\ Displaystyle U_ {0} (P, Q) = 0, \ quad U_ {1} (P, Q) = 1, \ quad U_ {n + 2} (P, Q) = P \ cdot U_ {n 1} (P, Q) -Q \ cdot U_ {n} (P, Q), \ n \ geq $ 0

${\ Displaystyle U_ {0} (P, Q) = 0, \ quad U_ {1} (P, Q) = 1, \ quad U_ {n + 2} (P, Q) = P \ cdot U_ {n 1} (P, Q) -Q \ cdot U_ {n} (P, Q), \ n \ geq $ 0$

{\ Displaystyle V_ {0} (P, Q) = 2, \ quad V_ {1} (P, Q) = P, \ quad V_ {n + 2} (P, Q) = P \ cdot V_ {n 1} (P, Q) -Q \ cdot V_ {n} (P, Q), \ n \ geq $ 0

${\ Displaystyle V_ {0} (P, Q) = 2, \ quad V_ {1} (P, Q) = P, \ quad V_ {n + 2} (P, Q) = P \ cdot V_ {n 1} (P, Q) -Q \ cdot V_ {n} (P, Q), \ n \ geq $ 0$

Soit

U_{n} (P, Q)

$U_n (P, Q)$ et

V_{n} (P, Q)

$V_n (P, Q)$ - séquence Luc, où les nombres entiers p et q satisfont à la condition

{\ Displaystyle D = P ^ {2} -4Q \ neq $ 0

${\ Displaystyle D = P ^ {2} -4Q \ neq $ 0$

On calcule le symbole de Jacobi :

l e f t (f r a c D p r i g h t) = v a r e p s i l o n

$\ left ({\ frac {D} {p}} \ right) = \ varepsilon$ .

Trouver de tels r, s pour lesquels l'égalité

n - ε = 2^{r} s

$n-ε = 2 ^ rs$

Pour prime n , l'une des conditions suivantes est remplie:

n divise $U_s$
n divise $V_ {2 ^ js}$ pour certains j <r

Sinon, n est composé.

La probabilité qu'un nombre composite n réussisse le test de Luc pour une paire donnée de paramètres P, Q ne dépasse pas 4/15. Par conséquent, après avoir appliqué le test k fois, cette probabilité est

(4 / 15)^{k}

$(4/15) ^ k$ .

Les tests de Miller-Rabin et Luke produisent des ensembles disjoints de nombres pseudo-simples, respectivement, si le nombre p a passé les deux tests, c'est simple. Il était sur cette propriété test basé Baillie-PSW.

Conclusion

En fonction de la tâche, vous pouvez utiliser différents nombres premiers méthodes de recherche. Par exemple, lors de la recherche de grands nombres premiers de Mersenne, tout d'abord, en utilisant le tamis d'Eratosthène ou d'Atkin, une liste de nombres premiers est déterminée jusqu'à une certaine limite, supposons

$inline$ . Ensuite, pour chaque nombre p de la liste, en utilisant le test de Luc-Lemer, il est vérifié pour la simplicité

M_{p} = 2^{p} - 1

$M_p = 2 ^ p-1$ .

Pour générer un grand nombre premier à des fins cryptographiques, un nombre aléatoire a est sélectionné et vérifié par le test de Miller-Rabin ou le plus fiable Baillie - PSW. Selon le théorème des nombres premiers , un nombre choisi au hasard de 1 à n chance d'être à peu près égale au simple

F r a c 1 n D a n s

${\ Frac {1} {\ n}} Dans$ . Par conséquent, pour trouver un nombre premier de 1024 bits, il suffit de trier environ mille options.

Sources PS

L'implémentation de tous les algorithmes décrits sur Go peut être visualisée sur GitHub .

Algorithmes de recherche de nombres premiers