大数的模幂 [英] Modulus power of big numbers

问题描述

我正在尝试实现 SAFER+ 算法.该算法需要按如下方式求幂函数的模数:

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

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

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.

我如何执行此计算?

推荐答案

一些伪代码

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)    

这篇关于大数的模幂的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！