計算n其中a^n mod m = 1？

Question

什麼是計算第一n滿足等式

一個^ n的模m最快的方式= 1

這裏A，N，m可以是素數或複合 MOD：是模量運營商

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。 （Proof）
3. 否則（作爲更一般的情況），n =ф（m），其中ф是歐拉的總功能。 （Proof）

正如你所看到的，計算ф（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 = 1，n = 1，沒有什麼差別;對於a = 14，m = 15，n = 1， 2）。 n是ф（m）的除數，但有效地計算最少可能n似乎是棘手的。任務可以通過使用this定理（最小n是各個餘數的所有度數的最小公倍數）來劃分。但是，當m是素數或具有足夠大的素數除數，並且只有一個a（而不是用相同的m計算n對許多不同的a）時，我們沒有選擇。你可能想看看1,2。