Can't Generate Large Prime Numbers

Question

I'm trying to generate large prime numbers in Java. I use BigIntegers for this. Here is my code to generate and store 10 prime numbers inside an array.

    public static void primeGenerator() {
    BigInteger[] primeList = new BigInteger[10];
    BigInteger startLine = new BigInteger("10");
    int startPower = 6;
    BigInteger endLine = new BigInteger("10");
    int endPower = 9;
    int j = 0;
    for (BigInteger i = fastExp(startLine,startPower); 
            i.compareTo(fastExp(endLine,endPower)) <= 0; 
            i = i.add(BigInteger.ONE)) {
        if (checkPrimeFermat(i) == true && j < 10) {
            primeList[j] = i;
            j++;
        }
    }

    System.out.println(primeList[0]);
    System.out.println(primeList[1]);
    System.out.println(primeList[2]);
    System.out.println(primeList[3]);
    System.out.println(primeList[4]);
    System.out.println(primeList[5]);
    System.out.println(primeList[6]);
    System.out.println(primeList[7]);
    System.out.println(primeList[8]);
    System.out.println(primeList[9]);


}

I wrote my own fastExp function to generate numbers faster. Here are my other functions.

public static BigInteger getRandomFermatBase(BigInteger n)
    {
        Random rand = new Random();

        while (true)
        {
            BigInteger a = new BigInteger (n.bitLength(), rand);

            if (BigInteger.ONE.compareTo(a) <= 0 && a.compareTo(n) < 0)
            {
                return a;
            }
        }
    }

    public static boolean checkPrimeFermat(BigInteger n)
    {
        if (n.equals(BigInteger.ONE))
            return false;

        for (int i = 0; i < 10; i++)
        {
            BigInteger a = getRandomFermatBase(n);
            a = a.modPow(n.subtract(BigInteger.ONE), n);

            if (!a.equals(BigInteger.ONE))
                return false;
        }

        return true;
    }
    public static void main(String[] args) throws IOException 
    {
        primeGenerator();



        }

       public static BigInteger fastExp (BigInteger x, int n){
            BigInteger result=x;
            int pow2=powof2leN(n);
            int residue= n-pow2;
            for(int i=1; i<pow2 ; i=i*2){
                result=result.multiply(result);
                }
            for(int i=0 ; i<residue; i++){
                result=result.multiply(x);          
            }
            return result;

        }

        private static int powof2leN(int n) {
            for(int i=1; i<=n; i=i*2){
                if(i*2>2)
                    return 1;
            }
            return 0;
        }    

}

So the problem is when I try it with small numbers (for example startPower=3, endPower=5) it generates and prints prime numbers. But when I try it with big numbers (for example startPower=5, endPower=7) it doesn't generate anything. How can I improve my code to work with large numbers?

Thank you

Answer 1

First of all, I would like to point out that you did not write this code. You stole it from here and claimed that you wrote it, which is incredibly unethical.

---

The code is correct. It's just slow. As you increase the power, the code takes increasingly longer. There are two reasons why this occurs:

1. The Fermat test takes increasingly longer to apply.
2. BigInteger operations take increasingly longer to execute.

The Fermat test grows like O(k × log2n × log log n × log log log n). BigInteger's addition and subtraction grow like O(n). Obviously, BigInteger is what is slowing you down.

Below is a profile of your code with the power set from 5 to 7.

If you want your code to produce larger and larger primes, you should focus on reducing the number of operations you do on BigIntegers. Here is one such improvement:

• Take n.subtract(BigInteger.ONE) outside of your for loop. The result does not need to be calculated many times.

Further suggestions will have to come from the Mathematics folks over on Mathematics Stack Exchange.

Answer 2

Here is a much simpler solution for finding large primes -

BigInteger big = new BigInteger("9001");//or whatever big number you want to start with
BigInteger[] primes = new BigInteger[10];
for(int i=0;i<10;i++){
    primes[i]=big=big.nextProbablePrime();
}

It has some limitations outlined here, but based on your code it should be more than enough.

Answer 3

you can use BigInteger(int bitLength, int certainty, Random rnd) constructor

BigInteger b= new BigInteger(20, 1, new Random());

It will generate a prime number for you. bitLength specifies the number of digits you want in your BigInteger, certainity specifies the amount of certainity you want that your BigInteger should be prime.