快速手动修改数字的方法

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:

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

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.

但这需要很长时间。是否有任何简单快速的方法来执行此操作,而无需实际使用b AND的功能而不使用耗时的循环?如果所有其他方法都失败了,我可以创建一个bool数组来表示一个巨大的数据类型,并找出如何使用按位运算符来实现这一点,但必须有一个更好的方法。

11 个解决方案

#1

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

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

#2

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.

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

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).

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

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

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

#3

Here's an example of Fast Modular Exponentiation (suggested in one of the earlier answers) in java. Shouldn't be too hard to convert that to C#

这是java中Fast Modular Exponentiation(在早期答案之一中提出)的一个例子。不应该太难将其转换为C#

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

and the source...

和来源......

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

#4

Python has pow(a,b,c) which returns (a**b)%c (only faster), so there must be some clever way to do this. Maybe they just do the identity you mentioned.

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

#5

I'd recommend checking over the Decimal documentation and seeing if it meets your requirements since it is a built in type and can use the mod operator. If not then you're going to need an arbitrary precision library like java's Bignum.

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

#6

You can try factoring 'a' into sufficiently small numbers.

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

If the factors of 'a' are 'x', 'y', and 'z', then

如果'a'的因子是'x','y'和'z',那么

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

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

Then you can use your identity: (a^b)%c = (a%c)^b%c

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

#7

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.

在我看来,功率和mod之间存在某种关系。权力只是重复乘法,而mod与分裂有关。我们知道乘法和除法是相反的,所以通过这种连接我会假设幂和mod之间存在相关性。

For example, take powers of 5:

例如,取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.

对于b的所有值,模式清楚地表明5 ^ b%4 = 1。

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.

如果你可以计算模式背后的数学,如果你能在没有实际功率的情况下弄清楚mod的值,我不会感到惊讶。

#8

You could try this:

你可以试试这个:

C#: Doing a modulus (mod) operation on a very large number (> Int64.MaxValue)
http://www.del337ed.com/blog/index.php/2009/02/04/c-doing-a-modulus-mod-operation-on-a-very-large-number-int64maxvalue/

C#:对非常大的数字(> Int64.MaxValue)进行模数(mod)运算http://www.del337ed.com/blog/index.php/2009/02/04/c-doing-a-modulus- MOD-操作上-A-超大型用户号码int64maxvalue /

#9

Short of writing your own fast modular exponentiation, the simplest idea I can come up with, is to use the F# BigInt type: Microsoft.FSharp.Math.Types.BigInt which supports operations with arbitrarily large scale - including exponentiation and modular arithmetic.

如果没有编写自己的快速模幂运算,我可以提出的最简单的想法是使用F#BigInt类型:Microsoft.FSharp.Math.Types.BigInt,它支持任意大规模的操作 - 包括取幂和模运算。

It's a built-in type that will be part of the full .NET framework with the next release. You don't need to use F# to use BitInt - you can make use of it directly in C#.

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

#10

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

你可以考虑a,b或c吗? C是否具有已知范围?

These are 32 bit integers! Go check this site

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

For instance, here is how you get the mod of n%d where d 1>>s (1,2,4,8,...)

例如,这里是你如何得到n%d的mod,其中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, ...)

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

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

如果c很小,这只会真的有用,就像你说的那样。

#11

Looks like homework in cryptography.

看起来像密码学中的家庭作业。

Hint: check out Fermat's little theorem.

提示:查看费马的小定理。

#1