4

Existe alguma função que gere números primos e inteiros em tamanhos consideravelmente grandes?

Se não, como faze-lo usando JavaScript?

13
  • 1
    Você quer que alguém faça para você?
    – Lucas
    8/04/2015 às 20:18
  • 6
    Você precisa mesmo gerar os números? Eles são conhecidos, eu montaria uma array com primos de uma tabela qualquer (como esta) e sortearia uma posição da array.
    – bfavaretto
    8/04/2015 às 20:18
  • 2
    Estou falando da implementação. Em geral é mais confiável usar bibliotecas existentes para cripto ao invés de programar tudo denovo você mesmo. E se sua cripto estiver rodando em um broser, tem o problema de um adversário interferir no código Javascript que o cliente recebe
    – hugomg
    8/04/2015 às 20:50
  • 2
    Você já tinha perguntado a mesma coisa sobre PHP e eu tinha dado a mesma sugestão, e outros usuários também (a pergunta não existe mais, você apagou). Não consigo entender por que gerar, os números primos são todos conhecidos (os que não são, não é um browser que vai conseguir calcular...). Não entendo por que você acha que eles seriam mais secretos se você calcular. Qualquer um com uma tabela de primos pode tentar um ataque brute-force, se é essa a sua preocupação.
    – bfavaretto
    8/04/2015 às 21:05
  • 2
    Embora a pergunta tal como foi escrita dê margem para interpretação, eu pessoalmente [que tenho interesse em criptografia, apesar de não ser especialista] quando leio "primos muito grandes" já presumo se tratar de algo que vai além da representação em int, long ou double, algo que demande uma biblioteca de inteiros de precisão arbitrária. E a solução "padrão" para esse problema é sempre a mesma - gerar números aleatórios e testar se são provavelmente primos. O fato desses primos serem "conhecidos" não tem relevância no caso, pois o número deles é grande demais para testar de um por um.
    – mgibsonbr
    8/04/2015 às 23:50

4 Respostas 4

9

Uma solução fazendo uso de forge:

var bits = 1024;
forge.prime.generateProbablePrime(bits, function(err, num) {
    console.log('número primo aleatório', num.toString(16));
});

Crédito da solução para @dlongley nesta resposta no SOEN.

2
  • Interessante como isso funciona (está descrito na resposta do SOEN que você indicou). Ele gera um candidato a primo de maneira eficiente, e depois testa se é primo mesmo. Se não for, tenta outro candidato. E essa biblioteca forge parece ser exatamente o que o AP precisa para resolver o problema maior dele (que é de criptografia).
    – bfavaretto
    8/04/2015 às 21:52
  • Adorei esta, estou tentando extrair apenas esta funçao com suas dependencias mas nao consigo, tem sugestao? 8/04/2015 às 23:12
8

Eu já insisti o suficiente nos comentários para você usar uma tabela de primos pré-definidos. Gerar primos em JavaScript não é nada eficiente, especialmente se você só precisa sortear um. Se você precisa de números com vários dígitos então, vai ser bem lento.

Segue uma adaptação da implementação do Crivo de Eratóstenes postada pelo usuário Guffa no site Code Review:

function primosAte(n) {
  var i, j;
  var prime = new Array(n);
  for (i = 2; i < n ; i++) prime[i] = true;
  
  for (i = 2; i * i < n ; i++) {
    if (prime[i]) {
      for (j = 0; i * i + i * j < n ; j++) {
        prime[i * i + i * j] = false;
      }
    }
  }
  var primes = [];
  for (i = 2 ; i < n ; i++) {
    if (prime[i]){
      primes.push(i);
    }
  }
  return primes;
}
 
var primos = primosAte(1000);
document.body.innerHTML = primos.toString(', ');

2

Você pode usar uma das bibliotecas nessa página para resolver o seu problema:

-- Transcrição traduzida de uma parte --

A API da biblioteca jsbn lembra bastante as classes java.math.BigInteger do Java. Por exemplo:

x = new BigInteger("abcd1234", 16);
y = new BigInteger("beef", 16);
z = x.mod(y);
alert(z.toString(16));

vai imprimir b60c.

Core Library

  • jsbn.js - implmentação básica de BigInteger, o suficiente para criptografia RSA e não muito mais.
  • jsbn2.js - o resto da biblioteca, incluindo a maioria dos métodos públicos de BigInteger.

RSA

  • rsa.js - implementação da criptografia RSA, não requer jsbn2.js.
  • rsa2.js - resto do algoritmo RSA, incluindo decriptação e geração de chave.

ECC

  • ec.js - matemática de curvas elípticas, depende de jsbn.js e jsbn2.js
  • sec.js - parâmetros padrão de curvas elípticas

Utilities

  • rng.js - interface coletora de entropia rudimentar RNG, requer um backend PRNG para definir prng_newstate().
  • prng4.js - PRNG backend baseado em ARC4 para rng.js, bem pequeno.
  • base64.js - rotinas de codificação e decodificação de Base64.
  • sha1.js - função hash SHA-1, só é necessária para demo IBE.

-- Fim da transcrição --

 

Algoritmos para gerar primos muito grandes

Achei uma implementação de um algoritmo em python

13
  • 1
    perdao, nao entendi o contexto de ligaçao pergunta-resposta. 8/04/2015 às 21:22
  • 1
    @user3163662 Esse último algoritmo citado é para encontrar números que são garantidamente primos. Antigamente, enquanto esse problema ainda estava em aberto, só se podia determinar [em tempo hábil] se um número era provavelmente primo, e isso continuou sendo "bom o bastante" para muitas aplicações práticas (mesmo depois da descoberta de um algoritmo polinomial que dá uma resposta exata). Como você não cita na pergunta qual o propósito desses primos, não tenho como dizer se no seu caso é ou não é importante essa garantia (provavelmente não é).
    – mgibsonbr
    8/04/2015 às 23:54
  • 1
    Eu estou tentando traduzir o código... mesmo que não seja importante para esta questão, parece que pode ser algo útil. 9/04/2015 às 0:04
  • 1
    @user3163662 Conheço muito pouco de Diffie-Hellman (exceto a teoria), mas até onde eu saiba os primos usados precisam ser grandes, enormes até, mas não sei te dizer se eles precisam ou não ser secretos. Sei que pelo menos um de seus parâmetros não é secreto, há inclusive uma lista recomendada desses parâmetros. De todo modo, como esse assunto anda muito popular ultimamente (você é a 3ª ou 4ª pessoa que aparece com dúvidas desse tipo), estou escrevendo um par pergunta-resposta para ajudar a esclarecer alguns dos detalhes mais finos do DH em JavaScript.
    – mgibsonbr
    9/04/2015 às 1:19
  • 1
    @user3163662 A resposta do Zuul não te atende? Nem alguma das bibliotecas mencionadas nesta resposta? O processo básico é esse mesmo: gere números aleatórios e faça-os passar por um teste de primalidade (exato ou probabilístico). Implementar isso à mão é osso (estudei na faculdade, mas como exercício somente), melhor procurar uma implementação já pronta.
    – mgibsonbr
    9/04/2015 às 1:30
-1


function primosAte(n) { var i, j; var prime = new Array(n); for (i = 2; i < n ; i++) prime[i] = true;

for (i = 2; i * i < n ; i++) {
if (prime[i]) {
  for (j = 0; i * i + i * j < n ; j++) {
    prime[i * i + i * j] = false;
  }
}
}
var primes = [];
for (i = 2 ; i < n ; i++) {
  if (prime[i]){
  primes.push(i);
}
}
return primes;

}

var primos = primosAte(100000000000000000000000000000000000000000000000000000000000000); document.body.innerHTML = primos.toString(', ');

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .