BigInteger Raised to the power of BigInteger

[Sumayah Abdul]

hello everyone,

I'm working on a crypto application using RSA so my whole application is based on the use of BigIntegers.

I reached a point where I need to calculate a bigInteger raised to the power of a bigInteger. unfortunately, this is not supported in the java bigInteger class.
I checked for codes to accomplish this and found one here in the forum with some errors. I fixed it to

private static BigInteger Square(BigInteger number)
{
System.err.println("Square:" + number.toString());
return number.multiply(number);
}

private static BigInteger Power(BigInteger a,BigInteger exponent)
{
System.err.println("Power");
if (exponent.equals(BigInteger.ONE)) return a;
else if (exponent.equals(BigInteger.ZERO)) return BigInteger.ONE;
else if (exponent.getLowestSetBit() != 0)
return Square(Power(a,exponent.divide(BigInteger.valueOf(2l))));
else
return a.multiply(Power(a,exponent.subtract(BigInteger.ONE)));
}

The code above ran ok for small numbers only.
I also tried using loops asin the following code

private static BigInteger Power (BigInteger M, BigInteger exp)
{
final BigInteger TWO = BigInteger.valueOf(2l);
BigInteger res = BigInteger.valueOf(1l);
BigInteger sq = M;
BigInteger[] qr; // holds quotient & remainder
BigInteger n = exp;

System.err.println("Power: before loop");
while (true) {
qr = n.divideAndRemainder(TWO);
if (qr[1].compareTo(BigInteger.valueOf(1l)) == 0)
res = res.multiply(sq);
n = qr[0];
if (n.compareTo(BigInteger.valueOf(0)) == 0) break;
sq = sq.multiply(sq);
}
System.err.println("Power: after loop");
return res;
}
it also ran ok for small numbers.

When I tested both functions for the large numbers that I have, it run ok for the first couple of iterations but then when it reached very large numbers it became too slow. I waited 30 minutes and it didn't finish so I stopped it.

Can someone help me here, please. is there anyway around it?

thank you in advance.
your help is greatly appreciated..

[Campbell Ritchie]

Welcome to JavaRanch

Please confirm that is your real name; you know about our naming policy.

Apart from using what looks like 21 when you probably mean 2L (please don't use a small l in long literals) I can't see anything wrong with your method. I think you are seeing normal behaviour. It is hardly surprising if it runs slowly; you try calculating 98765198951987984698749187619849516198795 to the power of 548787548794654979845987654694 quickly!

[Bill Shirley]

Use Code Tags
Use Code Tags

Use Code Tags

[fred rosenberger]

Why wouldn't BigInteger's modpow() method work? just pass a 1 for the mod value.

[Mike Simmons]

Here's what I've done in the past. Should be fairly fast.

public static BigInteger pow(BigInteger x, BigInteger y) {
  if (y.compareTo(BigInteger.ZERO) < 0)
    throw new IllegalArgumentException();
  BigInteger z = x; // z will successively become x^2, x^4, x^8, x^16, x^32...
  BigInteger result = BigInteger.ONE;
  byte[] bytes = y.toByteArray();
  for (int i = bytes.length - 1; i >= 0; i--) {
    byte bits = bytes[i];
    for (int j = 0; j < 8; j++) {
      if ((bits & 1) != 0)
        result = result.multiply(z);
      // short cut out if there are no more bits to handle:
      if ((bits >>= 1) == 0 && i == 0)
        return result;
      z = z.multiply(z);
    }
  }
  return result;
}

[Sumayah Abdul]

Originally posted by Campbell Ritchie:
Welcome to JavaRanch

Please confirm that is your real name; you know about our naming policy.

Apart from using what looks like 21 when you probably mean 2L (please don't use a small l in long literals) I can't see anything wrong with your method. I think you are seeing normal behaviour. It is hardly surprising if it runs slowly; you try calculating 98765198951987984698749187619849516198795 to the power of 548787548794654979845987654694 quickly!

My apologies, I didn't know about the nameing policy. but Yes, those are my initials.

no, its "2l". in small letters.

[Sumayah Abdul]

Originally posted by Bill Shirley:
Use Code Tags
Use Code Tags

Use Code Tags

I'm sorry, this is my first post here. I didn't know about the tags.
I checked for codes to accomplish this and found one here in the forum with some errors. I fixed it to

private static BigInteger Square(BigInteger number)
{
System.err.println("Square:" + number.toString());
return number.multiply(number);
}
 
private static BigInteger Power(BigInteger a,BigInteger exponent)
{
System.err.println("Power");
if (exponent.equals(BigInteger.ONE)) return a;
else if (exponent.equals(BigInteger.ZERO)) return BigInteger.ONE;
else if (exponent.getLowestSetBit() != 0) 
return Square(Power(a,exponent.divide(BigInteger.valueOf(2l))));
else 
return a.multiply(Power(a,exponent.subtract(BigInteger.ONE)));
}

The code above ran ok for small numbers only.
I also tried using loops asin the following code

private static BigInteger Power (BigInteger M, BigInteger exp)
{
final BigInteger TWO = BigInteger.valueOf(2l);
BigInteger res = BigInteger.valueOf(1l);
BigInteger sq = M;
BigInteger[] qr; // holds quotient & remainder 
BigInteger n = exp;
 
System.err.println("Power: before loop");
while (true) {
qr = n.divideAndRemainder(TWO);
if (qr[1].compareTo(BigInteger.valueOf(1l)) == 0) 
res = res.multiply(sq);
n = qr[0];
if (n.compareTo(BigInteger.valueOf(0)) == 0) break;
sq = sq.multiply(sq);
}
System.err.println("Power: after loop");
return res;
}

it also ran ok for small numbers.

When I tested both functions for the large numbers that I have, it run ok for the first couple of iterations but then when it reached very large numbers it became too slow. I waited 30 minutes and it didn't finish so I stopped it.

Can someone help me here, please. is there anyway around it?

thank you in advance.
your help is greatly appreciated..

[Sumayah Abdul]

Originally posted by Mike Simmons:
Here's what I've done in the past. Should be fairly fast.

public static BigInteger pow(BigInteger x, BigInteger y) {
  if (y.compareTo(BigInteger.ZERO) < 0)
    throw new IllegalArgumentException();
  BigInteger z = x; // z will successively become x^2, x^4, x^8, x^16, x^32...
  BigInteger result = BigInteger.ONE;
  byte[] bytes = y.toByteArray();
  for (int i = bytes.length - 1; i >= 0; i--) {
    byte bits = bytes[i];
    for (int j = 0; j < 8; j++) {
      if ((bits & 1) != 0)
        result = result.multiply(z);
      // short cut out if there are no more bits to handle:
      if ((bits >>= 1) == 0 && i == 0)
        return result;
      z = z.multiply(z);
    }
  }
  return result;
}

Thank you.
I'll try it and get back to you. Currently, I'm waiting for my current run to stop. its been going on for an hour now!

[Mike Simmons]

[fred]: Why wouldn't BigInteger's modpow() method work? just pass a 1 for the mod value.

I don't think mod 1 would work - that always returns 0. However you could use mod n where n is any number larger than the number you're modding.

However, SA: there's a big problem with the very idea of taking a BigInteger to a BigInteger power: memory. If you actually need a BigInteger for both those values (as opposed to a long), then the result is going to be very big indeed, and will require a huge amount of memory. (And also a fair amount of time to calculate all the digits, no matter how fast your algorithm.)

However, for the cryptography applications I'm aware of, you don't actually need to calculate the complete result - you just want a certain mod of the result. Basically, you usually want to retain a certain number of lower-order bits, and can afford to omit the higher ones. That allows you so save considerably on both time and memory. And that's exactly what modpow() does, efficiently. You could also modify mo own algorithm above to do this, modding results along the way. But I bet the modpow() version has already been written to be quite efficient. There's an excellent chance that modpow() does exactly what you really need here.
[ November 14, 2008: Message edited by: Mike Simmons ]

[Sumayah Abdul]

Originally posted by Mike Simmons:
[fred]: Why wouldn't BigInteger's modpow() method work? just pass a 1 for the mod value.

I don't think mod 1 would work - that always returns 0. However you could use mod n where n is any number larger than the number you're modding.

However, SA: there's a big problem with the very idea of taking a BigInteger to a BigInteger power: memory. If you actually need a BigInteger for both those values (as opposed to a long), then the result is going to be very big indeed, and will require a huge amount of memory. (And also a fair amount of time to calculate all the digits, no matter how fast your algorithm.)

However, for the cryptography applications I'm aware of, you don't actually need to calculate the complete result - you just want a certain mod of the result. Basically, you usually want to retain a certain number of lower-order bits, and can afford to omit the higher ones. That allows you so save considerably on both time and memory. And that's exactly what modpow() does, efficiently. You could also modify mo own algorithm above to do this, modding results along the way. But I bet the modpow() version has already been written to be quite efficient. There's an excellent chance that modpow() does exactly what you really need here.

[ November 14, 2008: Message edited by: Mike Simmons ]

Yes, ModPow is very efficient. I'm using it for some steps and its amazing.
I tried testing BigInteger.Pow(32000) but it has taking 3 hours and counting!. their code is similar to mine (i.e. squaring).

I'm following Shoup's protocol to implement Threshold Crypto and in the last step I need to calculate the power to a bigInteger. but you're right, I noticed many applications using Powmod to minimize the size but I don't understand how it works, wouldn't that change the result (plainText)?
where can I find any explanations regarding this issue?
If you can point me in the direction, I would be gratefull.

thank you.

[Sumayah Abdul]

I think I should use a precision arithmetic Library. unfortunately, I'll have to replace each occurrence of BigInteger in the code but if it solves the problem, I'm willing to give it a try.

I found a couple for Java, but can anyone suggest one in particular because performance is a priority for me.

Thank you.

[Campbell Ritchie]

Originally posted by SA AL:


My apologies, I didn't know about the nameing policy. but Yes, those are my initials.

no, its "2l". in small letters.

I am afraid initials are not acceptable. I shall have to ask you to go to "my profile" and alter your displayed name to match the naming policy.

The reason for not using 2l is that human readers may confuse it with 21. Always use 2L with a capital L to avoid such confusion.

[Sumayah Abdul]

Originally posted by Mike Simmons:
[fred]: Why wouldn't BigInteger's modpow() method work? just pass a 1 for the mod value.

I don't think mod 1 would work - that always returns 0. However you could use mod n where n is any number larger than the number you're modding.

However, SA: there's a big problem with the very idea of taking a BigInteger to a BigInteger power: memory. If you actually need a BigInteger for both those values (as opposed to a long), then the result is going to be very big indeed, and will require a huge amount of memory. (And also a fair amount of time to calculate all the digits, no matter how fast your algorithm.)

However, for the cryptography applications I'm aware of, you don't actually need to calculate the complete result - you just want a certain mod of the result. Basically, you usually want to retain a certain number of lower-order bits, and can afford to omit the higher ones. That allows you so save considerably on both time and memory. And that's exactly what modpow() does, efficiently. You could also modify mo own algorithm above to do this, modding results along the way. But I bet the modpow() version has already been written to be quite efficient. There's an excellent chance that modpow() does exactly what you really need here.

[ November 14, 2008: Message edited by: Mike Simmons ]

Thank you Mr.Simmons.

Issue solved using Mod!
I can't thank you enough..

[Bear Bibeault]

"Sumayah", please check your private messages for an important administrative matter.