math - 在 a^x = a (mod n) 中找到 x

Question

我想计算一个^m mod n，其中n是一个素数，而m非常大。我想用二进制幂计算来做这个，我想找到这样的x，a ^x = a (mod n)然后计算a ^{(m mod x)} mod n。

显然，任何a都存在这样的x，因为在某些时候为 mod n 循环提供了动力，但我没有找到如何用模运算来计算它。我想知道我是否遗漏了什么，或者是否存在一些数值方法？

Answer 1

你的模数是素数，这很容易开始，就像费马（不恰当地称为“小”）定理一样，然后

a^n ≡ a (mod n)

对于所有人a。等效的是公式

a^(n-1) ≡ 1 (mod n),  if n doesn't divide a.

然后你有

a^m ≡ 0 (mod n) if a ≡ 0 (mod n) and m > 0

和

a^m ≡ a^(m % (n-1)) (mod n) otherwise

（请注意，您的建议a^(m % x)通常是不正确的，如果m = q*x + r，您会有

a^m ≡ (a^x)^q * a^r ≡ a^q * a^r ≡ a^(q+r) (mod n)

并且您需要重复该减少，q+r直到您获得小于x) 的指数。

如果您真的对最小的x > 1这样感兴趣，那么a^x ≡ a (mod n)的情况又a ≡ 0 (mod n)是微不足道的 [ x = 2]，而对于其他情况，让y = min { k > 0 : a^k ≡ 1 (mod n) }，然后是所需的x = y+1，并且，由于环中的单元Z/(n)形成有序的（循环）群n-1，我们知道y是 的一个除数n-1。

如果您有 的因式分解，则很容易找到并检查n-1除数和候选者，因此找到的工作量并不大- 但它通常仍然比计算单个.yya^r (mod n)0 <= r < n-1

找到 的因式分解n-1可能很简单（例如对于费马素数），但也可能非常困难。除了找到a模的确切周期通常比计算somen多得多的工作之外，这使得它是否值得尝试进一步减少指数非常值得怀疑。a^r (mod n)0 <= r < n-1

通常，当模不是素数时，情况gcd(a,n) = 1类似，用[n-1替换λ(n)其中λ是 Carmichael 函数，它产生 的单位组的最小指数Z/(n)；对于素数n，我们有λ(n) = n-1]。