快速的方式来手动mod一些 [英] Fast way to manually mod a number

问题描述

我需要能够计算（一^ B）％C为一个非常大的价值和b（当您试图计算^ B那些单独地推极限，造成溢出错误）。对于足够小的数字，使用标识（一^ B）％C =（A％C）^ B％C的作品，但如果C太大这并不能真正帮助。我写了一个循环做模操作手动，一个是在一个时间：

I need to be able to calculate (a^b) % c for very large values of a and b (which individually are pushing limit and which cause overflow errors when you try to calculate a^b). For small enough numbers, using the identity (a^b)%c = (a%c)^b%c works, but if c is too large this doesn't really help. I wrote a loop to do the mod operation manually, one a at a time:

private static long no_Overflow_Mod(ulong num_base, ulong num_exponent, ulong mod) 
    {
        long answer = 1;
        for (int x = 0; x < num_exponent; x++)
        {
            answer = (answer * num_base) % mod;
        }
        return answer;
    }

，但这需要很长的时间。有没有简单快速的方法来做到这一点的操作，而不必实际拍摄到b的功率和不使用耗时的循环？如果一切都失败了，我可以做一个布尔数组来重新present一个巨大的数据类型，并找出如何与位运算符做到这一点，但必须有一个更好的办法。

but this takes a very long time. Is there any simple and fast way to do this operation without actually having to take a to the power of b AND without using time-consuming loops? If all else fails, I can make a bool array to represent a huge data type and figure out how to do this with bitwise operators, but there has to be a better way.

推荐答案

我猜你是不是想找：<一href="http://en.wikipedia.org/wiki/Montgomery_reduction">http://en.wikipedia.org/wiki/Montgomery_reduction 或者更简单的方法基于模幂（维基百科）

I guess you are looking for : http://en.wikipedia.org/wiki/Montgomery_reduction or the simpler way based on Modular Exponentiation (from wikipedia)

Bignum modpow(Bignum base, Bignum exponent, Bignum modulus) {

    Bignum result = 1;

    while (exponent > 0) {
        if ((exponent & 1) == 1) {
            // multiply in this bit's contribution while using modulus to keep result small
            result = (result * base) % modulus;
        }
        // move to the next bit of the exponent, square (and mod) the base accordingly
        exponent >>= 1;
        base = (base * base) % modulus;
    }

    return result;
}

这篇关于快速的方式来手动mod一些的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！