Pergunta aleatória de SQuAD:

Quando foi descoberto que os números primos poderiam ser aplicados à criação de algoritmos de criptografia de chave pública?

Responder:

os anos 1970

Frases recuperadas:

1. No entanto, esta visão foi quebrada na década de 1970, quando foi anunciado publicamente que números primos poderia ser usado como base para a criação de algoritmos de criptografia de chave pública.
2. Os números primos são usados ​​em várias rotinas de tecnologia da informação, como a criptografia de chave pública, que faz uso de propriedades como a dificuldade de fatorar grandes números em seus fatores primos.
3. Algoritmos muito mais eficientes do que a divisão experimental foram concebidos para testar a primalidade de grandes números.
4. Vários algoritmos de criptografia de chave pública, como RSA e a troca de chaves Diffie – Hellman, são baseados em grandes números primos (por exemplo, números primos de 512 bits são frequentemente usados ​​para RSA e números primos de 1024 bits são típicos para Diffie – Hellman.) .
5. Os números primos também são usados ​​para tabelas hash e geradores de números pseudo-aleatórios.
6. Alguns desses primos foram encontrados usando computação distribuída.
7. Por muito tempo, a teoria dos números em geral, e o estudo dos números primos em particular, foram vistos como o exemplo canônico da matemática pura, sem aplicações fora do interesse próprio de estudar o tópico, com exceção do uso de números primos dentes da engrenagem para distribuir o desgaste uniformemente.
8. Algoritmos determinísticos fornecem uma maneira de dizer com certeza se um determinado número é primo ou não.
9. A frase "todos os algoritmos possíveis" inclui não apenas os algoritmos conhecidos hoje, mas qualquer algoritmo que possa ser descoberto no futuro.
10. Por exemplo, a divisão experimental é um algoritmo determinístico porque, se executado corretamente, sempre identificará um número primo como primo e um número composto como composto.
11. Formulado como um problema de decisão, é o problema de decidir se a entrada tem um fator menor que k. Nenhum algoritmo de fatoração de números inteiros eficiente é conhecido, e esse fato forma a base de vários sistemas criptográficos modernos, como o algoritmo RSA.
12. Antes do início da pesquisa real explicitamente dedicada à complexidade dos problemas algorítmicos, várias bases foram estabelecidas por vários pesquisadores.
13. Este princípio local-global novamente sublinha a importância dos primos para a teoria dos números.
14. Os algoritmos probabilísticos são normalmente mais rápidos, mas não provam completamente que um número é primo.
15. No entanto, o algoritmo quântico mais conhecido para esse problema, o algoritmo de Shor, é executado em tempo polinomial.
16. A peneira de Eratóstenes, atribuída a Eratóstenes, é um método simples para calcular primos, embora os grandes primos encontrados hoje em computadores não sejam gerados dessa forma.
17. Um problema é considerado inerentemente difícil se sua solução requer recursos significativos, qualquer que seja o algoritmo usado.
18. Algoritmos que usam bits aleatórios são chamados de algoritmos aleatórios.
19. Acredita-se que se um problema pode ser resolvido por um algoritmo, existe uma máquina de Turing que resolve o problema.
20. Os números de Carmichael são substancialmente mais raros do que os números primos, portanto, este teste pode ser útil para fins práticos.
21. Por exemplo, a lista de primos de Derrick Norman Lehmer até 10.006.721, reimpressa até 1956, começou com 1 como seu primeiro primo.
22. A tese de Cobham diz que um problema pode ser resolvido com uma quantidade viável de recursos se admitir um algoritmo de tempo polinomial.
23. Euclides também mostrou como construir um número perfeito a partir de um primo de Mersenne.
24. Em janeiro de 2016 [atualização], o maior número primo conhecido tinha 22.338.618 dígitos decimais.
25. Essas questões estimularam o desenvolvimento de vários ramos da teoria dos números, com foco nos aspectos analíticos ou algébricos dos números.