形式的离散对数（2ⁿ-1）

Question

我需要找到（2 ⁿ-1）^k％M等于给定k的最小数字X。

这里的陷阱是n可以是一个非常大的数字，可能有10,000个数字，因此将被存储为字符串。我知道这通常是一个难题，但是在这种情况下，数字的特殊形式是否暗示任何使此操作更容易的属性？ M不一定是素数，但在10 [[8的合理范围内。

Answer 1

首先，您不能将值存储在字符串中，因为2

10000位数字远远大于宇宙中粒子的总数（10 ⁸⁰≈2 ^265.75）。如果将其存储为位，甚至没有足够的内存（事实上，这就是bigint库存储其数字的方式，没有好的库将值存储为字符）

所以您可以做的是使用modular exponentiation获取模。基本上，您使用(a * b) % M = ((a % M) * (b % M)) % M属性来避免计算有功功率值。许多语言已经对此提供了内置支持，例如Python pow function为此提供了一个可选的第三个参数，即pow。该实现与普通的pow(base, exp[, mod])完全相同，只是将pow替换为power *= base。 SO上有很多示例

modpow = (modpow * base) % M
• Calculating (a^b)%MOD
• Calculating pow(a,b) mod n

您不需要循环（2

n

-1）^k次。这实际上是不可能的，因为假设您每秒可以循环2 ³²次，那么您将需要2 ³²≈136年才能循环2 ⁶⁴次。想象一下需要多少个世纪才能计算出2 [10000。幸运的是，结果将在循环后重复出现，您只需要计算循环长度^{这些是需要的提示。您可以参考更接近您的问题的Calculate (a^b)%c where 0<=a,b,c<=10^18和how to calculate a^(b^c) mod n?}