[理工] [資工][離散] 數論

[codepo (codenfu)]

題目：
Suppose that x and y are integers, that x = 3^111 mod 143 and  y = 209^263 mod 5
3. Please compute x, y and gcd(x, y).

解答：
 x = 14
y = 26

問題：
1. 目前透過尤拉函數 知道 3^120 ≡ 1 mod 143, 但 題目只求 3^111 希望有大大可以提
供 x 的詳解
2. y ≡ 209^263 ≡ 209^3 目前做到這邊卡住
 希望可以提示下一步怎麼做

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.129.201.81 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1662599222.A.66E.html
推 jacksoncsie: ((209mod53)^3)mod53 但應該有更好的算法
→ TaiwanFight: 兩題都差不多就解第二題    因  209跟50 mod53
→ TaiwanFight: 所 209^263跟50^263 mod 53  ; 53歐拉函數為52
→ TaiwanFight: 263 = 52*3 + 3   算 50^3/53 的餘數得26
→ TaiwanFight: 最後餘數我一秒能算出來  所以沒有很簡化 大概就這樣
→ codepo: 謝謝
→ st000an: 雖然隔了很久才看到這篇 但我看不出第一題要怎麼用留言
→ st000an: 提到的方式解欸 我是用中國剩餘定理 想請問一下其他人是
→ st000an: 怎麼算的？
→ st000an: 我的算法 是11x [3^111 mod 13] x 13 [3^111 mod 11] mod
→ st000an:  143