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

Question

我要计算上午调制 n , 其中 n 是质数，米 很大。而不是用二进制幂计算来做这个，我想找到这样的 x 那 ax = a (mod n) 然后计算 a(m mod x) mod n .

显然是这样的 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 的因式分解, 除数和候选 y很容易找到和检查，所以找到 y 的工作量并不大然后 - 但通常仍然是 远比计算更多的工作 a^r (mod n)单人 0 <= r < n-1 .

寻找 n-1 的因式分解可能是微不足道的(例如对于费马素数)，但也可能非常困难。除了找到 a 的确切周期这一事实之外。模 n通常不仅仅是计算 a^r (mod n)对于一些 0 <= r < n-1 ，这使得尝试进一步降低指数是否值得非常怀疑。

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