Gerando primos realmente grandes
https://stackoverflow.com/questions/1146274
-
16-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Estou brincando e tentando escrever uma implementação do RSA. O problema é que estou preso a gerar os enormes números primos envolvidos na geração de um par de chaves. Alguém poderia me indicar uma maneira rápida de gerar grandes primos/primos prováveis?
Solução
Você não gera números primos exatamente. Você gera um grande número ímpar aleatoriamente e teste se esse número é o Prime, se não gerar outro aleatoriamente. Existem algumas leis de números primos que basicamente afirmam que suas chances de "acertar" um prime via aleatória tentativas é (2/ln n)
Por exemplo, se você deseja um número aleatório de 512 bits, encontrará um em 2/(512*ln (2)), aproximadamente 1 em cada 177 dos números que você tentará serão primos.
Existem várias maneiras de testar se um número é o Prime, um bom é o "teste de molho-rabina" Conforme declarado em outra resposta a esta pergunta.
Além disso, o OpenSSL tem um bom utilitário para testar os primos:
$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime
Outras dicas
Dê uma olhada em como TrueCrypt faz isso. Além disso, dê uma olhada em Rabin-Miller Para testar grandes pseudoprimes.
Você não mencionou qual idioma está usando. Alguns têm um método de fazer isso embutido. Por exemplo, em Java, isso é tão fácil quanto chamar NextProbablePrime () em um biginteger.
A resposta anterior está incorreta: 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 509 * 59.
Eu acho que o pôster está se lembrando da prova (real) de que existem um número incontável de números primos.
Mono tem uma classe Biginteger que é de código aberto, assim como Java. Você pode dar uma olhada neles. Eles provavelmente são portáteis :) G'luck
Existe um algoritmo devido a U. Maurer que gera números anuais aleatórios (em contraste com os primos estatisticamente altamente comprováveis) que são quase uniformemente distribuídos pelo conjunto de todos os primos de um tamanho especial. Eu tenho uma implementação python que é bastante eficiente em:http://s13.zetaboards.com/crypto/topic/7234475/1/
