c++ - 计算 n 其中 a^n mod m = 1？

Question

计算满足方程的第一个 n 的最快方法是什么

a^n 模 m = 1

这里 a,n,m 可以是素数或复合模：是模运算符

Answer 1

直接方式有什么问题：

int mod_order(int m, int a) {
    for(int n = 1, an = a; n != m; n++, an = an * a % m) if(an % m == 1) return n;
    return -1;
}

Answer 2

1. 如果gcd(a,m)>1，则不存在这样的n。（明显的）
2. 否则，如果 m 是素数，则 n=m-1。（证明）
3. 否则（和更一般的情况），n=ф(m)，其中 ф 是欧拉的总函数。（证明）

如你所见，计算ф(m)本质上与m的因式分解相同。这可以在 sqrt(m) 时间或更短的时间内完成，具体取决于您使用的算法的复杂程度。简单一：

int phi(m){
  if(m==1) return 1;
  for(int d=2; d*d<m; ++d){
    if(m%d != 0) continue;
    int deg = 1; long acc=1;
    for(; m%(acc*d)==0; ++deg) acc*=d;
    acc /= d;
    return phi(m/acc)*acc*(d-1)/d;
  }
  return m-1;
}

更新：我的错。a^(ф(m)) = 1 (mod m)，但可以有更小的 n 值（对于 a=1，n=1，m 是什么没有区别；对于 a=14，m=15，n= 2）。n 是 ф(m) 的除数，但有效地计算最不可能的 n 似乎很棘手。使用这个定理可以划分任务（对于各个余数，最小 n 是所有度的最小公倍数）。但是当 m 是素数或有足够大的素数除数时，并且只有一个 a（而不是为许多具有相同 m 的不同 a 计算 n），我们就别无选择了。您可能想查看1、2。