I've been working on a method for exponentiating large BigIntegers and longs in Java. Here's the code I wrote:
```java
public BigInteger exp(long b, long e){
BigInteger a = new BigInteger("1");
BigInteger c = new BigInteger(Long.toString(b));
for (long i = 1; i <= e; i++){
a = a.multiply(c);
}
return a;
}
```
The issue arises because the exponent 'e' can be as large as 73136786415, and the base 'b' (which I also convert to c) can be similarly huge, like 31781653242. This makes the computation extremely slow, and I've waited 30 minutes just to see if anything happens.
I know the multiply function I'm using implements the karatsuba algorithm, which is somewhat faster, but I've also read about Discrete Fourier Transformation and its application in large number multiplication. However, I'm confused about how it works and how to apply it since it's typically only applicable for powers of two.
Does anyone have suggestions or different approaches for handling exponentiation more efficiently? I've been stuck trying to find a solution for hours!
1 Answer
Exponentiation with such large numbers can lead to huge results, so it's good to be cautious about performance. Have you thought about using the method of exponentiation by squaring? It drastically reduces the number of multiplications needed and is much faster for large exponents.
I really want to make this work for my RSA implementation, but now I'm doubting if it's even feasible given the size of the numbers. Thanks for the suggestion about squaring.