HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

BigInteger prime testing

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
randomcodereviewprimesjavastackoverflow
bigintegerprimetesting

Problem

import java.math.BigInteger;
import java.util.Random;
public class Primetest {

    private static int size=15;
    private static Random r=new Random();
    private static BigInteger two=new BigInteger("2");
    private static BigInteger three=new BigInteger("3");
    public static void main(String[] args) {

        while(true)
        {
            BigInteger p=new BigInteger(size,r);
            if(isprime(p)==true)
            {
                System.out.println("prime="+p);
                break;
            }
        }
    }   

    public static boolean isprime(BigInteger n)
        {
             if(n.compareTo(BigInteger.ONE)==0 || n.compareTo(two)==0)
            {
                return true;
            }
          BigInteger half=n.divide(two);

           for(BigInteger i=three; i.compareTo(half)<=0;i=i.add(two))
            {

                if(n.mod(i).equals(BigInteger.ZERO))
                {
                  return false; 
                }

            }
             return true;

        }
 }


This code selects a random prime BigInteger number. I want a 2048 bit BigInteger prime number, but it only works with 15 bit. Can anybody help me?

Solution

Edit: Your code is working beyond 15 bits, it's just really slow..... More about that later.

I am not sure why your code does not work beyond 15-bit BigIntegers either.... it's not something daft like the fact you have size = 15, now, is it?

Two suggestions

Apart from that, there are two items that may interest you:

-
you can probably improve performance by using the two methods:

  • nextProbablePrime()



  • isProbablePrime()



With these methods you can check your candidate prime before you do the hard work... i.e. your first call in the isprime() method can be:

if (!n.isProbablePrime()) {
     return false;
}


Then, if it is probably a prime, you will need to check it, and you can do that in a way that may be faster with:

for(BigInteger i=three; i.compareTo(half)<=0;i=i.nextProbablePrime()) {
    ....
}


This may, or may not be faster. Check it.

-
What will be faster is if you only check to the square-root of n, instead of 'half'. BigInteger does not have a method square-root, but you can get an approximate limit quite fast with just a few iterations through the Babylonian method. You don't need to find the actual square-root, just some value that is slightly larger than the root. This will save many, many, many potential iterations for when the input value really is prime.

Test implementation

I have put together some example code which shows a few things:

  • your code is, in fact working....



  • when you have large numbers, your prime factoring guesses are going to pretty much take forever.... and I am not sure if forever-running code is working code...



  • It uses the faster isProbablyPrime(int) method to short-circuit the slow math.



  • It computes an approximate square-root of the input value.



  • It uses nextProbablePrime() instead of checking every odd number in the loop.



Note that I think your algorithm could also be optimized by changing the outer loop. If the goal is to find a large random number, then the better way to do it would be to choose a large number randomly, make sure it is odd, and then test it for prime-ness. If it is not prime, then keep adding 2 until the value is prime. This will significantly reduce the random hunting for prime values.

Here is the code:

private static int size = 1024;
private static Random r = new Random(1);
private static BigInteger two = new BigInteger("2");
private static BigInteger three = new BigInteger("3");

public static void main(String[] args) {

    while (true) {
        BigInteger p = new BigInteger(size, r);
        System.out.println("Processing prime " + p + " with input " + size
                + " bits");

        if (isprime(p) == true) {
            System.out.println("prime=" + p);
            break;
        }
    }
}

public static boolean isprime(BigInteger n) {

    if (!n.isProbablePrime(10)) {
        return false;
    }

    if (n.compareTo(BigInteger.ONE) == 0 || n.compareTo(two) == 0) {
        return true;
    }
    BigInteger root = appxRoot(n);
    System.out.println("Using approximate root " + root);

    int cnt = 0;
    for (BigInteger i = three; i.compareTo(root)  0) {
        half = half.shiftRight(1);
    }
    return half.shiftLeft(1);
}


And, here is the output

```
Processing prime 98329376886274465203040498066651959157640182809094020631664385777551847591123638109144698149095205744886312777380124671380640351550097713803874959847367838878126620008205910502904640512240477769179755530216157310355581410760731210073213721673064659778570224177036380289355437254781245378941806708640626915896 with input 1024 bits
Processing prime 37646605107187235792943122848905725816642680759921726391069038948580233504043310475106107937453362419670194263133240792533036542339813188374350574945196545621538046755833078747457686689427373500864049860688062396137214885740182673993779980005699518336257562987964318771232237070594662691795239179395907746381 with input 1024 bits
Processing prime 125205778308571596366364664578026315265996047681538536772575342694310454438809896771367811860534210488218628994364991251294455216205362342490618659150824104797110134588899854049460243713711039304748274575425927846133394573799688746650452867761117377057477970221094526444104587198668516522314203910650060775297 with input 1024 bits
Processing prime 29927154392784343780961536475173096429548596167420203155112563329853022850079385324824305227046118707802338722443720119949840770560558670171973682574167343679095711827324930773450204678598945005042160247713118600168856758838352856602314407651532633576632941646038272135258001495947267516367654449573770447978 with input 1024 bits
Processing prime 139243961902015178358905340711072637999780823861985238094201532190345570854225223205633490036395897038352240416702384303956261085630258304397095684303936086294128301544469715824139689002062508603332475411268227340511899314982630226967627021263463712185132048978641948260688280239972303621025851700017991795656 with input 1024 bits
Processing prime 1223

Code Snippets

if (!n.isProbablePrime()) {
     return false;
}
for(BigInteger i=three; i.compareTo(half)<=0;i=i.nextProbablePrime()) {
    ....
}
private static int size = 1024;
private static Random r = new Random(1);
private static BigInteger two = new BigInteger("2");
private static BigInteger three = new BigInteger("3");

public static void main(String[] args) {

    while (true) {
        BigInteger p = new BigInteger(size, r);
        System.out.println("Processing prime " + p + " with input " + size
                + " bits");

        if (isprime(p) == true) {
            System.out.println("prime=" + p);
            break;
        }
    }
}

public static boolean isprime(BigInteger n) {

    if (!n.isProbablePrime(10)) {
        return false;
    }

    if (n.compareTo(BigInteger.ONE) == 0 || n.compareTo(two) == 0) {
        return true;
    }
    BigInteger root = appxRoot(n);
    System.out.println("Using approximate root " + root);

    int cnt = 0;
    for (BigInteger i = three; i.compareTo(root) <= 0; i = i
            .nextProbablePrime()) {
        cnt++;
        if (cnt % 1000 == 0) {
            System.out.println(cnt + " Using next prime " + i);
        }
        if (n.mod(i).equals(BigInteger.ZERO)) {
            return false;
        }

    }
    return true;

}

private static BigInteger appxRoot(final BigInteger n) {
    BigInteger half = n.shiftRight(1);
    while (half.multiply(half).compareTo(n) > 0) {
        half = half.shiftRight(1);
    }
    return half.shiftLeft(1);
}
Processing prime 98329376886274465203040498066651959157640182809094020631664385777551847591123638109144698149095205744886312777380124671380640351550097713803874959847367838878126620008205910502904640512240477769179755530216157310355581410760731210073213721673064659778570224177036380289355437254781245378941806708640626915896 with input 1024 bits
Processing prime 37646605107187235792943122848905725816642680759921726391069038948580233504043310475106107937453362419670194263133240792533036542339813188374350574945196545621538046755833078747457686689427373500864049860688062396137214885740182673993779980005699518336257562987964318771232237070594662691795239179395907746381 with input 1024 bits
Processing prime 125205778308571596366364664578026315265996047681538536772575342694310454438809896771367811860534210488218628994364991251294455216205362342490618659150824104797110134588899854049460243713711039304748274575425927846133394573799688746650452867761117377057477970221094526444104587198668516522314203910650060775297 with input 1024 bits
Processing prime 29927154392784343780961536475173096429548596167420203155112563329853022850079385324824305227046118707802338722443720119949840770560558670171973682574167343679095711827324930773450204678598945005042160247713118600168856758838352856602314407651532633576632941646038272135258001495947267516367654449573770447978 with input 1024 bits
Processing prime 139243961902015178358905340711072637999780823861985238094201532190345570854225223205633490036395897038352240416702384303956261085630258304397095684303936086294128301544469715824139689002062508603332475411268227340511899314982630226967627021263463712185132048978641948260688280239972303621025851700017991795656 with input 1024 bits
Processing prime 122363695497135362876334096986750092237187818163935289528269643131788940948676195886148173694943587069178270471951802290191005226421476324835369279161430725594938044767129988205836293228618396536013056503441398180392306035348529131293104302985721904196513857471448257453900973803574632148674525698706255968469 with input 1024 bits
Processing prime 6766841734279494121695202528813564426876102386393672096192548380596947610679150306271345703101761193843898532659901726349258449119163161846636750914151571614552775446973414312295356121082306016346670297986250268817217032557516075488000173517339258842372202954513367225234606811784912645921661651252301210439 with input 1024 bits
Processing prime 1244168157289385582197158692756366939639032807157147509726417844315011285784938824776953893721289756574282393714469772808628985336160381884771437651533388861457165174027710304927221871555060351769769251837444763151883211741263529676654328058488380773866083064897587855677058477160609886235025932428799595897 with input 1024 bits
Processing prime 13215891658342429677398929252451811581509762342713411985623240377786331326941123025329750427546950327377955556185708764444989488503250802043768130163718442351723352879378431863711073199345973919511948968973
public static void main(String[] args) {

    BigInteger p = new BigInteger(size, r);
    if (testBit(0)) {
        p = p.add(BigInteger.ONE);
    }
    while (true) {
        System.out.println("Processing prime " + p + " with input " + size
                + " bits");

        if (isprime(p) == true) {
            System.out.println("prime=" + p);
            break;
        }
        p = p.add(TWO);
    }
}

Context

StackExchange Code Review Q#43490, answer score: 8

Revisions (0)

No revisions yet.