问计算n，其中a^n模m= 1？

EN

直接的方式有什么问题：

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;
}

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)，我们就没有选择了。你可能想看看1，2。