-2

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
Astoach167
  • 91
  • 1
  • 7
  • It looks like you have a low probability of getting a prime number. Plus you have this wierd mathematical relationship between the two numbers you're testing. – matt Aug 12 '20 at 16:13
  • Even if you were generating them correctly, the `Prime Number Theorem` says the asymptotic density of primes becomes smaller as primes get larger. So one would expect them to occur less frequently for large values of `n`. – WJS Aug 12 '20 at 16:41

1 Answers1

2

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.

Joachim Sauer
  • 302,674
  • 57
  • 556
  • 614
  • 1
    A random integer of n bits has about a 1/n chance of being prime (within a small constant factor). As far as I know that is also true of 2*p + 1 if p is prime. So the probability that a random n-bit integer is a Sophie Germain prime should be about 1/(n^2 + n). Another way of putting it: the expected number of tries to find an n-bit prime is O(n). The expected number of tries to find an n-bit SG prime is O(n^2). – President James K. Polk Aug 13 '20 at 16:37