java - 我将如何在java中实现有效的powers方法

Question

假设有人正在进行加密，并且需要使用大于 long 最大值的数字，因此我需要能够快速(只需几个步骤)高效地完成某些操作尽可能。以这个例子为例。我需要采用 (65^17) % LARGENUMBER，因此我决定使用 65^17 部分，如下所示:

65^17=65(((65^2)^2)^2)^2。 (请原谅我的格式，我不知道如何计算这个方程)

现在，我对我的选择有疑问。也就是说，我如何将其实现到 Java 代码行中？它只是一个 for 循环吗，例如:

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

然后代码中会包含什么？难道只是:

fin = (fin * 65) % LONGNUMBER;

这还能用吗？或者我要对此进行哪些更改才能使其发挥作用？顺便说一句，这都是理论。

提前感谢您的帮助:)

Answer 1

Java 的 java.math.BigInteger 类有一个 modPow 方法来执行模幂运算。这符合你的要求吗？

如果你想自己做，这里是“平方乘法”的伪代码 algorithm ，我将让您将其转换为具有适当数据类型的 Java:

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