0

式を満たす最初の n を計算する最速の方法は何ですか?

a^n mod m = 1

ここで、a、n、m は素数または複合 mod です: はモジュラス演算子です

4

2 に答える 2

-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 が 1 つしかない場合 (同じ m を持つ多くの異なる a に対して n を計算するのとは対照的に)、選択肢がありません。1、2を見たいと思うかもしれません。

于 2013-10-23T07:21:39.600 に答える