主要内容
模的指数
最后，让我们探讨指数属性：
A^B mod C = ( (A mod C)^B ) mod C
通常我们需要计算 B值很大 时 A ^ B mod C 的值。
很遗憾的是，即使 B 并不大时， A^B 已经会非常大。
很遗憾的是，即使 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。
即使没有溢出，也需要 很长时间 来直接找到这些巨大数字的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^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
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^10 和 1个 7^6，但这样分法并不十分有效。
还有更好的办法....