7

我需要能够为非常大的 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;
    }

但这需要很长时间。有没有任何简单快捷的方法来执行此操作，而无需实际使用 a 的 b AND 的幂而不使用耗时的循环？如果一切都失败了，我可以创建一个 bool 数组来表示一个巨大的数据类型，并弄清楚如何使用按位运算符来做到这一点，但必须有更好的方法。

4

11 回答 11

9

我猜您正在寻找：http ://en.wikipedia.org/wiki/Montgomery_reduction 或基于模幂的更简单方法（来自维基百科）

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;
}
于 2009-06-12T17:58:13.200 回答
6

快速模幂（我认为这就是所谓的）可能会起作用。

给定 a, b, c 和 a^b (mod c)：

1. 将 b 写为 2 的幂的和。（如果 b=72，则为 2^6 + 2^3 ）
2. 做：
    (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. 使用上面的 a*，将 a* 乘以您确定的 2 的幂。例如：
    b = 72，在 3 处使用 a*，在 6 处使用 a*。
    a*(3) xa*(6) (mod c)

4. 一次做上一步的乘法，最后得到 a^b % c。

现在，我不知道你将如何处理数据类型。只要您的数据类型可以支持 c^2，我认为您会没事的。

如果使用字符串，只需创建加法、减法和乘法的字符串版本（不太难）。这种方法应该足够快。（并且您可以通过 mod c 开始步骤 1，以便 a 永远不会大于 c）。

编辑：哦，看，关于Modular Exponentiation的维基页面。

于 2009-06-12T17:43:58.227 回答
4

这是 java 中快速模幂运算的示例（在较早的答案之一中建议）。将其转换为 C# 应该不会太难

http://www.math.umn.edu/~garrett/crypto/a01/FastPow.html

和源...

http://www.math.umn.edu/~garrett/crypto/a01/FastPow.java

于 2009-06-12T18:03:15.827 回答
2

Python 有 pow(a,b,c) ，它返回 (a**b)%c （只是更快），所以必须有一些聪明的方法来做到这一点。也许他们只是做你提到的身份。

于 2009-06-12T17:51:38.490 回答
1

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

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

于 2009-06-12T17:36:43.610 回答
1

我建议检查 Decimal 文档并查看它是否满足您的要求，因为它是内置类型并且可以使用 mod 运算符。如果没有，那么您将需要一个任意精度库，例如 java 的 Bignum。

于 2009-06-12T17:39:37.880 回答
1

你可以试试这个：

C#：对非常大的数（> Int64.MaxValue）进行模数（mod）运算
http://www.del337ed.com/blog/index.php/2009/02/04/c-doing-a-modulus- mod-operation-on-a-very-large-number-int64maxvalue/

于 2009-06-12T17:44:43.577 回答
1

您可以尝试将“a”分解为足够小的数字。

如果“a”的因子是“x”、“y”和“z”，那么

a^b = (x^b)(y^b)(z^b)。

然后你可以使用你的身份： (a^b)%c = (a%c)^b%c

于 2009-06-12T17:50:36.340 回答
1

在我看来，power 和 mod 之间似乎存在某种关系。幂只是重复乘法，而mod与除法有关。我们知道乘法和除法是相反的，所以通过这种联系，我假设幂和 mod 之间存在相关性。

例如，取 5 的幂：

5 % 4 = 1
25 % 4 = 1
125 % 4 = 1
625 % 4 = 1
...

模式很清楚，对于 b 的所有值，5 ^ b % 4 = 1。

在这种情况下不太清楚：

5 % 3 = 2
25 % 3 = 1
125 % 3 = 2
625 % 3 = 1
3125 % 3 = 2
15625 % 3 = 1
78125 % 3 = 2
...

但是还是有规律的。

如果你能计算出模式背后的数学，如果你能在不计算实际功率的情况下计算出 mod 的值，我不会感到惊讶。

于 2009-06-12T17:51:34.887 回答
0

你能分解a、b或c吗？C有一个已知的范围吗？

这些是 32 位整数！去看看这个网站

例如，这里是如何获得 n%d 的 mod where d 1>>s (1,2,4,8,...)

  int n = 137;     // numerator
  int d = 32;      // denom d will be one of: 1, 2, 4, 8, 16, 32, ...
  int m;           // m will be n % d
  m = n & (d - 1);

有 n%d 的代码，其中 d 是 1>>s - 1 (1, 3, 7, 15, 31, ...)

就像你说的那样，如果 c 很小，这只会真正有帮助。

于 2009-06-12T17:43:51.473 回答
-2

看起来像密码学的作业。

提示：查看费马小定理。

于 2009-06-12T17:52:18.190 回答