大数模数电源 [英] 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.

我如何才能执行此计算？

How can I perform this calculation?

推荐答案

一些伪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;
}

和通话

powermod(45, x, 257)    

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