blocks|key|1569901|text|如果您使用的是.NET+4，我建议您查看BigInteger，它甚至提供了在单个操作中完成所有操作的ModPow方法:)|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1569902|BigInteger+n+=+...;
BigInteger+p+=+...;
BigInteger+q+=+...;
BigInteger+x+=+BigInteger.ModPow(n,+p,+q);|code-block|syntax|javascript|1569903|entityMap|0|LINK|mutability|MUTABLE|url|http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.aspx|1|http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.modpow.aspx^0|K|A|1E|6|K|A|0|1E|6|1|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@$9|V|A|W|B|C]|$9|X|A|Y|B|C]]|D|@$9|Z|A|10|1|11]|$9|12|A|13|1|14]]|E|$]]|$1|F|3|G|5|H|7|15|8|@]|D|@]|E|$I|J]]|$1|K|3|-4|5|6|7|16|8|@]|D|@]|E|$]]]|L|$M|$5|N|O|P|E|$Q|R]]|S|$5|N|O|P|E|$Q|T]]]]

If you're using .NET 4, I suggest you look at <a href="http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.aspx"><code>BigInteger</code></a>, which even provides the <a href="http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.modpow.aspx"><code>ModPow</code></a> method to do it all in a single operation :)

<pre><code>BigInteger n = ...;
BigInteger p = ...;
BigInteger q = ...;
BigInteger x = BigInteger.ModPow(n, p, q);
</code></pre>

blocks|key|3636900|text|这就是所谓的powermod+function|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|3636901|function+modular_pow(base,+exponent,+modulus)
++++c+:=+1
++++for+e_prime+=+1+to+exponent+
++++++++c+:=+(c+*+base)+mod+modulus
++++return+c|code-block|syntax|javascript|3636902|这可以通过平方应用指数来提高效率：|3636903|function+modular_pow(base,+exponent,+modulus)
++++result+:=+1
++++while+exponent+>+0
++++++++if+(exponent+&+1)+equals+1:
+++++++++++result+=+(result+*+base)+mod+modulus
++++++++exponent+:=+exponent+>>+1
++++++++base+=+(base+*+base)+mod+modulus
++++return+result|3636904|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Modular_exponentiation^0|6|H|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@$A|V|B|W|1|X]]|C|$]]|$1|D|3|E|5|F|7|Y|8|@]|9|@]|C|$G|H]]|$1|I|3|J|5|6|7|Z|8|@]|9|@]|C|$]]|$1|K|3|L|5|F|7|10|8|@]|9|@]|C|$G|H]]|$1|M|3|-4|5|6|7|11|8|@]|9|@]|C|$]]]|N|$O|$5|P|Q|R|C|$S|T]]]]

This is known as the <a href="http://en.wikipedia.org/wiki/Modular_exponentiation">powermod function</a>:

<pre><code>function modular_pow(base, exponent, modulus)
 c := 1
 for e_prime = 1 to exponent 
 c := (c * base) mod modulus
 return c
</code></pre>

This can be made more efficient by applying exponentiation by squaring:

<pre><code>function modular_pow(base, exponent, modulus)
 result := 1
 while exponent &gt; 0
 if (exponent &amp; 1) equals 1:
 result = (result * base) mod modulus
 exponent := exponent &gt;&gt; 1
 base = (base * base) mod modulus
 return result
</code></pre>

blocks|key|5237037|text|请查看此topic和此article，了解如何提高数学函数本身的效率。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|5237038|entityMap|0|LINK|mutability|MUTABLE|url|http://www.physicsforums.com/showthread.php?t=159418|1|http://excel.tips.net/Pages/T003302_Large_Numbers_in_the_MOD_Function.html^0|4|5|0|B|7|1|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]|$A|R|B|S|1|T]]|C|$]]|$1|D|3|-4|5|6|7|U|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]|L|$5|G|H|I|C|$J|M]]]]

Please check this <a href="http://www.physicsforums.com/showthread.php?t=159418" rel="nofollow">topic</a> and this <a href="http://excel.tips.net/Pages/T003302_Large_Numbers_in_the_MOD_Function.html" rel="nofollow">article</a> on ways to make the mathematical function more efficient in itself.

blocks|key|5237655|text|琐碎的..。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|5237656|x+=+1
for(i+=+0;+i+<+p;+i%2B%2B)
+++x+=+(x*n)+%25+q|code-block|syntax|javascript|5237657|还有更有效的方法，比如二进制求幂，而不是这种朴素的迭代，但这确实克服了溢出问题，因为x由n*q限定|5237658|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

Trivially...

<pre><code>x = 1
for(i = 0; i &lt; p; i++)
 x = (x*n) % q
</code></pre>

Theres more efficient ways such as binary exponentiation rather than this naive iteration, but this does get past the overflow problem as x is bounded by n*q

blocks|key|3636936|text|参见BigInteger.ModPow+(Fx+4%2B)，这里是MSDN。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|3636937|entityMap|0|LINK|mutability|MUTABLE|url|http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.modpow.aspx^0|2|H|V|4|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@$9|O|A|P|B|C]]|D|@$9|Q|A|R|1|S]]|E|$]]|$1|F|3|-4|5|6|7|T|8|@]|D|@]|E|$]]]|G|$H|$5|I|J|K|E|$L|M]]]]

See <code>BigInteger.ModPow</code> (Fx 4+), here is the <a href="http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.modpow.aspx" rel="nofollow">MSDN</a>.

blocks|key|1570231|text|如果您计划编写自己版本的Modpow()|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1570232|1570233|您只需要幂模数q，因此您的计算不需要使用任何大于q%5E2的数字，使用的事实是：|1570234|if+a+=+b+(mod+q)+then+a*p+=+b*p+(mod+q)|code-block|syntax|javascript|1570235|因此，当计算幂n%5Ep时，在每次乘法之后，对工作变量进行(模q)运算。|1570236|1570237|此外，如果Q是质数，你可以使用费马小定理，它说明：|1570238|a%5E(q-1)+=+1+(mod+q)
++++(when+a+is+not+a+multiple+of+q)|1570239|当p比q大得多时，这可以用来缩短计算量|1570240|entityMap^0|C|8|0|0|O|3|0|0|7|3|0|0|0|0|1|1|3|1|0^^$0|@$1|2|3|4|5|6|7|Y|8|@$9|Z|A|10|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|11|8|@]|D|@]|E|$]]|$1|G|3|H|5|6|7|12|8|@$9|13|A|14|B|C]]|D|@]|E|$]]|$1|I|3|J|5|K|7|15|8|@]|D|@]|E|$L|M]]|$1|N|3|O|5|6|7|16|8|@$9|17|A|18|B|C]]|D|@]|E|$]]|$1|P|3|-4|5|6|7|19|8|@]|D|@]|E|$]]|$1|Q|3|R|5|6|7|1A|8|@]|D|@]|E|$]]|$1|S|3|T|5|K|7|1B|8|@]|D|@]|E|$L|M]]|$1|U|3|V|5|6|7|1C|8|@$9|1D|A|1E|B|C]|$9|1F|A|1G|B|C]]|D|@]|E|$]]|$1|W|3|-4|5|6|7|1H|8|@]|D|@]|E|$]]]|X|$]]

If you plan to write your own version of <code>Modpow()</code>:

<hr>

You only need the power modulo q, so your calculations don't need to use any number bigger than <code>q^2</code>, using the fact that:

<pre><code>if a = b (mod q) then a*p = b*p (mod q)
</code></pre>

Therefore, when calculating the power <code>n^p</code>, after every multiplication, do a (modulo q) operation on your working variable. 

<hr>

Additionally, if q is prime, you can use Fermat's little theorem, which states that:

<pre><code>a^(q-1) = 1 (mod q)
 (when a is not a multiple of q)
</code></pre>

This can be used to shorten the calculations when <code>p</code> is (much) bigger than <code>q</code>

blocks|key|2135733|text|虽然这里提供的所有答案都是正确的，但我遗漏了显而易见的平方乘法算法，这是实现模幂运算的“经典”方法。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2135734|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Although all the answers provided here are correct I mis the obvious square-and-multiply algorithm, which is the "classic" way to implement modular exponentiation.

I want to calculate the RSA algorithm by myself . I need to calculate the modulus of a number at a certain power. The thing is that that number at that certain power can get quite big. 

Here is what i want :

<pre><code>x = pow(n, p) % q
</code></pre>

How can I efficiently determine x?

Calculate the modulus of a number at a certan power (the number at that power is quite big)

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我想自己计算RSA算法。我需要计算一个数的某一幂的模数。问题是，在一定的功率下，这个数字可能会变得相当大。这是我想要的：x = pow(n, p) % q如何有效地确定x？

问计算一个数在一定幂上的模数(这个幂上的数很大)
EN

回答 7

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算一个数在一定幂上的模数(这个幂上的数很大)EN

回答 7

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算一个数在一定幂上的模数(这个幂上的数很大)
EN