How would I implement an efficient powers method in java

Question

Say someone is doing encryption, and it requires the use of numbers greater than the max value of long, so I need the ability to do something just as quickly (as in few steps) and efficiently as possible. take this example. I need to take (65^17) % LARGENUMBER, and so I decided to use the 65^17 part like below:

65^17=65(((65^2)^2)^2)^2. (please forgive my formatting, I dont know how to do it for this equation)

Now, I have a question about what I chose. how, per say, would I implement that into a Java code line? would it just be a for loop such as:

int fin = 65;
int times = 17/2;
int extra = 17 % 2;
for(int i = 0; i < times; i++){
    ...code...
}

and then what would be in the code? would it just be:

fin = (fin * 65) % LONGNUMBER;

would that even work? or what would I change about this to make it work? This is all theory by the way.

Thanks for the help, in advance :)

Answer 1

Java's java.math.BigInteger class has a modPow method to perform modular exponentiation. Does that do what you want?

If you want to do it yourself, here is pseudocode for the "square-and-multiply" algorithm, which I will leave to you to translate into Java with appropriate datatypes:

function modPow(base, exp, mod)
    x := 1
    while exp > 0
        if exp % 2 == 1
            x := (x * base) % mod
        base := (base * base) % mod
        exp := exp // 2 # integer division
    return x