快速手动修改数字的方法

Question

我需要能够为a和b的非常大的值计算(a ^ b)%c(它们分别是推动限制,当你尝试计算a ^ b时会导致溢出错误).对于足够小的数字,使用标识(a ^ b)%c =(a%c)^ b%c可以工作,但如果c太大,这实际上没有帮助.我写了一个循环来手动执行mod操作,一次一个:

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 AND的功能而不使用耗时的循环？如果所有其他方法都失败了,我可以创建一个bool数组来表示一个巨大的数据类型,并找出如何使用按位运算符来实现这一点,但必须有一个更好的方法.

Answer 1

我猜您正在寻找:http://en.wikipedia.org/wiki/Montgomery_reduction 或基于Modular Exponentiation的简单方法(来自维基百科)

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;
}

Answer 2

快速模块化指数(我认为这就是所谓的)可能有效.

Given a, b, c and a^b (mod c):

1. Write b as a sum of powers of 2. (If b=72, this is 2^6 + 2^3 )
2. Do:
    (1) a^2 (mod c) = a*
    (2) (a*)^2 (mod c) = a*
    (3) (a*)^2 (mod c) = a*
    ...
    (n) (a*)^2 (mod c) = a*

3. Using the a* from above, multiply the a* for the powers of 2 you identified. For example:
    b = 72, use a* at 3 and a* at 6.
    a*(3) x a*(6) (mod c)

4. Do the previous step one multiplication at a time and at the end, you'll have a^b % c.

现在,我不知道你将如何使用数据类型做到这一点.只要你的数据类型可以支持c ^ 2,我想你会没事的.

如果使用字符串,只需创建加,减,乘的字符串版本(不要太难).这种方法应该足够快.(你可以用mod c开始第1步,这样a就不会大于c).

编辑:哦,看看,Modular Exponentiation的维基页面.

Answer 3

除了编写自己的快速模幂运算之外，我能想到的最简单的想法是使用 F# BigInt 类型：Microsoft.FSharp.Math.Types.BigInt它支持任意大规模的运算 - 包括幂运算和模算术。

它是一种内置类型，将成为下一版本的完整 .NET 框架的一部分。您不需要使用 F# 来使用 BitInt - 您可以直接在 C# 中使用它。