手动修改数字的快速方法

发布于 2024-07-24 09:26:50 字数 588 浏览 4 评论 0原文

我需要能够计算 (a^b) % c 对于非常大的 a 和 b 值（它们分别推动限制，当您尝试计算 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 数组来表示一个巨大的数据类型，并弄清楚如何使用按位运算符来做到这一点，但必须有更好的方法。

原文

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

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.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

扶醉桌前 2024-07-31 09:26:50

我猜您正在寻找：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;
}

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

回复收藏 0 原文

谁对谁错谁最难过 2024-07-31 09:26:50

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

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）。

编辑：哦，看，模幂上的 wiki 页面。

Fast Modular Exponentiation (I think that's what it's called) might work.

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.

Now, how you're going to do that with data types, I don't know. As long as your datatype can support c^2, i think you'll be fine.

If using strings, just create string versions of add, subtract, and multiply (not too hard). This method should be quick enough doing that. (and you can start step 1 by a mod c so that a is never greater than c).

EDIT: Oh look, a wiki page on Modular Exponentiation.

回复收藏 0 原文

笔芯 2024-07-31 09:26:50

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

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

和来源...

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

回复收藏 0 原文

凉墨 2024-07-31 09:26:50

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

回复收藏 0 原文

如果没结果 2024-07-31 09:26:50

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

回复收藏 0 原文

最美不过初阳 2024-07-31 09:26:50

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

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

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

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

回复收藏 0 原文

海夕 2024-07-31 09:26:50

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

例如，取 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 的值，我不会感到惊讶。

It seems to me like there's some kind of relation between power and mod. Power is just repeated multiplication and mod is related to division. We know that multiplication and division are inverses, so through that connection I would assume there's a correlation between power and mod.

For example, take powers of 5:

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

The pattern is clear that 5 ^ b % 4 = 1 for all values of b.

It's less clear in this situation:

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

But there's still a pattern.

If you could work out the math behind the patterns, I wouldn't be surprised if you could figure out the value of the mod without doing the actual power.

回复收藏 0 原文

何处潇湘 2024-07-31 09:26:50

您可以尝试以下操作：

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

回复收藏 0 原文

绿阴红影里的.如风往事 2024-07-31 09:26:50

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

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

回复收藏 0 原文

感性不性感 2024-07-31 09:26:50

你能因式分解 a、b 或 c 吗？ C 是否有已知范围？

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

例如，这里是如何获取 mod n%d 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 很小的情况下才会真正有帮助，就像你说的那样。

Can you factor a, b, or c? Does C have a known range?

These are 32 bit integers! Go check this site

For instance, here is how you get the mod of n%d 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);

There is code for n%d where d is 1>>s - 1 (1, 3, 7, 15, 31, ...)

This is only going to really help if c is small though, like you said.

回复收藏 0 原文