# BigInteger Raised to the power of BigInteger

Sumayah Abdul

Greenhorn

Posts: 21

posted 8 years ago

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

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

Marshal

Posts: 52530

119

posted 8 years ago

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!

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

Ranch Hand

Posts: 457

posted 8 years ago

Bill Shirley - bshirley - frazerbilt.com

if (Posts < 30) you.read( JavaRanchFAQ);

posted 8 years ago

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

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

Mike Simmons

Ranch Hand

Posts: 3090

14

Sumayah Abdul

Greenhorn

Posts: 21

posted 8 years ago

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

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

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

Greenhorn

Posts: 21

posted 8 years ago

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?

thank you in advance.

your help is greatly appreciated..

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?

thank you in advance.

your help is greatly appreciated..

Sumayah Abdul

Greenhorn

Posts: 21

Mike Simmons

Ranch Hand

Posts: 3090

14

posted 8 years ago

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

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

[ November 14, 2008: Message edited 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 ]

Sumayah Abdul

Greenhorn

Posts: 21

posted 8 years ago

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.

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 actuallyneeda 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() doesexactlywhat 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

posted 8 years ago

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.

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: 52530

119

posted 8 years ago

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.

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

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

posted 8 years ago

Thank you Mr.Simmons.

Issue solved using Mod!

I can't thank you enough..

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 actuallyneeda 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() doesexactlywhat 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..