1

序幕

我们要计算模幂A (B C) mod p = ?，其中A, B, C, 和p是已知的，p是一个素数。例如：2 4 3模 23 = 6

如果我们直接计算，首先 B C = e，然后 A e = n，最后 n mod p；我们将遇到为 e 和 n 创建（可能）非常大的中间结果的问题。例如：e = 4 3 = 64，n = 2 64 ≈ 1.845x10 19，最后是 n mod 23 = 6

然而，以直接的方式做这件事，我们没有利用 p 是一个素数并且我们正在做模幂运算的事实。而且这样做，我们将在时间（CPU）和空间（内存）方面遇到使用计算机程序计算结果的问题。

（是的，我们可以通过首先将 A (B C) mod p 减少到 A e模式 p 来使用恒等式进行快速模幂运算。例如 A 2 mod p = (A ⋅ A) mod p = [(A mod p) ⋅ (A mod p)] mod p – 但这不是我们想要的）。(a ⋅ b) mod m = [(a mod m) ⋅ (b mod m)] mod m

聪明的方法——使用费马小定理

正如GeeksforGeeks上的 Find power of power under mod of a prime和这个问题的起源中所记录的那样，我们在 A (B C) mod p 中的指数 B C可以使用费马小定理以不同方式表示。

费马小定理：如果 p 是素数，则a (p - 1) ≡ 1 (mod p)

导致以下转变：

  1. 可以将指数 B C重写为 x ⋅ (p - 1) + y

  2. 使用该替代表达式，我们的 A B C变为 A x ⋅ (p - 1) + y = A x ⋅ (p - 1) ⋅ A y

  3. 使用费马小定理A x ⋅ (p - 1) = 1；计算 A (B C) mod p 变为计算 A y

  4. 使用 B C = x ⋅ (p - 1) + y 然后 y 可以写成 B C mod (p - 1)

从上面我们得到 A (B C) mod p = (A y ) mod p

有了所有这些，我们可以分两步计算 A (B C) mod p，同时保持中间结果很小。

  1. y = (B C ) mod (p - 1)
  2. 结果 = (A y ) mod p

例如：2 4 3模 23

  1. y = 4 3 mod (23 - 1) = 64 mod 22 = 20
  2. 结果 = 2 20模 23 = 1048576 模 23 = 6

问题

我的问题是关于上述转换，我在任何地方都找不到（易于理解的）解释。同样专注于费马小定理也无济于事。可能这些转换应该是显而易见的，但对我来说根本不清楚。

特别是，我不明白为什么指数 B C可以表示为 x ⋅ (p - 1) + y。– 这背后的原因是什么？

而且，为什么在使用费马小定理时它应该是“显而易见的” ：

a (p - 1) ≡ 1 (mod p) 即 A x ⋅ (p - 1) = 1？

如果有人能以一种易于理解的方式解释这些转变，那就太好了。

4

1 回答 1

2

让我解决您的两个主要问题：

特别是，我不明白为什么指数 B C可以表示为 x ⋅ (p - 1) + y。– 这背后的原因是什么？

对于某个模数 m，任何整数 k 都可以表示为 k = xm + y。可以把它想象成将 k 除以 m，得到商x 和余数y。所以让 k = B C和 m = p - 1 和 tada。

如果它有助于你理解，一个类比是你可以将任意数量的分钟变成“小时 + 分钟”，当 m = 60 时，x = 小时，y = 剩余分钟数。

而且，为什么在使用费马小定理时它应该是“显而易见的”：

a (p - 1) ≡ 1 (mod p) 即 A x ⋅ (p - 1) = 1？

假设我们有(p - 1) ≡ 1 (mod p)。如果我们将两边都乘以(p - 1)会发生什么？我们得到：

    a (p - 1) a (p - 1) ≡ a (p - 1) (mod p)
    a (p - 1) + (p - 1) ≡ 1 (mod p) (z x z y = z x+ y和右手边等价于 1，正如我们之前所见）
    a 2(p - 1) ≡ 1 (mod p)

我们可以反复将两边乘以(p - 1)得到3(p - 1)、4(p - 1)等，所以我们说对于任何整数 x 我们都有一个x(p - 1) ≡ 1 (mod p)。

于 2020-07-19T00:40:21.360 回答