如果你看到这则信息,这表示下载可汗学院的外部资源时遇到困难.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

主要内容

模的指数

最后,让我们探讨指数属性
A^B mod C = ( (A mod C)^B ) mod C
通常我们需要计算 B值很大 A ^ B mod C 的值。
很遗憾的是,即使 B 并不大时, A^B 已经会非常大。

举例:

2^90 = 1,237,940,039,290,000,000,000,000,000
7^256 = 2,213,595,400,050,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 83,794,038,078,300,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 721,264,246,243,000,000,000,000,000
这些巨大的值导致我们的计算器和计算机返回 溢出错误
即使没有溢出,也需要 很长时间 来直接找到这些巨大数字的mod。

我们可以做些什么来减少所涉及的数量并使我们的计算更快呢?

假设我们要计算 2^90 mod 13,但我们的计算器无法容纳任何 大于 2^50 的数字。
这里有一个简单的 分而治之 策略:
较小的部分
指数运算法则
2^90 = 2^50 * 2^40
mod C
每个部分
2^50 mod 13 = 1125899906842624 mod 13 = 4
2^40 mod 13 = 1099511627776 mod 13 = 3
乘法特性
组合各部分
2^90 mod 13 = (2^50 * 2^40) mod 13
2^90 mod 13 = (2^50 mod 13 * 2^40 mod 13) mod 13
2^90 mod 13 = ( 4 * 3 ) mod 13
2^90 mod 13 = 12 mod 13
2^90 mod 13 = 12

如果B是2的幂,我们如何快速计算 A^B mod C ?

我们如何使用一个不能存储比7^10大的计算器来计算 7^256 mod 13
我们可以将 7^256 分成 25 个 7^101个 7^6,但这样分法并不十分有效。
还有更好的办法....

想加入讨论吗?

尚无帖子。
你会英语吗?单击此处查看更多可汗学院英文版的讨论.