大数的模幂

发布于 2024-12-18 06:48:21 字数 189 浏览 3 评论 0原文

我正在尝试实施 SAFER+ 算法。该算法需要找到幂函数的模，如下所示：

pow(45, x) mod 257

变量 x 是一个字节，因此范围可以从 0 到 255。因此，如果使用 32- 实现，幂函数的结果可能非常大，从而导致错误的值或 64 位整数。

我怎样才能进行这个计算？

原文

I am trying to implement the SAFER+ algorithm. The algorithm requires finding the modulus of a power function as follows:

pow(45, x) mod 257

The variable x is a byte, and thus can range from 0 to 255. Accordingly, the result of the power function can be VERY big resulting in incorrect values if implemented using 32- or 64-bit integers.

How can I perform this calculation?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

指尖凝香 2024-12-25 06:48:21

一些伪代码

function powermod(base, exponent, modulus) {
    if (base < 1 || exponent < 0 || modulus < 1)
        return -1

    result = 1;
    while (exponent > 0) {
       if ((exponent % 2) == 1) {
           result = (result * base) % modulus;
       }
       base = (base * base) % modulus;
       exponent = floor(exponent / 2);
    }
    return result;
}

和调用

powermod(45, x, 257)

some pseudo code

function powermod(base, exponent, modulus) {
    if (base < 1 || exponent < 0 || modulus < 1)
        return -1

    result = 1;
    while (exponent > 0) {
       if ((exponent % 2) == 1) {
           result = (result * base) % modulus;
       }
       base = (base * base) % modulus;
       exponent = floor(exponent / 2);
    }
    return result;
}

and call

powermod(45, x, 257)

回复收藏 0 原文

小嗷兮 2024-12-25 06:48:21

通过重复平方来执行求幂，每次运算后减少模数。这是一个非常标准的技术。

一个有效的示例：45^13 mod 257：

首先计算 45^2、45^4、45^8 mod 257：
45^2 模 257 = 2025 模 257 = 226
45^4 模 257 = 226^2 模 257 = 51076 模 257 = 190
45^8 mod 257 = 190^2 mod 257 = 36100 mod 257 = 120
然后使用 13 的二进制展开将它们组合起来得到结果：
45^13 模 257 = 45^1 * 45^4 * 45^8 模 257
45^13 模 257 = 45 * 190 * 120 模 257
45^13 模 257 = 8550 * 120 模 257
45^13 模 257 = 69 * 120 模 257
45^13 模 257 = 8280 模 257
45^13 mod 257 = 56

请注意，计算的中间结果永远不会大于 257*257，所以这个可以轻松地以 32 位整数类型执行。