Pregunta aleatoria de SQuAD:

¿Cuándo se descubrió que los números primos podrían aplicarse a la creación de algoritmos de criptografía de clave pública?

Respuesta:

la década de 1970

Oraciones recuperadas:

1. Sin embargo, esta visión se hizo añicos en la década de 1970, cuando se anunció públicamente que los números primos podrían utilizarse como base para la creación de algoritmos de criptografía de clave pública.
2. Los primos se utilizan en varias rutinas de la tecnología de la información, como la criptografía de clave pública, que hace uso de propiedades como la dificultad de factorizar grandes números en sus factores primos.
3. Se han ideado algoritmos mucho más eficientes que la división de prueba para probar la primacía de grandes números.
4. Varios algoritmos de criptografía de clave pública, como RSA y el intercambio de claves Diffie-Hellman, se basan en números primos grandes (por ejemplo, los primos de 512 bits se utilizan con frecuencia para RSA y los primos de 1024 bits son típicos para Diffie-Hellman). .
5. Los números primos también se utilizan para tablas hash y generadores de números pseudoaleatorios.
6. Algunos de estos números primos se han encontrado utilizando computación distribuida.
7. Durante mucho tiempo, la teoría de números en general, y el estudio de los números primos en particular, fue visto como el ejemplo canónico de la matemática pura, sin aplicaciones fuera del interés propio de estudiar el tema con la excepción del uso de números primos. dientes de engranaje para distribuir el desgaste uniformemente.
8. Los algoritmos deterministas proporcionan una forma de saber con certeza si un número dado es primo o no.
9. La frase "todos los algoritmos posibles" incluye no solo los algoritmos conocidos hoy en día, sino cualquier algoritmo que pueda descubrirse en el futuro.
10. Por ejemplo, la división de prueba es un algoritmo determinista porque, si se realiza correctamente, siempre identificará un número primo como primo y un número compuesto como compuesto.
11. Expresado como un problema de decisión, es el problema de decidir si la entrada tiene un factor menor que k. No se conoce ningún algoritmo de factorización de enteros eficiente, y este hecho constituye la base de varios sistemas criptográficos modernos, como el algoritmo RSA.
12. Antes de que comenzara la investigación real dedicada explícitamente a la complejidad de los problemas algorítmicos, varios investigadores establecieron numerosos fundamentos.
13. Este principio local-global vuelve a subrayar la importancia de los números primos para la teoría de números.
14. Los algoritmos probabilísticos son normalmente más rápidos, pero no prueban completamente que un número sea primo.
15. Sin embargo, el algoritmo cuántico más conocido para este problema, el algoritmo de Shor, se ejecuta en tiempo polinomial.
16. El Tamiz de Eratóstenes, atribuido a Eratóstenes, es un método simple para calcular números primos, aunque los grandes números primos que se encuentran hoy en día con las computadoras no se generan de esta manera.
17. Un problema se considera intrínsecamente difícil si su solución requiere recursos importantes, sea cual sea el algoritmo utilizado.
18. Los algoritmos que utilizan bits aleatorios se denominan algoritmos aleatorios.
19. Se cree que si un problema puede resolverse mediante un algoritmo, existe una máquina de Turing que resuelve el problema.
20. Sin embargo, los números de Carmichael son sustancialmente más raros que los números primos, por lo que esta prueba puede ser útil para fines prácticos.
21. Por ejemplo, la lista de números primos hasta 10.006.721 de Derrick Norman Lehmer, reimpresa hasta 1956, comenzó con 1 como primer número primo.
22. La tesis de Cobham dice que un problema puede resolverse con una cantidad factible de recursos si admite un algoritmo de tiempo polinomial.
23. Euclides también mostró cómo construir un número perfecto a partir de un número primo de Mersenne.
24. En enero de 2016 [actualización], el número primo más grande conocido tiene 22,338,618 dígitos decimales.
25. Tales preguntas estimularon el desarrollo de varias ramas de la teoría de números, centrándose en los aspectos analíticos o algebraicos de los números.