CODEWITHSUNDEEP
java
blejzz
blejzz

Reputation: 3349

java find a biginteger within specific range

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

Upvotes: 1

Views: 686

Answers (3)

Keith Randall
Keith Randall

Reputation: 23265

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.

Upvotes: 1

corgichu
corgichu

Reputation: 2600

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.

Upvotes: 0

assylias
assylias

Reputation: 328735

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.

Upvotes: 1

Related Questions