BigInteger prime testing

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:

1. your code is, in fact working....
2. 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...
3. It uses the faster isProbablyPrime(int) method to short-circuit the slow math.
4. It computes an approximate square-root of the input value.
5. 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; 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);
}

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 122363695497135362876334096986750092237187818163935289528269643131788940948676195886148173694943587069178270471951802290191005226421476324835369279161430725594938044767129988205836293228618396536013056503441398180392306035348529131293104302985721904196513857471448257453900973803574632148674525698706255968469 with input 1024 bits
Processing prime 6766841734279494121695202528813564426876102386393672096192548380596947610679150306271345703101761193843898532659901726349258449119163161846636750914151571614552775446973414312295356121082306016346670297986250268817217032557516075488000173517339258842372202954513367225234606811784912645921661651252301210439 with input 1024 bits
Processing prime 1244168157289385582197158692756366939639032807157147509726417844315011285784938824776953893721289756574282393714469772808628985336160381884771437651533388861457165174027710304927221871555060351769769251837444763151883211741263529676654328058488380773866083064897587855677058477160609886235025932428799595897 with input 1024 bits
Processing prime 132158916583424296773989292524518115815097623427134119856232403777863313269411230253297504275469503273779555561857087644449894885032508020437681301637184423517233528793784318637110731993459739195119489689739447166431101193405592878819600262595536763785155730768337651779977312858406291899622027075197339272533 with input 1024 bits
Processing prime 69992427855596672916046274609831358925004102231151217146504934042278719263838690406603474915165537361784459455893083094877744290705302384633321340170916902155546529977673369310451021181970658193490668498069273542381636608842630759935789234533400192866934709438808312038202012904797132388392567889891155748450 with input 1024 bits
Processing prime 21158035183654230873794938382538380103022588111151171726822340627470812338126036440129555658534288545561323627229661551179395796822536779689099195780624577722259563387380039125533382285521378162912552760478091032365155104156393389243223430957343814123541441495493412606366108994001798740793143149348566611849 with input 1024 bits
Processing prime 15252401507860116139044993701109820472568933087608994119874588139374351833868522812721998308899653583211533913737970680874956499213716249151797416323727562426289207703789447617206459217803392887453871279176965603731348358876019227478462392987492580262414905238078166067132705908043224132942658110708655117575 with input 1024 bits
Processing prime 79207591965644170299922757157810677225143754875497695785333916966745459024878221535386104794074683912029219571613935837926395463393267459748825400976839505450111313617312314479345019735666163348592463847785881480127339787201145529464779061029020193892147298882124349322947190382379671430079191833914102173464 with input 1024 bits
Processing prime 61030497376329633328073316647655267262303694060711488520514344109326325543945802124423073251577269169186781440230219553617205658081336472411027108746182826458446589150653587257149674878699689258298746835269894603933930803472419590290016677183062036325055276717300539131443014986954057041180792801863470921160 with input 1024 bits
Processing prime 169114037779361593124142841783629182425924353804019723914654438093025578377446888507229925252227113606029383048794273249003173542629081468619397107139204307145864334149929493619281837363125251731861465625382815511697458723930987915758447225669236647982784800507786813022174334313252476414285766502413871475837 with input 1024 bits
Using approximate root 25226202323750862638468707057345770204269264134797015774704159175996067529790533462300444165020098361223682946889361283140757213132269147109605325588573982
1000 Using next prime 7927
2000 Using next prime 17393
3000 Using next prime 27457
4000 Using next prime 37831

by my estimates, on my machine, it will probably take a few years to test all primes up to 25226202323750862638468707057345770204269264134797015774704159175996067529790533462300444165020098361223682946889361283140757213132269147109605325588573982 .... but, that is much faster than what it would to calculate all the primes up to half of the test value which is 169114037779361593124142841783629182425924353804019723914654438093025578377446888507229925252227113606029383048794273249003173542629081468619397107139204307145864334149929493619281837363125251731861465625382815511697458723930987915758447225669236647982784800507786813022174334313252476414285766502413871475837

If you follow my suggestion and loop to find primes using +2 instead of random, then your main method could be:

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);
    }
}

This is Code Review, so I will not try to find where it doesn't support 2048 bit BigIntegers, but I will tell you what I see in your code:

Naming Conventions

You should choose your names according to your language's naming conventions: Primetest should be PrimeTest, two should be TWO (see also below regarding proper variable scopes), isprime should be isPrime, etc...

Also refrain from single letter names for anything that you use for more than one line of code - r, n, etc.

Proper names

Variable names should clearly state their purpose half means the number 1/2, especially next to one and two. Actually it means half the input number. It is used as the max possible divisor, so call it that - maxDivisor.

Same goes for size - it should be MAX_BITS_RANGE (btw, what happens when you change its value to 2048?)

When things don't change

If you have data which does not change over time (like the number two) - making is static is good, making it a constant (static final) is better:

private static final int MAX_BITS_RANGE=15;
private static final Random GENERATOR=new Random();
private static final BigInteger TWO=new BigInteger("2");
private static final BigInteger THREE=new BigInteger("3");

Redundant code

if (isPrime(x) == true) is exactly the same as if (isPrime(x)).

Be consistent

In different places in your code you check equality either as n.compareTo(BigInteger.ONE)==0 or as n.mod(i).equals(BigInteger.ZERO) - choose one way - and stick to it.

*Adding @Marc-Andre's observation:

You should also be consistent with your indentations and braces locations. Although Oracle's suggestion is to put the opening brace at the end of the line,

while(true) {
}

not at the start of the next (my preference as well), other styles are also used (some more widely than others):

// Allman Style
while (true)
{
}

// Whitesmiths Style
while (true)
    {
    }

but you should choose one style and stick with it, to prevent reading errors, and general head-ache by code readers...

I can suggest you something that can reduce your isPrime code size drastically.

public static boolean isPrime(BigInteger n) {
    BigInteger lessOne = n.subtract(BigInteger.ONE);
    // get the next prime from one less than number and check with the number
    return lessOne.nextProbablePrime().compareTo(n) == 0;
}