[數論] 歐拉函數問題

[bugmens (今天天氣好)]

http://en.wikipedia.org/wiki/Euler%27s_theorem
  x
17 =1(mod 2668)

按照歐拉函數的定義x=φ(2668)=1232
                         x
但我想要找出最小的x使得17 =1(mod 2668)
                4
似乎只能從1232=2 *7*11的因數去一個一個測試
  1
17  =17 (mod 2668)
  2
17  =289(mod 2668)
  4
17  =813(mod 2668)
...
  44
17  =1  (mod 2668)

所以最小的x是44，請問有沒有函數可以直接計算最小的x值

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 1.164.60.156
→ someone     :或許建立在各個質數的倒數循環節的長度的最小公倍數
推 hcsoso      :這問題被稱作 order finding problem, 目前似乎沒有
→ hcsoso      :快的演算法; 不過可能還是有當數字夠小時, 手算能接
→ hcsoso      :受的方式就是了.
→ hcsoso      :順帶一提, 如果你有量子電腦的話, Shor 的質數分解
→ hcsoso      :演算法實質上就是解這個問題.
→ bugmens     :我用你給的關鍵字找到資料了 感謝