why is my primality test failing so often when randomizing a BigInteger?

Tags: , ,



I wasn’t able to get true for both p and q, most of the results is both false or rarely p is true but q is false, why wouldn’t this test ever be true for both p and q?

BigInteger bitSize100 = new BigInteger("1").setBit(99);

for(int i = 0; i < 20; i++) {
        BigDecimal randomizer = new BigDecimal(Math.random()).multiply(new BigDecimal(bitSize100)); // get random 99 bit number
        BigInteger q = randomizer.toBigInteger().setBit(99); // must be 100 bits
        BigInteger p = q.add(q).add(BigInteger.ONE);
         System.out.println(p.isProbablePrime(100) + " " + q.isProbablePrime(100));
         
     }


output:
false false
false false
false false
false false
true false
false false
false false
false false
false false
false false
false false
false false
false false
false false
false false
false false
false false
false false
false false
false false

Answer

First of all BigDecimal randomizer = new BigDecimal(Math.random()).multiply(new BigDecimal(bitSize100)) does not result in 100 bit of randomness.

Math.random returns a double value that’s 64 bit large, so that’s the maximum amount of randomness this can create (and since the value is limited to values between 0 and 1, the actual amount of randomness is even smaller).

You should use a combination of Random.nextBytes() to fill a byte[] with random data and the BigInteger constructor that takes such a byte[] to construct your BigInteger. Avoid going through double and BigDecimal values at all here.

Edit: and that’s in fact exactly what you’ve been told on this other question of yours 4 hours ago.

Second: most numbers simply aren’t prime. If you randomly pick numbers (and don’t even exclude even numbers) then the huge majority of them will not be prime.

I don’t know how what fraction of prime numbers are Sophie Germain primes, but it’s obviously not all of them.

So with your code taking many attempts (definitely more than 20 on average) to find such a prime number pair is not surprising.



Source: stackoverflow