Large integers and cousins

Question

Is there any function that generates prime and integer numbers in considerably large sizes?

If not, how to do it using Javascript?

Answer 1

A solution making use of Forge:

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

^{Solution credit for @dlongley in this answer in the SOEN.}

Answer 2

I already I insisted enough on the comments for you to use a pre-defined primes table. Generating Javascript primes is not at all efficient, especially if you only need to draw one. If you need numbers with multiple digits then, it will be well slow.

An adaptation of the implementation of the Sieve of Eratosthenes posted by the user Guffa on the 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(', ');

Answer 3

You can use one of the libraries on this page to solve your problem:

• http://www-cs-students.stanford.edu/~tjw/jsbn/

-- Translated transcription of a part --

The jsbn library API is very reminiscent of classes java.math.BigInteger java. For example:

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

will print b60c.

Core Library

• jsbn.js - basic implmentation of BigInteger, enough for RSA encryption and not much more.
• jsbn2.js - the rest of the library, including most public methods of BigInteger.

RSA

• rsa.js - implementation of RSA encryption, does not require jsbn2.js.
• rsa2.js - rest of the RSA algorithm, including decryption and key generation.

ECC

• Ec.js - elliptic curves math, depends on jsbn.js and jsbn2.js
• sec.js - standard parameters of elliptic curves

Utilities

• Rng.js - RNG rudimentary entropy collector interface, requires a PRNG backend to define prng_newstate().
• prng4.js - ARC4-based PRNG backend for Rng.js, very small.
• Base64.js - Base64 encoding and decoding routines.
• sha1.js - SHA-1 hash function, only required for IBE demo.

-- End of transcription --

 

Algorithms to generate very large primes

I found a implementation of a python algorithm

Answer 4


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 cousins = primosAte(100000000000000000000000000000000000000000000000000000000000000); Document.body.innerHTML = cousins.toString(', ');