This week's book giveaway is in the Mac OS forum.
We're giving away four copies of a choice of "Take Control of Upgrading to Yosemite" or "Take Control of Automating Your Mac" and have Joe Kissell on-line!
See this thread for details.
The moose likes Java in General and the fly likes BigInteger Raised to the power of BigInteger Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


JavaRanch » Java Forums » Java » Java in General
Bookmark "BigInteger Raised to the power of BigInteger" Watch "BigInteger Raised to the power of BigInteger" New topic
Author

BigInteger Raised to the power of BigInteger

Sumayah Abdul
Greenhorn

Joined: Nov 14, 2008
Posts: 21
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
Sheriff

Joined: Oct 13, 2005
Posts: 39098
    
  23
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
Ranch Hand

Joined: Nov 08, 2007
Posts: 457
Use Code Tags
Use Code Tags

Use Code Tags


Bill Shirley - bshirley - frazerbilt.com
if (Posts < 30) you.read( JavaRanchFAQ);
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11356
    
  16

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

Joined: Mar 05, 2008
Posts: 3018
    
  10
Here's what I've done in the past. Should be fairly fast.
Sumayah Abdul
Greenhorn

Joined: Nov 14, 2008
Posts: 21
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

Joined: Nov 14, 2008
Posts: 21
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?

thank you in advance.
your help is greatly appreciated..
Sumayah Abdul
Greenhorn

Joined: Nov 14, 2008
Posts: 21
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
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
[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

Joined: Nov 14, 2008
Posts: 21
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

Joined: Nov 14, 2008
Posts: 21
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
Sheriff

Joined: Oct 13, 2005
Posts: 39098
    
  23
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

Joined: Nov 14, 2008
Posts: 21
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
Author and ninkuma
Marshal

Joined: Jan 10, 2002
Posts: 61315
    
  66

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


[Asking smart questions] [Bear's FrontMan] [About Bear] [Books by Bear]
 
GeeCON Prague 2014
 
subject: BigInteger Raised to the power of BigInteger