programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Ron McLeod
• Tim Cooke
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• Junilu Lacar
• Rob Spoor
• Jeanne Boyarsky
Saloon Keepers:
• Stephan van Hulst
• Carey Brown
• Tim Holloway
• Piet Souris
Bartenders:

BigInteger Raised to the power of BigInteger

Greenhorn
Posts: 21
• Number of slices to send:
Optional 'thank-you' note:
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?

Marshal
Posts: 77564
372
• Number of slices to send:
Optional 'thank-you' note:
Welcome to JavaRanch

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!

Ranch Hand
Posts: 457
• Number of slices to send:
Optional 'thank-you' note:

lowercase baba
Posts: 13086
67
• Number of slices to send:
Optional 'thank-you' note:
Why wouldn't BigInteger's modpow() method work? just pass a 1 for the mod value.

Rancher
Posts: 4381
59
• Number of slices to send:
Optional 'thank-you' note:
Here's what I've done in the past. Should be fairly fast.

Sumayah Abdul
Greenhorn
Posts: 21
• Number of slices to send:
Optional 'thank-you' note:

Originally posted by Campbell Ritchie:
Welcome to JavaRanch

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
Greenhorn
Posts: 21
• Number of slices to send:
Optional 'thank-you' note:

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

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

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?

Sumayah Abdul
Greenhorn
Posts: 21
• Number of slices to send:
Optional 'thank-you' note:

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

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
Rancher
Posts: 4381
59
• Number of slices to send:
Optional 'thank-you' note:
[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
Greenhorn
Posts: 21
• Number of slices to send:
Optional 'thank-you' note:

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
Greenhorn
Posts: 21
• Number of slices to send:
Optional 'thank-you' note:
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
Marshal
Posts: 77564
372
• Number of slices to send:
Optional 'thank-you' note:

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
Greenhorn
Posts: 21
• Number of slices to send:
Optional 'thank-you' note:

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..

Sheriff
Posts: 67699
173
• Number of slices to send:
Optional 'thank-you' note: