BigInteger.probablePrime() doesn't output the correct bitlength?
Hi,
I was trying to implement an algorithm for generating primes, p, that give an easy factorization of p - 1. To do this I am using BigInteger.probablePrime(int bitLength, Random rnd). For some reason, though, it never seems to give me a prime that has the bitlength I specify. This is how I coded it:
public BigInteger makePrime(int s)
{
BigInteger primeTest = BigInteger.valueOf(10);
boolean done =false;
while(!done)
{
primeTest = BigInteger.probablePrime(s,new Random());
System.out.println(primeTest.bitCount() +" = bit count (s = " + s +")");
primeTest = primeTest.multiply(BigInteger.valueOf(2));
primeTest = primeTest.add(BigInteger.valueOf(1));
if(primeTest.isProbablePrime(100))
{
done =true;
}
}
return primeTest;
}
Am I missing something?
I suppose I could always do something like:
while(primeTest.bitcount() < s)
{
primeTest = primeTest.nextProbablePrime();
}
But then, randomness is lost. And I only get the first probable prime with the bit length set. This is especially not cool because I am using this subroutine to populate an array of primes that I can then find the generator for Zp*. Anyway, can anyone see what's wrong with my code?
I would really appreciate any help anyone could send my way.
Thanks in advance,
Douglas
# 2
From the API documentation for Random:
"If two instances of Random are created with the same seed, and the same sequence of method calls is made for each, they will generate and return identical sequences of numbers."
And:
"Two Random objects created within the same millisecond will have the same sequence of random numbers."
So you might consider using only one Random object.
# 3
Sample output:
13 = bit count (s = 20)
11 = bit count (s = 20)
11 = bit count (s = 20)
11 = bit count (s = 20)
11 = bit count (s = 20)
Prime Number
1330103 and the bit count is 12 but should be 20
13 = bit count (s = 20)
10 = bit count (s = 20)
14 = bit count (s = 20)
8 = bit count (s = 20)
9 = bit count (s = 20)
13 = bit count (s = 20)
12 = bit count (s = 20)
11 = bit count (s = 20)
8 = bit count (s = 20)
Prime Number
1720619 and the bit count is 9 but should be 20
12 = bit count (s = 20)
10 = bit count (s = 20)
4 = bit count (s = 20)
11 = bit count (s = 20)
9 = bit count (s = 20)
Prime Number
1248407 and the bit count is 10 but should be 20
14 = bit count (s = 20)
10 = bit count (s = 20)
12 = bit count (s = 20)
11 = bit count (s = 20)
13 = bit count (s = 20)
13 = bit count (s = 20)
Prime Number
1402799 and the bit count is 14 but should be 20
13 = bit count (s = 20)
Prime Number
1551479 and the bit count is 14 but should be 20
13 = bit count (s = 20)
9 = bit count (s = 20)
12 = bit count (s = 20)
8 = bit count (s = 20)
9 = bit count (s = 20)
9 = bit count (s = 20)
13 = bit count (s = 20)
13 = bit count (s = 20)
12 = bit count (s = 20)
11 = bit count (s = 20)
8 = bit count (s = 20)
Prime Number
1634819 and the bit count is 9 but should be 20
10 = bit count (s = 20)
10 = bit count (s = 20)
12 = bit count (s = 20)
13 = bit count (s = 20)
13 = bit count (s = 20)
13 = bit count (s = 20)
11 = bit count (s = 20)
9 = bit count (s = 20)
11 = bit count (s = 20)
9 = bit count (s = 20)
9 = bit count (s = 20)
11 = bit count (s = 20)
Prime Number
1767947 and the bit count is 12 but should be 20
9 = bit count (s = 20)
10 = bit count (s = 20)
Prime Number
1679603 and the bit count is 11 but should be 20
13 = bit count (s = 20)
10 = bit count (s = 20)
12 = bit count (s = 20)
7 = bit count (s = 20)
9 = bit count (s = 20)
Prime Number
1074023 and the bit count is 10 but should be 20
11 = bit count (s = 20)
Prime Number
2081159 and the bit count is 12 but should be 20
(Also getting some output from another class in there. Will try using only one random object. Not sure if it'll work though but I guess anything is worth a try)
Thanks,
Douglas
# 4
Hi,
I changed my code to the following:
package q1;
import java.math.*;
import java.util.*;
public class Generator
{
int[] factorBase = new int[100];
int[] factors = new int[100];
Random p = new Random();
public Generator()
{
int i = 1;
factorBase[0] = 3;
while(i < 100)
{
factorBase[i] = BigInteger.valueOf(factorBase[i - 1]).nextProbablePrime().intValue();
++i;
}
}
public int[] initFactors()
{
int i = 0;
while(i < 100)
{
factors[i] = -1;
++i;
}
return factors;
}
public BigInteger makePrime(int s)
{
BigInteger primeTest = BigInteger.valueOf(10);
boolean done = false;
while(!done)
{
primeTest = BigInteger.probablePrime(s, p);
System.out.println(primeTest.bitCount() + " = bit count (s = " + s + ")");
primeTest = primeTest.multiply(BigInteger.valueOf(2));
primeTest = primeTest.add(BigInteger.valueOf(1));
if(primeTest.isProbablePrime(100))
{
done = true;
}
}
return primeTest;
}
}
and still got the following output:
11 = bit count (s = 20)
12 = bit count (s = 20)
8 = bit count (s = 20)
13 = bit count (s = 20)
13 = bit count (s = 20)
13 = bit count (s = 20)
6 = bit count (s = 20)
9 = bit count (s = 20)
12 = bit count (s = 20)
7 = bit count (s = 20)
Prime Number
1378823 and the bit count is 8 but should be 20
14 = bit count (s = 20)
9 = bit count (s = 20)
12 = bit count (s = 20)
11 = bit count (s = 20)
7 = bit count (s = 20)
15 = bit count (s = 20)
11 = bit count (s = 20)
13 = bit count (s = 20)
13 = bit count (s = 20)
12 = bit count (s = 20)
8 = bit count (s = 20)
11 = bit count (s = 20)
9 = bit count (s = 20)
10 = bit count (s = 20)
13 = bit count (s = 20)
10 = bit count (s = 20)
11 = bit count (s = 20)
8 = bit count (s = 20)
9 = bit count (s = 20)
14 = bit count (s = 20)
13 = bit count (s = 20)
16 = bit count (s = 20)
13 = bit count (s = 20)
8 = bit count (s = 20)
12 = bit count (s = 20)
13 = bit count (s = 20)
12 = bit count (s = 20)
13 = bit count (s = 20)
13 = bit count (s = 20)
13 = bit count (s = 20)
14 = bit count (s = 20)
12 = bit count (s = 20)
12 = bit count (s = 20)
6 = bit count (s = 20)
10 = bit count (s = 20)
13 = bit count (s = 20)
12 = bit count (s = 20)
6 = bit count (s = 20)
13 = bit count (s = 20)
9 = bit count (s = 20)
14 = bit count (s = 20)
10 = bit count (s = 20)
8 = bit count (s = 20)
11 = bit count (s = 20)
Prime Number
1077023 and the bit count is 12 but should be 20
10 = bit count (s = 20)
14 = bit count (s = 20)
10 = bit count (s = 20)
11 = bit count (s = 20)
13 = bit count (s = 20)
11 = bit count (s = 20)
Prime Number
1342007 and the bit count is 12 but should be 20
10 = bit count (s = 20)
10 = bit count (s = 20)
9 = bit count (s = 20)
13 = bit count (s = 20)
9 = bit count (s = 20)
14 = bit count (s = 20)
11 = bit count (s = 20)
9 = bit count (s = 20)
12 = bit count (s = 20)
12 = bit count (s = 20)
13 = bit count (s = 20)
10 = bit count (s = 20)
13 = bit count (s = 20)
10 = bit count (s = 20)
16 = bit count (s = 20)
10 = bit count (s = 20)
8 = bit count (s = 20)
9 = bit count (s = 20)
10 = bit count (s = 20)
12 = bit count (s = 20)
8 = bit count (s = 20)
11 = bit count (s = 20)
Prime Number
1103723 and the bit count is 12 but should be 20
16 = bit count (s = 20)
10 = bit count (s = 20)
Prime Number
1975187 and the bit count is 11 but should be 20
12 = bit count (s = 20)
11 = bit count (s = 20)
12 = bit count (s = 20)
Prime Number
1199039 and the bit count is 13 but should be 20
12 = bit count (s = 20)
11 = bit count (s = 20)
6 = bit count (s = 20)
9 = bit count (s = 20)
11 = bit count (s = 20)
10 = bit count (s = 20)
11 = bit count (s = 20)
11 = bit count (s = 20)
16 = bit count (s = 20)
12 = bit count (s = 20)
13 = bit count (s = 20)
13 = bit count (s = 20)
10 = bit count (s = 20)
6 = bit count (s = 20)
13 = bit count (s = 20)
12 = bit count (s = 20)
9 = bit count (s = 20)
15 = bit count (s = 20)
10 = bit count (s = 20)
13 = bit count (s = 20)
7 = bit count (s = 20)
13 = bit count (s = 20)
13 = bit count (s = 20)
16 = bit count (s = 20)
Prime Number
1900463 and the bit count is 17 but should be 20
11 = bit count (s = 20)
12 = bit count (s = 20)
11 = bit count (s = 20)
15 = bit count (s = 20)
Prime Number
2061287 and the bit count is 16 but should be 20
13 = bit count (s = 20)
11 = bit count (s = 20)
13 = bit count (s = 20)
10 = bit count (s = 20)
12 = bit count (s = 20)
15 = bit count (s = 20)
11 = bit count (s = 20)
9 = bit count (s = 20)
10 = bit count (s = 20)
8 = bit count (s = 20)
11 = bit count (s = 20)
14 = bit count (s = 20)
Prime Number
1926623 and the bit count is 15 but should be 20
9 = bit count (s = 20)
11 = bit count (s = 20)
13 = bit count (s = 20)
13 = bit count (s = 20)
11 = bit count (s = 20)
11 = bit count (s = 20)
11 = bit count (s = 20)
14 = bit count (s = 20)
11 = bit count (s = 20)
12 = bit count (s = 20)
12 = bit count (s = 20)
Prime Number
1914323 and the bit count is 13 but should be 20
What should I do?
Douglas
