java find a biginteger within specific range

Question

Im developing an application with java which needs to find two big integers (Y and Z) that meet this two conditions:

Y^k < N  and Z^j < N < Z^(j+1)

N, k and j are known. N is a big integer(1024bit).

My current implementations finds Y and Z by choosing a random BigInteger and tests if the conditions are met. But the problem is that sometimes it takes really long to find the solution or it doesn't find one at all (probably the bitSize isn't correctly computed). Is there any way i could speed this up?

The code:

BigInteger getMessage(int bitSize, int lowerBound, int upperBound, BigInteger module)
{
        boolean foundOne = false;
        BigInteger candidate = null;
        while( !foundOne )
        {
                candidate = new BigInteger(bitSize,random);
                foundOne = (upperBound == 0 || candidate.pow(upperBound).compareTo(module) > 0 ) && (lowerBound == 0 || candidate.pow(lowerBound).compareTo(module) < 0);
        }

        return candidate;
}

score 1 · Answer 1 · edited May 23 '17 at 12:20

One way is to solve the equation directly by taking the logarithm of your expressions:

   k * log (Y) < log (N)
=> log (Y) < log (N) / k

   j * log (Z) < log (N) < (j + 1) * log (Z)
=> log (Z) < log (N) / j AND log (Z) > log (N) / (j + 1)

Once you have determined a value for log(Y) and log(Z), you can take the exponential (for neperian log or power of 10 for log10) of your result to get back to Y and Z.

You can read here about various ways of calculating the log of a BigInteger. It seems sensible to run the calculation on BigDecimal, then round (up or down) to BigInteger and check that it works.

score 1 · Accepted Answer · answered Sep 05 '12 at 23:06

1

Use binary search. For instance, to find Z, start with Zmin=0 and Zmax=N. Compute Zmid = (Zmin+Zmax)/2, then compare Zmid^j versus N. if Zmin^j < N, then set Zmin=Zmid. Otherwise, set Zmax=Zmid. Eventually you'll narrow down to the correct Z in O(log(N)) time.

answered Sep 05 '12 at 23:06

Keith Randall

22,985
2
35
54

i have failed to mention that i need several solutions. how could i modify binary search so i dont get the same solution all the time? – blejzz Sep 05 '12 at 23:17
1

You can search for the maximum possible solution of `Z^j – Keith Randall Sep 05 '12 at 23:20

score 0 · Answer 3 · answered Sep 05 '12 at 22:47

0

Don't make it random, make an adjustment to your current guess depending on its relation to the specifications you want to match.

For example, start with n = N/2.

If n^j > N, then lower n by some amount.

If n^j < N, then check n^(j+1) > N.

If n^(j+1) < N, then increase n by some amount.

Etc.

answered Sep 05 '12 at 22:47

corgichu

2,580
3
32
46

the numbers are quite big (1024 bit at least), (de)incrementing by 1 would probably take a long time. – blejzz Sep 05 '12 at 22:52
then don't decrement by 1, divide/multiply by 1000 or more, then decrease as you get more precise. – corgichu Sep 05 '12 at 22:54

java find a biginteger within specific range

3 Answers3