Tag: biginteger

How Java BigInteger nextProbablePrime method works?

I’m working with Java BigInteger Class and curious about the Algorithm behind nextProbablePrime method. I know about some efficient primality testing algorithm like Miller-Rabin but not sure about which algorithm was implemented here.

Trying the following code for a good time and still no response.

BigInteger number = BigInteger.ZERO;
number = number.setBit(82589933);
number = number.nextProbablePrime();

Solution:

I have gone through with the source code of BigInteger. It is internally using the MillerRabin algorithm for the nextProbablePrime method.

Convert byte array to BigInteger

My numbers are base 256 from left to right and represented in byte array. I would like to convert them to BigInteger such that below examples will work:

  • [5] -> 5
  • [200] -> 200
  • [0,1] -> 256
  • [100,2] -> 612

I came up with this solution:

    byte[] input = new byte[]{(byte) 200,2};
    BigInteger a = BigInteger.ZERO;
    BigInteger base = BigInteger.valueOf(256);
    for (int i = 0; i < input.length; i++) {
        a = a.add(BigInteger.valueOf(input[i] & 0xFF).multiply(base.pow(i)));
    }
    System.out.println(a);

While it works, it feels very inefficient. Is there a more efficient way of doing this?

Solution:

Easiest way to create a BigInteger from a byte array is to use the new BigInteger​(byte[] val) constructor:

Translates a byte array containing the two’s-complement binary representation of a BigInteger into a BigInteger. The input array is assumed to be in big-endian byte-order: the most significant byte is in the zeroth element.

Since your input array is in little-endian order, and you don’t want negative numbers returned, you need to reverse the bytes and ensure the first byte is 0-127, so the sign bit is not set. Easiest way to do that is to make the first byte 0.

Example: [2, 20, 200] -> [0, 200, 20, 2]

Here is the code for that:

private static BigInteger toBigInt(byte[] arr) {
    byte[] rev = new byte[arr.length + 1];
    for (int i = 0, j = arr.length; j > 0; i++, j--)
        rev[j] = arr[i];
    return new BigInteger(rev);
}

Test

byte[][] data = { {5},
                  {(byte)200},
                  {0,1},
                  {100,2} };
for (byte[] arr : data)
    System.out.println(toBigInt(arr));

Output

5
200
256
612