Skip to content
Advertisement

Is there a way to pow 2 BigInteger Numbers in java?

I have to pow a bigInteger number with another BigInteger number.

Unfortunately, only one BigInteger.pow(int) is allowed.

I have no clue on how I can solve this problem.

Advertisement

Answer

I have to pow a bigInteger number with another BigInteger number.

No, you don’t.

You read a crypto spec and it seemed to say that. But that’s not what it said; you didn’t read carefully enough. The mathematical ‘universe’ that the math in the paper / spec you’re reading operates in is different from normal math. It’s a modulo-space. All operations are implicitly performed modulo X, where X is some number the crypto algorithm explains.

You can do that just fine.

Alternatively, the spec is quite clear and says something like: C = (A^B) % M and you’ve broken that down in steps (… first, I must calculate A to the power of B. I’ll worry about what the % M part is all about later). That’s not how that works – you can’t lop that operation into parts. (A^B) % M is quite doable, and has its own efficient algorithm. (A^B) is simply not calculable without a few years worth of the planet’s entire energy and GDP output.

The reason I know that must be what you’ve been reading, is because (A ^ B) % M is a common operation in crypto. (Well, that, and the simple fact that A^B can’t be done).

Just to be crystal clear: When I say impossible, I mean it in the same way ‘travelling faster than the speed of light’ is impossible. It’s a law in the physics sense of the word: If you really just want to do A^B and not in a modspace where B is so large it doesn’t fit in an int, a computer cannot calculate it, and the result will be gigabytes large. int can hold about 9 digits worth. Just for fun, imagine doing X^Y where both X and Y are 20 digit numbers.

The result would have 10^21 digits.

That’s roughly equal to the total amount of disk space available worldwide. 10^12 is a terabyte. You’re asking to calculate a number where, forget about calculating it, merely storing it requires one thousand million harddisks each of 1TB.

Thus, I’m 100% certain that you do not want what you think you want.

TIP: If you can’t follow the math (which is quite bizarre; it’s not like you get modulo-space math in your basic AP math class!), generally rolling your own implementation of a crypto algorithm isn’t going to work out. The problem with crypto is, if you mess up, often a unit test cannot catch it. No; someone will hack your stuff and then you know, and that’s a high price to pay. Rely on experts to build the algorithm, spend your time ensuring the protocol is correct (which is still quite difficult to get right, don’t take that lightly!). If you insist, make dang sure you have a heap of plaintext+keys / encrypted (or plaintext / hashed, or whatever it is you’re doing) pairs to test against, and assume that whatever you wrote, even if it passes those tests, is still insecure because e.g. it is trivial to leak the key out of your algorithm using timing attacks.

User contributions licensed under: CC BY-SA
7 People found this is helpful
Advertisement