Question aléatoire de SQuAD :

Quand a-t-on découvert que les nombres premiers pouvaient s'appliquer à la création d'algorithmes de cryptographie à clé publique ?

Réponse:

les années 1970

Phrases récupérées :

1. Cependant, cette vision a été brisée dans les années 1970, quand il a été annoncé publiquement que les nombres premiers pourraient être utilisés comme base pour la création d'algorithmes de cryptographie à clé publique.
2. Les nombres premiers sont utilisés dans plusieurs routines des technologies de l'information, telles que la cryptographie à clé publique, qui utilise des propriétés telles que la difficulté de prendre en compte de grands nombres dans leurs facteurs premiers.
3. Des algorithmes beaucoup plus efficaces que la division d'essai ont été conçus pour tester la primalité des grands nombres.
4. Plusieurs algorithmes de cryptographie à clé publique, tels que RSA et l'échange de clés Diffie-Hellman, sont basés sur de grands nombres premiers (par exemple, des nombres premiers de 512 bits sont fréquemment utilisés pour RSA et des nombres premiers de 1024 bits sont typiques pour Diffie-Hellman.) .
5. Les nombres premiers sont également utilisés pour les tables de hachage et les générateurs de nombres pseudo-aléatoires.
6. Certains de ces nombres premiers ont été trouvés en utilisant l'informatique distribuée.
7. Pendant longtemps, la théorie des nombres en général, et l'étude des nombres premiers en particulier, a été considérée comme l'exemple canonique des mathématiques pures, sans aucune application en dehors de l'intérêt personnel d'étudier le sujet, à l'exception de l'utilisation des nombres premiers. dents d'engrenage pour répartir l'usure uniformément.
8. Les algorithmes déterministes permettent de savoir avec certitude si un nombre donné est premier ou non.
9. L'expression "tous les algorithmes possibles" comprend non seulement les algorithmes connus aujourd'hui, mais tout algorithme qui pourrait être découvert à l'avenir.
10. Par exemple, la division d'essai est un algorithme déterministe car, si elle est effectuée correctement, elle identifiera toujours un nombre premier comme premier et un nombre composé comme composé.
11. Exprimé comme un problème de décision, c'est le problème de décider si l'entrée a un facteur inférieur à k. Aucun algorithme efficace de factorisation d'entiers n'est connu, et ce fait constitue la base de plusieurs systèmes cryptographiques modernes, tels que l'algorithme RSA.
12. Avant le début des recherches proprement dites explicitement consacrées à la complexité des problèmes algorithmiques, de nombreux fondements ont été posés par divers chercheurs.
13. Ce principe local-global souligne à nouveau l'importance des nombres premiers pour la théorie des nombres.
14. Les algorithmes probabilistes sont normalement plus rapides, mais ne prouvent pas complètement qu'un nombre est premier.
15. Cependant, l'algorithme quantique le plus connu pour ce problème, l'algorithme de Shor, fonctionne en temps polynomial.
16. Le crible d'Ératosthène, attribué à Ératosthène, est une méthode simple pour calculer les nombres premiers, bien que les grands nombres premiers trouvés aujourd'hui avec les ordinateurs ne soient pas générés de cette façon.
17. Un problème est considéré comme intrinsèquement difficile si sa résolution nécessite des ressources importantes, quel que soit l'algorithme utilisé.
18. Les algorithmes qui utilisent des bits aléatoires sont appelés algorithmes aléatoires.
19. On pense que si un problème peut être résolu par un algorithme, il existe une machine de Turing qui résout le problème.
20. Cependant, les nombres de Carmichael sont nettement plus rares que les nombres premiers, ce test peut donc être utile à des fins pratiques.
21. Par exemple, la liste des nombres premiers de Derrick Norman Lehmer jusqu'à 10 006 721, réimprimée jusqu'en 1956, a commencé avec 1 comme premier nombre premier.
22. La thèse de Cobham dit qu'un problème peut être résolu avec une quantité réalisable de ressources s'il admet un algorithme en temps polynomial.
23. Euclide a également montré comment construire un nombre parfait à partir d'un nombre premier de Mersenne.
24. En janvier 2016[mise à jour], le plus grand nombre premier connu compte 22 338 618 chiffres décimaux.
25. De telles questions ont stimulé le développement de diverses branches de la théorie des nombres, en se concentrant sur les aspects analytiques ou algébriques des nombres.