计算的最佳方法((2 ^ n)-1)mod p

Question

我正在进行加密练习,我正在尝试计算(2 ⁿ -1)mod p,其中p是素数

这样做的最佳方法是什么？我正在使用C,因此当n很大时,2 ⁿ -1变得太大而无法保持

我遇到了等式(a*b)modp =(a(bmodp))modp,但我不确定这适用于这种情况,因为2 ⁿ -1可能是素数(或者我不知道如何分解这个)

非常感谢.

Answer 1

一些提示可以帮助您找到更好的方法:

1. 不要使用(a*b)modp =(a(bmodp))modp来计算2 ⁿ -1 mod p,用它来计算2 ⁿ mod p然后再减去它.
2. 费马的小定理在这里很有用.这样,你实际需要处理的指数不会超过p.

Answer 2

您在评论中提到 和n是p9 或 10 位数字，或者其他数字。如果将它们限制为 32 位 ( unsigned long) 值，则可以2^n mod p使用简单的（二进制）模幂求出：

unsigned long long u = 1, w = 2;

while (n != 0)
{
    if ((n & 0x1) != 0)
        u = (u * w) % p; /* (mul-rdx) */

    if ((n >>= 1) != 0)
        w = (w * w) % p; /* (sqr-rdx) */
}

r = (unsigned long) u;

并且，自从(2^n - 1) mod p = r - 1 mod p：

r = (r == 0) ? (p - 1) : (r - 1);

如果2^n mod p = 0- 如果 是素数，则实际上不会发生p > 2- 但我们不妨考虑一般情况 - 那么(2^n - 1) mod p = -1 mod p。

由于“共同残差”或“余数”(mod p)位于 中[0, p - 1]，因此我们添加 的某个倍数，p使其处于该范围内。

否则， 的结果2^n mod p在 中[1, p - 1]，并且减法1将已经在这个范围内。它可能更好地表达为：

if (r == 0)
    r = p - 1; /* -1 mod p */
else
    r = r - 1;