c - 计算 ((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

您在评论中提到nandp是 9 位或 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);

---

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

由于“普通残基”或“余数”(mod p)在 中[0, p - 1]，我们添加了 的某个倍数p，使其在此范围内。

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

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

Answer 3

要取模数，您必须以某种方式获得 2^n-1 ，否则您将朝着不同的算法方向移动，有趣但不知何故是独立的方向，因此我建议您使用 big int 概念，因为它很容易......制作一个结构和以小值实现大值，例如

  struct bigint{
    int lowerbits;
    int upperbits;
  }

语句的分解也有像 2^n = (2^n-4 * 2^4 )-1%p 分解和单独处理它们的解决方案，那将是相当算法化的

Answer 4

要计算 2^n - 1 mod p，您可以在首先从 n 中删除 (p - 1) 的任何倍数后进行平方运算（因为 a^{p-1} = 1 mod p）。在伪代码中：

n = n % (p - 1)
result = 1
pow = 2
while n {
    if n % 2 {
        result = (result * pow) % p
    }
    pow = (pow * pow) % p
    n /= 2
}
result = (result + p - 1) % p

Answer 5

在解决 HackerRank 上的一个数学问题时，我发现了我在此处发布的答案，并且它适用于那里给出的所有给定测试用例。

如果您将n和限制p为 64 位（无符号长整数）值，那么这里是数学方法：

2^n - 1可以写成1*[ (2^n - 1)/(2 - 1) ]

如果你仔细看这个，这是GP的总和1 + 2 + 4 + .. + 2^(n-1)

瞧，我们知道(a+b)%m = ( (a%m) + (b%m) )%m

如果您对上述关系是否成立有疑问，您可以谷歌搜索或查看此链接： http: //www.inf.ed.ac.uk/teaching/courses/dmmr/slides/ 13-14/Ch4.pdf

所以，现在我们可以将上述关系应用到我们的全科医生身上，你就会得到答案！！也就是说， (2^n - 1)%p等价于( 1 + 2 + 4 + .. + 2^(n-1) )%p并且现在应用给定的关系。

Answer 6

首先，关注 2 ⁿ mod p，因为你总是可以在最后减去一个。

考虑两个的幂。这是通过重复乘以 2 产生的数字序列。

考虑模运算。如果该数字以 p 为底数，则您只需抓住最后一位数字。更高的数字可以被丢弃。

因此，在序列中的某个点上，您会得到一个两位数（p 的位置为 1），而您的任务实际上只是在发生这种情况时去掉第一个数字（减去 p）。

从概念上讲到这里，蛮力方法将是这样的：

uint64_t exp2modp( uint64_t n, uint64_t p ) {
    uint64_t ret = 1;
    uint64_t limit = p / 2;
    n %= p; // Apply Fermat's Little Theorem.

    while ( n -- ) {
        if ( ret >= limit ) {
            ret *= 2;
            ret -= p;
        } else {
            ret *= 2;
        }
    }
    return ret;
}

不幸的是，对于大的 n 和 p，这仍然需要很长时间，而且我想不出任何更好的数论。

如果您有一个可以计算 (p-1)^2 而不会溢出的乘法工具，那么您可以使用类似的算法，在每次平方运算后使用带模的重复平方，然后再次取平方残差系列的乘积每次乘法后都有一个模数。

Answer 7

步骤 1. x= 将 1 移动 n 次，然后减去 1

step 2.result = x 和 p 的逻辑与运算