Prime Generation

Dans la continuité du sujet abordé dans cette série d'articles , nous parlerons aujourd'hui de la génération des nombres premiers. La génération est probabiliste et garantie. Ainsi, notre cas est avec une garantie qui vous permet d'utiliser les numéros obtenus dans les applications liées à la cryptographie, ce qui garantit, par exemple, la sécurité de la gestion de votre argent via des applications bancaires. De plus, vous verrez comment il est garanti de recevoir des nombres premiers de taille suffisante pour la cryptographie, ainsi que les problèmes qui peuvent survenir si vous négligez les garanties.


Le schéma général de sécurité pour l'échange de données est basé sur la complexité de la factorisation d'un grand nombre composite. De plus, s'il existe de nombreux facteurs, ils seront faibles, ce qui simplifie considérablement le piratage du système de sécurité. Par conséquent, un grand nombre composite est obtenu en multipliant deux nombres premiers d'une certaine taille. Mais ici, un problème est évident - comment choisir un nombre premier suffisamment grand?

Déterminez d'abord la taille. Dans la cryptographie moderne, l'ordre du nombre composite est déterminé par la formule $$$2 ^ {2048}$ c'est-à-dire que l'ordre réel est 2048 en notation binaire. Et les diviseurs de ce nombre composite sont de l'ordre de 1024, c'est-à-dire quelque part autour des valeurs $$$2 ^ {1024}$ . Pourquoi 1024? Parce qu'il y a dix ans, un facteur de l'ordre de 768 était factorisé, et aujourd'hui il est très probable que les nombres composés de l'ordre de 1024 soient décomposés. Il a donc été décidé pour la fiabilité de doubler l'ordre à la fois, c'est-à-dire jusqu'en 2048. Eh bien, partir de cet ordre est facile à déterminer ordre des facteurs requis.

Mais que se passe-t-il si l'ordre des facteurs est bien inférieur à 1024? Ensuite, dans un temps acceptable, vous pouvez décomposer un nombre composite, même s'il est de l'ordre de 2048. Cela signifie qu'il faut garantir que les facteurs choisis par nous ont un ordre proche de 1024 et sont simples, c'est-à-dire qu'ils ne peuvent pas être factorisés. Mais ici, le choix lui-même est effectué selon un schéma probabiliste, ce qui ne fait que conduire à des problèmes potentiels.

La probabilité de la simplicité d'un nombre est vérifiée sur la base de l'hypothèse que le nombre est "très probablement" premier si sa période (qui est décrite ici ) est un diviseur du nombre lui-même, moins un ( $$$N-1$ ) Sous la forme d'une formule, cela ressemble à ceci:

$$

$$a ^ p \ pmod N = 1$$

$$

$$N-1 \ pmod p = 0$$

Ici $$$N$ - numéro enquêté, $$$a$ - valeur de $$$2$ avant $$$N-2$ (il détermine la base du système numérique dans lequel la période est calculée), $$$p$ - période du numéro examiné. Fonctionnement $$$mod$ ici signifie prendre le reste de la division du premier opérande par le second.

Les contrôles existants reposent sur une telle approche, car pour de grands nombres, la détermination inconditionnelle de la simplicité par des tests connus prend beaucoup de temps. Mais le inconvénient d'une telle vérification est évident - parfois, vous pouvez obtenir un nombre composite, au lieu d'un simple. De plus, personne ne sait quels diviseurs feront partie d'un tel nombre. Plus précisément, un attaquant pourra le découvrir en appliquant les méthodes de factorisation bien connues, qui commencent à fonctionner dans un temps acceptable si les facteurs sont de l'ordre de moins de quelques centaines de bits.

Quelle est la fréquence des erreurs de simplicité probabiliste? Assez rarement. Il y a une erreur pour plusieurs dizaines de milliers de simples, et parfois deux, mais rien ne nous garantit de trois. De plus, cela dépend beaucoup du test utilisé. Ainsi, par exemple, dans la bibliothèque de langage Java standard de la classe BigInteger, une vérification est implémentée qui permet une absence de 2 à 3 fois pour mille simples. Autrement dit, vous ne devriez pas penser que s'il y a théoriquement très peu d'erreurs, alors dans la pratique, tout sera dans le chocolat.

Comment est-ce dangereux? Cela ne semble pas aussi effrayant que certains peuvent le dire, car si un site qui ferme la navigation sur ses pages avec le protocole https reçoit une clé facilement calculée, alors quel sera le problème? Eh bien, les pirates découvriront quelles nouvelles vous lisez sur ce site, et quel est le point? Mais en fait, le cryptage ne se fait pas uniquement lors de la navigation sur le Web. Une situation plus désagréable se produira si les pirates découvrent la clé de votre service bancaire préféré pour gérer à distance votre argent. Bien que, encore une fois, il semble que pour ouvrir sûrement l'échange avec la banque (et si la banque utilise un contrôle de simplicité faible), le pirate devra attendre environ 500 ans jusqu'à ce que la probabilité d'émettre une clé facilement calculable soit enfin réalisée, car les clés ont généralement une période de validité de 1 an et par conséquent, pour garantir le piratage, vous devez attendre que 500 numéros d'une nouvelle clé soient exécutés. Il semble que tout soit logique, mais il y a un autre «mais» - il y a beaucoup plus de banques que 500 dans le monde. Par conséquent, en ce moment, peut-être dans votre banque préférée, les pirates peuvent avoir accès à votre propre argent.

As-tu peur? Sûrement pas, car nous sommes tous très courageux, jusqu'à ce que le coq rôti picote. Mais il y a encore quelque chose à craindre. Bien que la probabilité d'une attaque réussie par des pirates informatiques précisément sur votre banque ne soit pas si élevée, mais néanmoins, si elle est réalisée, votre argent ne sera probablement pas trouvé. Pourquoi? C'est très simple - la première hypothèse standard du service de sécurité de la banque est de blâmer quelqu'un avec les droits d'accès appropriés. Pas un pirate informatique, la probabilité d'ingérence qu'ils considèrent également comme minime, à savoir quelqu'un à eux. Par conséquent, un pirate pourrait bien rester impuni.

Comment résoudre ce problème? Vous devez apprendre à obtenir des nombres premiers garantis. Mais comment garantir leur simplicité? Il existe quatre méthodes pour cela.

La première méthode casse avec un minimum de restrictions. Il s'agit généralement d'une variante du tamis amélioré d'Eratosthène. La méthode est fiable et garantie, mais limitée à des commandes très modestes (moins d'une centaine). Par conséquent, cette méthode n'est pas applicable en cryptographie.

La deuxième méthode est l'énumération avec des restrictions plus strictes. Donc, si la période d'un nombre est égale au nombre lui-même, moins un, alors le nombre est garanti premier. La formule ici est - $$$N-1 = p$ . Mais pour déterminer l'égalité de la période de la différence entre le nombre et l'unité, on utilise des méthodes très lourdes qui ne fonctionnent pas pour toutes les classes de nombres. Par conséquent, leur utilisation en cryptographie repose soit sur le nombre limité de nombres de classes spécifiques, soit lors de la vérification, si nous augmentons la taille du nombre. Et d'ailleurs, même les nombres d'une certaine classe ne garantissent rien par eux-mêmes, ce qui signifie la nécessité de trier de nombreux nombres de candidats. Ici, par exemple, les nombres de Mersenne, pour lesquels il existe un test inconditionnel de simplicité, ont déjà été triés et ont découvert qu'ils sont pratiquement absents dans la gamme utilisée en cryptographie. Voici leur liste complète des commandes fermées - 1279, 2203, 2281, 3217. Comme vous pouvez le voir, de 1024 à 2048, il n'y a qu'un seul numéro approprié. Mais même si nous prenons le reste, leur nombre nous indique très clairement - ça ne vaut pas le coup! Encore une fois, nous n'avons pas eu de chance avec la méthode de vérification.

La troisième méthode est probabiliste. C'est elle qui est utilisée aujourd'hui, y compris dans votre banque préférée. Comment fonctionne-t-il? Très simple - le reste de la division d'un nombre arbitraire en une puissance est vérifié $$$N-1$ sur $$$N$ si le reste est un, il est probable que le nombre soit premier. Et ici, le mot «probablement» est le plus désagréable ici. Bien que les méthodes probabilistes de vérification de la simplicité contiennent également des améliorations supplémentaires, néanmoins, comme indiqué ci-dessus, la bibliothèque Java standard se trompe souvent.

Et enfin, la quatrième méthode. Il ne fonctionne pas aussi vite que les tests probabilistes (bien que quelque chose puisse être optimisé ici aussi), mais il donne des nombres premiers garantis, et même avec une période facilement définissable. À quoi sert une période de pointe, demandez-vous? Par exemple, pour générer une séquence pseudo-aléatoire ou de chiffrement. Plus précisément, connaissant la période, nous savons exactement combien de nombres seront dans la séquence, ce qui permet de planifier facilement combien de temps nous pouvons utiliser le générateur de séquence en fonction de ce nombre. Certes, cela s'applique déjà au chiffrement symétrique, mais il peut également être utile dans un certain nombre de cas. Ensuite, nous considérerons une théorie qui garantit la simplicité de la vérification des nombres candidats.

Contexte théorique

Pour comprendre comment générer des nombres premiers garantis, vous devez plonger dans un peu de mathématiques. Mais ne vous inquiétez pas, les mathématiques sont ici au cinquième niveau.

Pour être complet, il est recommandé de regarder ici pour plus de détails sur ce qu'est une période et une série de résidus. Eh bien, disons brièvement qu'un certain nombre de résidus se forment en divisant le «coin» (une méthode connue de tout étudiant) de l'unité par le nombre choisi pour l'étude. Dans le même temps, à chaque étape, une différence apparaît entre le nombre supérieur, avec un zéro ajouté, et le produit du nombre étudié par une valeur de 0 à 9 (pour le système de nombres décimaux) - c'est le reste. Mais il y a de nombreuses étapes dans la division par le «coin», donc il y a aussi beaucoup de résidus, et ensemble ils forment une série de résidus dans laquelle le même ensemble de nombres est répété périodiquement un nombre infini de fois. Un signe du début d'un nouveau cycle est un reste égal à un. La quantité de résidu entre les unités est la longueur de la période (ou cycle). En fait, c'est tout, mais il vaut également la peine de comprendre qu'une telle méthode de construction d'une série de soldes peut être appliquée en utilisant n'importe quel système numérique, et en particulier, le système avec la base 2 (et non 10, comme c'est la coutume à l'école) sera le plus souvent utilisé. Lorsque vous utilisez d'autres systèmes numériques, toutes les règles sont conservées, mais le nombre de variantes de produit à chaque étape sera différent, égal à b (à partir de la base), c'est-à-dire la base du système numérique.

Ainsi, d'après ce qui a été montré précédemment, nous savons que les nombres composites donnent toujours des périodes relativement courtes qui n'incluent pas un certain nombre de valeurs «interdites». Connaissant la factorisation d'un nombre composé, il est facile de calculer combien de valeurs doivent être absentes dans un certain nombre de résidus qui forment la période d'un nombre donné. Une série de résidus ne contiendra pas de facteurs et tous les nombres qui sont des multiples de ces facteurs si la série elle-même est construite sur la base d'un système numérique qui n'est pas un multiple de l'un des diviseurs (c'est-à-dire que la base n'est pas divisée par les diviseurs du nombre). Par exemple, s'il n'y a que deux facteurs, le nombre de résidus multiples est déterminé par la formule $$$m = a + b-2$ où $$$m$ - le nombre de résidus multiples, $$$a$ et $$$b$ Ce sont les facteurs qui forment notre nombre composite. Connaissant le nombre de résidus «interdits», il est facile de calculer qu'une série de résidus plus longue que la moitié de la valeur $$$N-1$ aura une longueur égale à $$$L = N-1- (a + b-2) = N-a-b + 1$ . Autrement dit, une telle série sera sur $$$a + b-2$ plus courte que la série qui se révélerait si le nombre donné était premier. Cela explique pourquoi tous les nombres avec une période égale à la période complète (c.-à-d. $$$N-1$ ), s'avèrent simples - si au moins un élément (qui est «interdit») était exclu de la séquence des résidus, alors la période deviendrait moins longue $$$N-1$ . Du fait de l'existence d'une telle régularité, nous observons l'opérabilité de tous ces tests de probabilité, qui vérifient aujourd'hui la simplicité d'un nombre. Ces tests calculent des valeurs dans une série de soldes par position. $$$N-1$ ou $$$(N-1) / 2$ , et si les valeurs sont égales $$$1$ ou $$$N-1$ , il est fort probable que le nombre soit premier. Pourquoi seulement avec une forte probabilité et non garanti? Parce que les tests probabilistes de période ne sont pas calculés, mais entre les positions $$$N-1$ et $$$(N-1) / 2$ il peut y avoir plus d'unités, ce qui signifie l'inégalité de la période à la valeur $$$N-1$ mais si la période n'est pas égale $$$N-1$ , alors le nombre peut être composite. De plus, le manque d'égalité en soi n'est pas critique, une autre chose est importante - les nombres pseudo-simples peuvent donner un tel arrangement d'unités. Parmi les chiffres vérifiés par un tel test, vous pouvez trouver des pseudo-simples qui sont composites et qui aident les pirates qui volent votre argent. Après tout, quels sont les diviseurs de ces nombres composites? Ils peuvent être suffisamment petits pour qu'un attaquant ouvre facilement un échange de données cryptées.

Rappelez-vous maintenant pourquoi les pseudo-nombres premiers peuvent apparaître. Ces nombres ont de courtes périodes qui se répètent plusieurs fois au cours de la période complète. $$$N-1$ par conséquent, ils peuvent parfois «s'intégrer» et s'intégrer un nombre entier de fois dans une période complète. Ainsi, par exemple, le nombre 25 a une période de 4 pour le système numérique avec la base 7. $$$N-1$ pour 25 est 24, essayez de diviser: 24/4 = 6. Autrement dit, cette période est présentée un nombre entier de fois dans une période complète. Ce fait peut être vérifié par la formule ci-dessus pour raccourcir la période, mais en tenant compte du fait que a et b sont les mêmes dans ce cas. La période maximale possible sera de 24-4 = 20, ici 24 est le nombre total de résidus, 4 est le nombre de résidus qui sont des multiples de 5. Mais la période n'est pas toujours le maximum, et toutes les autres options peuvent être obtenues en divisant complètement la période maximale. 20 est divisé par 2,4,5,10, et juste en divisant 20 par un nombre de la liste ci-dessus, nous obtenons une période de 4, ce qui nous donne à la fin de la période complète $$$N-1$ unité. Et lors de la vérification de la simplicité, seules les valeurs à la position sont vérifiées $$$N-1$ , c'est-à-dire la dernière valeur de la période complète. Et pour 25, il est égal à 1, ce qui est un signe de la simplicité du nombre. Bien qu’en fait un signe clair de simplicité, c’est quand, pour toutes les bases des systèmes numériques, moins $$$N$ , la dernière valeur de la période complète est égale à un. Mais il n'y a aucun moyen de vérifier tous les systèmes numériques pour les grands nombres, donc des nombres pseudo-simples apparaissent qui sont parfois utilisés même en cryptographie, ce qui augmente la vulnérabilité de nos finances.

Comment éliminer l'influence des pseudo-nombres premiers? En principe, c'est simple - vous pouvez vérifier les périodes pour tous les systèmes numériques, mais pour cette opération pour les grands nombres, il n'y aura pas assez de temps. Par conséquent, nous irons dans l'autre sens. Et le chemin est également simple (au sens littéral - il utilise d'autres nombres premiers). Nous avons vu que de courtes périodes peuvent s'adapter à une période complète un nombre entier de fois, et cela nous donne des nombres pseudo-simples. Mais qu'est-ce qui nous empêche de prendre et d'annuler ces lundis? Oui, en général, rien n'empêche.

Pour de courtes périodes, la période complète ( $$$N-1$ ) doit être divisé en plusieurs diviseurs. Donc pour le nombre 25, la période complète 24 est divisée en 2, 3, 4, 6, 8, 12. Il y a tellement de possibilités de pénétrer dans le territoire protégé des nombres pseudo-simples. Nous avons donc juste besoin de prendre un prime comme une période complète, car il ne se divise en rien du tout et nous sauve donc automatiquement de l'élément ennemi. Certes, il y a un «mais» - nous avons besoin de nombres premiers, et ils sont connus pour être impairs (sauf pour une exception - 2), ce qui signifie que si $$$N-1$ simple alors lui-même $$$N$ cela ne peut plus être simple. Par conséquent, nous devrons admettre la possibilité de l'apparition de périodes incomplètes. Pourquoi est-ce mauvais? Comme nous l'avons vu plus haut, la période complète garantit la simplicité du nombre, mais nous n'avons pas encore prouvé la période incomplète. Nous devons donc prouver ce moment.

La preuve est assez simple - pour le composé $$$N$ durée $$$N-1$ deux fois, obtenu dans un système numérique qui n'est pas un multiple des diviseurs de N, n'a que deux rangées de résidus, et aucun d'entre eux ne doit contenir des nombres qui sont des multiples des diviseurs de N $$$N$ (Numéros "interdits"). Si au moins un élément est exclu d'une rangée de résidus, alors le second diminue automatiquement du même montant (après tout, une rangée est égale à une autre multipliée par un nombre qui n'est pas dans le premier). Donc, s'il y a des diviseurs dans le nombre $$$N$ , nous obtenons une durée totale plus courte de deux périodes avec tous les soldes «autorisés» que la valeur de la période complète et ainsi déplaçons l'unité de sa place à la fin de la période complète, garantissant ainsi l'absence de pseudo-simplicité. Mais le nombre de restes de diviseurs multiples peut-il être tel qu'il donne exactement la moitié ou le tiers de la période complète? En effet, nous recevrions alors, par exemple, les deux tiers des soldes «autorisés» (deux rangées) et un tiers des soldes «interdits», et au total - la période complète. Mais pour obtenir un tiers, nous devons garantir la divisibilité de toute la période ( $$$N-1$ ) par 3, que l'on peut assez facilement exclure - prendre un nombre premier, le multiplier par deux et en ajouter un au résultat - le tour est joué, nous avons la garantie d'exclure la pseudo-simplicité. Avec lui, le nombre de diviseurs divisibles par les diviseurs ne peut pas être égal au tiers de la période complète, car il ne peut pas diviser par trois périodes complètes. Il reste l'option avec la moitié du reste qui est un multiple des diviseurs $$$N$ . Cette option est éliminée un peu plus difficile, il y aura donc une légère digression ci-dessous.

Calcul de la période ou de tous les nombres - Les enfants de Mersenne

La période de n'importe quel nombre peut être calculée. Dans le cas le plus simple, le calcul se fait en divisant simplement le coin $$ jusqu'à ce que nous rencontrions un reste égal à un (dans le système numérique, pas un multiple des diviseurs $$$N$ ) Mais pour un grand nombre, c'est irréaliste. Par conséquent, il est nécessaire de dériver une formule pour calculer la période. Et une telle formule existe, mais pas dans sa forme idéale, quand nous avons un nombre à l'entrée et une période à la sortie. La formule est:

$$

$$N = \ frac {b ^ {m + n + 1} -1} {b ^ n + k}$$

Ici $$$N$ - numéro enquêté, $$$b$ - la base du système de numérotation utilisé (base), $$$m$ - degré maximum $$$b$ à laquelle le résultat de l'exponentiation est moins $$$N$ (en d'autres termes, l'indice de niveau supérieur $$$N$ dans le système numérique $$$b$ ), $$$n$ - distance de gauche à droite dans une série de résidus de l'indice $$$m + 1$ (égal au nombre de bits dans $$$N$ ) à un, $$$k$ Est un certain coefficient entier.

Sortie de formule

Par la définition de la formule, il est clair que (1) $$$b ^ {m + 1} -N = x$ c'est-à-dire le premier degré $$$b$ qui est plus grand $$$N$ , vous permet de soustraire $$$N$ et obtenez une différence dans le formulaire $$$x$ . Il résulte également de la définition que (2) $$$x * b ^ n-k * N = 1$ ici $$k est un coefficient entier. Si vous multipliez(1)par$k$$$b n et remplacer$b^n$$$x ∗ b n à sa valeur de(2), qui est égale à$x*b^n$$$k N + 1 , alors on obtient$kN+1$$$$b^{m+n+1}=N*b^n+kN+1=N*(b^n+k)+1 => N=\frac{b^{m+n+1}-1}{b^n+k}$ .

Propriétés utiles

Comme nous pouvons le voir, en utilisant cette formule, vous pouvez obtenir des nombres avec une période connue. Certes, il y a une difficulté - vous devez sélectionner un coefficient$$k , qui pour de grands nombres redevient quelque chose d'inatteignable. Mais la formule nous donne autre chose - nous voyons clairement comment tous les nombres sont formés. Oui, absolument tous les entiers positifs peuvent être obtenus par cette formule, car tous les nombres ont une période. Et fait intéressant, tous les nombres sont obtenus en divisant le nombre de Mersenne par l'un de ses diviseurs. Rappelons qu'un nombre de Mersenne est un nombre égal à$k$$$$2^n-1$ .Dans la formule du numérateur, nous voyons une généralisation pour les nombres de Mersenne avec n'importe quelle base (y compris 2, bien sûr). Et si nous nous intéressons aux nombres premiers, nous n'aurons pas besoin d'autres bases que 2.

Sachant que nous partageons Mersenne premier, il serait utile de pouvoir calculer la période des numéros est dans le cas de la division des nombres de Mersenne (souvenez - vous de la période de concept élargi ici ). Mais ce qui est très remarquable, c'est que la formule de calcul de la période de Mersen coïncide avec la formule de calcul d'une période du type$$$1/N$ . Eh bien, pour dériver la formule de division des nombres de Mersenne, le même principe est utilisé que pour dériver la formule de division $$1 / N , à l'exception de la formule de calcul de la valeur dans une série de résidus avec indice$1/N$$$n qui ressemble à ceci -$n$$$b n + 1 - 1b - 1 , et pour les nombres binaires, nous obtenons$\frac{b^{n+1}-1}{b-1}$$$$2^{n+1}1$ .

Nous avons maintenant toutes les cartes en main et nous pouvons commencer le jeu en ouvrant les archers pseudo-simples dans les rangs des premiers.

Comme nous le savons à partir de la série précédente, lorsqu'elle est divisible, toute la période de Mersen d'un nombre doit correspondre au nombre de chiffres du nombre de Mersenne un nombre entier de fois. Par conséquent, dans la formule ci-dessus, une solution en nombres entiers n'est possible que si le dénominateur a une période soit égale au numérateur soit plusieurs fois plus petite. Mais une période beaucoup plus courte nous donnera, y compris les diviseurs du nombre lui-même$$N , car si$N$$$N divise le nombre de Mersenne, puis ses diviseurs divisent également le nombre de Mersenne. Et c'est un point très important, car il en résulte que les longueurs des périodes des diviseurs N divisent la longueur de la période$N$$$N complètement. Autrement dit, si nous prenons$N$$$N est tel que sa période est égale à la période du numérateur, alors tous les diviseurs$N$$$N sera en même temps des diviseurs du nombre de Mersenne, et doit donc s'insérer dans la période et$N$$$N et Mersenne numérote un nombre entier de fois.$N$

Encore environ la moitié de la période

Rappelons maintenant que nous nous sommes arrêtés sur la recherche d'un moyen de prouver que nous pouvons exclure le cas où la moitié de la longueur d'une série de nombres résiduels est un multiple de ses diviseurs. Nous voulions prouver cela pour éliminer les pseudo-nombres premiers lors du choix d'un nombre premier comme base pour construire la période du prochain nombre premier. Alors maintenant, nous savons que si le nombre construit a des diviseurs, alors leurs périodes divisent toujours complètement la période du nombre construit. Ensuite, il nous reste à vérifier quels diviseurs peuvent correspondre aux restrictions précédemment données sur le nombre construit. Et de telles restrictions - sa période est divisée uniquement en$$2 et plus$2$$$$(N-1)/2$ . Par conséquent, seuls les nombres avec des points peuvent être des diviseurs $$$2$ et $$$(N-1)/2$ . Période $$2 a un nombre$2$$$2 , aucun autre nombre d'une telle période n'a plus. Période$2$$$2 ne correspond pas à un nombre entier de fois$2$$$( N - 1 ) / 2 , car$(N-1)/2$$$( N - 1 ) / 2 est premier, donc la divisibilité en trois est exclue pour une telle période. Il n'y a donc qu'une seule possibilité - les séparateurs ont une période$(N-1)/2$$$$(N-1)/2$ . Mais le nombre ne peut pas être inférieur ou égal à sa période, donc la valeur minimale pour les diviseurs est $$$(N-1)/2+1$ . Si nous multiplions deux diviseurs minimaux, nous obtenons - $$( N - 1 ) 2 / 4 + ( N - 1 ) + 1 = ( N 2 - 2 N + 1 + 4 N ) / 4 = ( N 2 + 2 N + 1 ) / 4 , cette valeurdoit pas être plus$(N-1)^2/4+(N-1)+1=(N^2-2N+1+4N)/4=(N^2+2N+1)/4$$$N , parce que nous parlons de diviseurs$N$$$$N$ . Ensuite, nous obtenons l'inégalité $$$(N^2+2N+1)/4\leq N => N^2-2N+1\leq 0$ . Cette inégalité peut être négative ou égale à zéro uniquement pour $$N = 1 , par conséquent, pour tous les nombres ainsi construits, la pseudo-simplicité est exclue si le nombre résultant est supérieur à$N=1$$$$1$ . Eh bien, pour de plus petits nombres, nous pouvons tester la simplicité même dans l'esprit.

Maintenant, il y a deux options - le nouveau nombre est un nombre premier, ce dont nous avions besoin, ou c'est un nombre composite, puis sa période ne correspond pas à un nombre entier de fois dans une période complète, et donc ce nombre peut être facilement vérifié pour plus de simplicité en calculant la dernière valeur dans une série complète de résidus. Autrement dit, le nombre construit peut être facilement vérifié avec des tests de simplicité probabiliste standard, et ce qui est important, le résultat du test ne sera pas probabiliste, mais garanti. Donc, au final, nous nous sommes débarrassés de la malédiction de la pseudo-simplicité, qui met la pression sur tous les tests probabilistes.

Mais bien sûr, la vie serait chérie si tous les problèmes étaient résolus si simplement. En éliminant la pseudo-simplicité, nous n'avons pas exclu les numéros qui ne sont cachés à personne et qui ne sont masqués sous rien. Et avec eux, il y a un problème de plus - pour le moment, nous ne pouvons vérifier un terme arbitraire dans la séquence de résidus qu'en élevant à une puissance et en prenant ensuite le reste. Mais cette méthode est très lente. Plus précisément, il est assez rapide pour les nombres utilisés en cryptographie, mais il ne convient pas pour trouver de grands nombres premiers à la maison, car il nécessite de nombreuses années de calcul d'un ordinateur domestique normal, ce qui ne nous permet pas d'obtenir 400k $ (comme illustré ici ).

Néanmoins, presque tout est prêt pour le calcul des nombres premiers cryptographiques. Bien que notre vieil ami reste - le maximalisme. Il demande - si vous pouvez utiliser une période $$$(N-1) / 2$ , ce qui empêche l'utilisation des règles $$$(N-1) / 4, (N-1) / 6, (N-1) / 8$ etc.? Et il s'avère qu'avec la prudence requise - rien n'empêche!

De la même manière qu'avec la période $$$(N-1) / 2$ pour la période $$$(N-1) / 4$ nous sommes en mesure de fixer une borne inférieure en multipliant un nombre premier par 4 et en ajoutant 1. Ensuite, nous nous garantissons de pseudo-simple avec des périodes inférieures à $$$(N-1) / 4$ . Par conséquent, il reste à considérer la possibilité d'occurrences pseudo-simples avec un multiple de période de 4, 3, 2 (1 est exclu pour les composants, comme indiqué ci-dessus). D'après la formule de calcul du nombre par période, on voit que la période du dividende doit être égale au plus petit commun multiple de ses diviseurs, ce qui implique que la période possible du nombre $$$N$ devrait non seulement tenir un nombre entier de fois $$$N-1$ (sinon il n'y aura pas de pseudo-simplicité), mais contient également un nombre entier de périodes de séparations. Ainsi, le nombre de diviseurs possibles d'un nombre pseudo-premier est fortement limité. Puisque la période d'un nombre quelconque ne peut pas être plus longue $$$N-1$ , puis pour un éventuel diviseur $$$N$ donnant à la suite de la division 3, la période ne peut pas être plus longue $$$N / 3-1$ , en outre, nous tenons compte du fait que la période de 3 est 2. $$$N / 3$ doit être étrange car il est étrange $$$N$ . Il résulte de ce qui précède que la période paire N / 3-1 est le plus petit multiple commun avec une période 2 du nombre 3, ce qui signifie que la période possible d'un N potentiellement pseudo-simple doit être égale à la période du nombre $$$N / 3$ . Au total, il y a une valeur de la période $$$N$ pour laquelle la pseudo-simplicité est possible, cette $$$(N-1) / 4$ . Pour les autres valeurs, soit $$$N / 3$ trop peu ou sa période (et avec elle la période $$$N$ ) ira dans la zone interdite ci-dessous $$$(N-1) / 4$ . La même histoire avec des nombres impairs, moins $$$N / 3$ mais leurs règles ne peuvent pas être plus longues $$$(N-1) / 4$ et, par conséquent, tous sont simplement exclus de l'examen. Montrez maintenant que $$$N / 3$ ne peut pas avoir de règles $$$(N-1) / 4$ , ce qui signifie qu'il ne peut pas diviser entièrement la période entière. Rappelons d'abord la formule $$$m = a + b-2$ , ce qui nous donne le nombre de résidus de diviseurs multiples pour un nombre divisible uniquement par $$$a$ et $$$b$ . Dans notre cas $$$N$ censé être divisé en $$$N / 3$ et par 3, tous les autres diviseurs sont exclus, nous obtenons donc - $$$m = N / 3 + 3-2 = N / 3 + 1$ . Maintenant, à partir de la période complète, vous devez soustraire les valeurs «interdites», qui seront $$$N / 3 + 1$ , puis diviser par 4. Nous obtenons la période de travail possible $$ : $$$p = (N-1-N / 3-1) / 4 = N / 6-1 / 2$ moins $$$(N-1) / 4$ c'est-à-dire une période de temps $$$(N-1) / 4$ impossible en raison de la nécessité de prendre en compte les résidus «interdits», ce qui conduit toutes les périodes pseudo-simples possibles à la région interdite (moins $$$(N-1) / 4$ ) Cela signifie que cette situation nous garantit que le nombre construit n'est pas pseudo-simple, et donc nous pouvons à nouveau être sûr des résultats d'un test de simplicité probabiliste ultérieur.

De même, et compte tenu de la divisibilité de la période complète, on peut obtenir les mêmes résultats pour d'autres valeurs. Mais si nous voulons obtenir des nombres premiers cryptographiques de cette façon, alors en multipliant par 2,4,6, nous augmenterons la taille du nombre pendant très longtemps, il est donc logique de regarder dans la direction d'une autre option - la multiplication de deux nombres premiers. Si nous multiplions un nombre premier par un autre, nous obtenons un nombre impair, nous devons donc également multiplier par 2 pour obtenir une période entière paire et un candidat impair pour le nombre premier. La période complète dans ce cas sera divisée en $$ où $$$a$ et $$$b$ Sont des nombres premiers. Nous devons maintenant prouver que les périodes indiquées ne donneront pas de pseudo-simplicité, ou trouver des signes nous avertissant de la présence de pseudo-simplicité. Notez simplement que si la période est égale à $$ , alors le nombre sera premier (comme indiqué ci-dessus). Il est également montré ci-dessus qu'un nombre de demi-période ne peut pas être pseudo-simple, donc une période de longueur $$$ab$ peut être exclu. Bien que pour être complet, vous pouvez vérifier la période $$$ab$ des moyens alternatifs. Donc, si la période est $$$ab$ , puis étant donné que $$$a$ et $$$b$ simple, il devient clair que le plus petit commun multiple des périodes de diviseur $$$N$ ne peut être égal $$$ab$ , tandis que les périodes des séparateurs peuvent être égales à $$$ab$ les deux ou un $$$a$ et un autre $$$b$ . Puisque la période est toujours inférieure au nombre lui-même, alors $$$(ab + x) * (ab + y)$ il y aura évidemment plus $$ . Par conséquent, la pseudo-simplicité n'est pas possible avec une telle période. Il reste donc à vérifier les périodes $$ . 2 est inférieur à la période minimale possible pour tous les nombres, plus de 3, par conséquent, nous excluons une telle période. Supposons maintenant que le nombre construit est divisé par $$$m$ et $$$n$ , puis avec l'égalité de la période $$$N$ sens $$$a$ , leurs périodes seront également égales $$$a$ , car il s'agit du seul multiple le moins commun pour deux nombres, car $$$a$ pas divisé en rien. Il s'ensuit que $$$(a + x) * (a + y) = N = ab * 2 + 1$ où $$$a + x = m$ - le premier facteur possible avec une période $$$a$ et $$$a + y = n$ - deuxième. Suivant: $$$a ^ 2 + ax + ay + xy = 2ab + 1$$$$=>$$$$a ^ 2 + ax + ay + (ka + r) = 2ab + 1$$$$=>$$$$a + x + y + k = (2ab + 1-r) / a$ . Ici $$$r$ peut être égal à un seul, sinon l'entier ne fonctionnera pas à gauche. Ensuite: $$$x + y + k = 2b-a$ , d'où il résulte que si $$$a \ geq 2b$ , puis pseudo-simple avec un point $$$a$ ne peut pas être. Reste à vérifier la pseudo-simplicité à $$$a <2b$ , ce qui peut être fait en vérifiant les valeurs dans la série de résidus à la position $$$a$ s'il y a 1, un tel nombre peut être pseudo-simple et doit être exclu des opérations ultérieures. Raisonnement pour $$$b$ complètement analogue, ce qui signifie la nécessité de vérifier l'égalité de l'unité et de son reste, à condition $$$b <2a$ .

Pour la période $$$2a$ nous avons: $$$4a ^ 2 + 2ax + 2ay + xy = 2ab + 1$$$$=>$$$$4a ^ 2 + 2ax + 2ay + (ka + r) = 2ab + 1$$$$=>$$$$4a + 2x + 2y + k = (2ab + 1-r) / a$$$$=>$$$$2x + 2y + k = 2b-4a$ . Nous obtenons cela pour $$$4a \ geq 2b$ (ou de manière équivalente - $$$2a \ geq b$ ) encore une fois, il ne peut y avoir de simplicité, mais si $$$2a <b$ , alors vous devez vérifier le solde de la position $$$2a$ . De même pour $$$b$ - vérifier si $$ . Au total, on obtient pour $$$a$ et pour $$$b$ la nécessité de vérifier uniquement les éléments de campagne $$$2a$ et $$$2b$ parce que les règles $$$a$ et $$$b$ va se répéter juste en position $$$2a$ et $$$2b$ . La vérification n'est effectuée que dans les conditions ci-dessus, ce qui doublera presque le processus lors de la vérification de grandes valeurs $$$a$ ou $$$b$ , car pour eux ils doivent $$$a \ geq 2b$ avec le schéma de génération simple ci-dessous, et les valeurs inférieures seront vérifiées très rapidement en raison de leur petite taille.

Ainsi, les fondements théoriques ont été montrés ci-dessus pour pouvoir générer des nombres premiers garantis pour des domaines critiques tels que la cryptographie.

De plus, une voie est ouverte pour vérifier la simplicité d'un nombre arbitraire, à condition que les diviseurs de sa période entière soient trouvés ( $$$N-1$ ) Ainsi, pour des nombres premiers <126 000 000, le nombre de «nombres premiers multipliés» appartenant à la classe est de 676625, avec le nombre total de nombres premiers 7163812, ce qui nous donne un peu moins de 9,5%. Pour les nombres premiers jusqu'à un milliard, nous avons 3,49% appartenant à la classe 2p + 1, 1,8116% de la classe 4p + 1, 2,4709% de la classe 6p + 1 et seulement 7,7746%, où p est un nombre premier. Certes, il convient de noter que la décomposition de la période complète des grands nombres est très difficile. Dans ce cas, vous pouvez proposer un contrôle récursif, ce qui augmentera légèrement la taille des nombres disponibles pour le contrôle, mais en même temps réduira considérablement la proportion de nombres passant un tel contrôle, car si le coefficient déterminant l'appartenance aux classes de nombres premiers récursifs est pris égal à 0,2, alors déjà dans le deuxième contrôle, nous ont seulement 0,04, soit 4% du nombre total de nombres premiers. Néanmoins, dans certains cas, cette approche peut être bénéfique.

Résultats pratiques

Le générateur lui-même, bien sûr, a été écrit et testé, car la complexité y est minime. Au cours de la vérification, il s'est avéré que l'algorithme suivant serait pleinement fonctionnel:

Nous obtenons, par exemple, 1000 nombres premiers initiaux, qui peuvent être générés à l'aide du tamis d'Eratosthène ou simplement téléchargés à partir d'ici . Ensuite, nous multiplions chaque valeur par chacune restante et n'oubliez pas de multiplier par deux, puis d'ajouter une. Le candidat résultant est souvent divisé par 3, car les nombres premiers ont une caractéristique spécifique similaire à la présence d'une charge sur les particules en physique. Les personnes simples avec la même «charge» sont repoussées et avec différentes, elles sont attirées. Dans ce cas, la «charge» est le reste de la division par 3. Autrement dit, si le reste de la division par 3 est le même pour les deux nombres premiers, le nouveau nombre premier ne fonctionnera pas, car il sera divisé par 3. Et si le reste est différent, alors nous pouvons obtenir le bon candidat à simple. De plus, tous les simples obtenus par multiplication sont «synchronisés», c'est-à-dire qu'ils reçoivent le même reste égal à 2. Par conséquent, il est inutile de les multiplier à nouveau par eux-mêmes. Donc, pour obtenir de nouveaux nombres premiers, nous devons filtrer la partie du 1000 initial pour laquelle le module du triple (le reste de la division par 3) est 1. Ainsi, après la première multiplication de tous avec tout le monde, nous grandissons dans la quantité de nombres qui sont déjà inutiles pour se multiplier les uns avec les autres par conséquent, pour augmenter encore la taille (à celle utilisée en cryptographie), nous devons multiplier encore et encore les nombres premiers obtenus par les nombres «chargés de manière opposée» précédemment sélectionnés. Après multiplication et ajout d'une unité, nous effectuons des vérifications selon le critère de possibilité de pseudo-simplicité et si le critère est satisfait, nous vérifions le reste en position 2a pour chaque candidat. S'il y a 1, alors le candidat est rejeté. Ensuite, chaque candidat est vérifié par le test probabiliste habituel, c'est-à-dire que la valeur est calculée dans la série de résidus à la position $$$(N-1) / 2$ si c'est 1 ou $$$N-1$ , alors devant nous est un nombre premier garanti.

Lors de la génération, il faut garder à l'esprit qu'à chaque itération, une augmentation du nombre de nombres premiers générés est obtenue, c'est-à-dire que le coefficient de multiplication pour 1000 nombres premiers initiaux est bien plus que l'unité. Par conséquent, pour obtenir des nombres premiers cryptographiques, il est nécessaire de limiter la génération, sinon cela prendra beaucoup de temps et il n'y aura peut-être pas assez de mémoire. Dans le même temps, il ne faut pas réduire l'ensemble initial de simples, car la génération doit être aussi aléatoire que possible, de sorte que, connaissant son algorithme, l'attaquant ne prédirait pas les valeurs résultantes. Pour cela, il est nécessaire de mettre en œuvre un mécanisme de coupure des branches de l'arbre de génération, qui permet à chaque fois d'obtenir des simples simples situés assez loin des précédents. Et bien sûr, couper l'excédent accélère considérablement le processus.

Le temps d'exécution du test dépend du nombre de candidats générés. Chacun des candidats passe un test de probabilité, ce qui ralentit le plus la génération. En tests pour obtenir quelques centaines de portée simple $$ - $$$2 ^ {1200}$ 5 à 20 minutes ont été consacrées. Cette différence de temps s'explique par différentes manières dont l'algorithme passe dans l'arbre de génération. Donc, initialement, la génération est limitée à environ 10 nombres, mais à mesure que la taille cryptographique approche, la génération s'estompe en raison d'une réduction significative du coefficient de multiplication avec un nombre croissant. Par conséquent, il est nécessaire d'augmenter le nombre de nombres intermédiaires intermédiaires, mais il est difficile de dire à quel point il est spécifique, et donc une simple augmentation de la quantité autorisée d'un facteur deux est utilisée pour le limiter avec une augmentation de la taille du nombre et un excès d'un seuil approximatif. En conséquence, dans les limites des limitations, le nombre de nouveaux simples peut flotter et ainsi faire une différence significative dans le temps de génération total.

Voici le texte d'une procédure Java qui génère des nombres premiers. Naturellement, il ne satisfait pas aux exigences cryptographiques qui vont bien au-delà du code du programme et concernent principalement des problèmes d'organisation. Dans la partie purement logicielle, la procédure n'implémente pas le mécanisme de rognage des branches de l'arbre de génération, à l'exception de la restriction la plus simple. Néanmoins, comme exemple de mise en œuvre de l'algorithme de génération, le programme peut vous aider avec quelque chose.

Les paramètres d'entrée sont la liste initiale de simples et PrintWriter pour enregistrer le résultat dans un fichier. Après l'achèvement de l'algorithme, le fichier contiendra tous les produits des nombres premiers générés avec ces nombres initiaux qui ont un module de trois égal à un. Le résultat peut être vérifié à l'aide de services en ligne qui implémentent la factorisation des nombres, mais il faut comprendre qu'ils peuvent utiliser un test probabiliste de simplicité avant d'effectuer la factorisation, et donc, pour vérifier l'approche proposée, ils deviennent inutiles (car tous les nombres sont déjà vérifiés par un test probabiliste). Mais un certain nombre d'entre eux commencent immédiatement à factoriser le nombre proposé en facteurs, de tels sites peuvent donner une confiance supplémentaire dans l'exactitude de la méthode proposée.

public static void generatePrimes(List<Integer> primes, PrintWriter pw) { List<BigInteger> mod3_1 = new ArrayList<BigInteger>(); List<BigInteger> l = new ArrayList<BigInteger>(); BigInteger three=BigInteger.valueOf(3), two=BigInteger.valueOf(2); for (int k=0;k<primes.size()-1;k++) { BigInteger seed=BigInteger.valueOf(primes.get(k)); BigInteger s2=seed.shiftLeft(1); BigInteger r0=seed.remainder(three); if (r0.intValue()==1) mod3_1.add(seed); for (int i=k+1;i<primes.size();i++) { BigInteger p=BigInteger.valueOf(primes.get(i)); BigInteger r=p.remainder(three); if (r.intValue()==r0.intValue()) continue; // divisible by 3 else addIfPrime(p,seed,s2,two,l); } } List<BigInteger> ps=l; do { System.out.println("found "+l.size()+", bits="+l.get(0).bitLength()); l=new ArrayList<BigInteger>(); for (int k=0;k<ps.size();k++) { BigInteger seed=ps.get(k); BigInteger s2=seed.shiftLeft(1); for (int i=0;i<mod3_1.size();i++) addIfPrime(mod3_1.get(i),seed,s2,two,l); int n=100000; // change following to adjust for required bit count if (l.size()>0) if (l.get(0).bitLength()<700) n=10; else if (l.get(0).bitLength()<800) n=20; else if (l.get(0).bitLength()<900) n=40; if (l.size()>n) break; } ps=l; for (int i=0;i<l.size();i++) pw.println(l.get(i)); pw.flush(); } while (l.size()>0); System.out.println("Done"); } private static void addIfPrime(BigInteger a, BigInteger b, BigInteger b2, BigInteger two, List<BigInteger> l) { BigInteger a2=a.shiftLeft(1), fp=b.multiply(a2), n=fp.add(BigInteger.ONE); BigInteger r=null; if (a2.compareTo(b)<0) r=two.modPow(a2,n); // 2a<b else if (a.compareTo(b2)<0) r=two.modPow(a,n); // a<2b if (r!=null && r.compareTo(BigInteger.ONE)==0) return; r=null; if (b2.compareTo(a)<0) r=two.modPow(b2,n); // 2b<a else if (b.compareTo(a2)<0) r=two.modPow(b,n); // b<2a if (r!=null && r.compareTo(BigInteger.ONE)==0) return; r=two.modPow(fp.shiftRight(1),n); if (r.compareTo(BigInteger.ONE)!=0) return; l.add(n); } 

Eh bien, maintenant que vous (enfin, presque) savez tout sur la génération de nombres premiers, peut-être que vos intérêts iront au-delà de la cryptographie seule et il deviendra intéressant pour vous d'étudier la théorie des nombres, car, comme mentionné ci-dessus, elle est disponible pour les élèves de cinquième année, mais en même temps, cela vous permet également de trouver indépendamment de vrais diamants sans attendre l'aide de mathématiciens sérieux.