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

看板Grad-ProbAsk作者 (codenfu)時間1年前 (2022/09/08 09:07), 編輯推噓1(1推 0噓 5→)
留言6則, 3人參與, 1年前最新討論串1/1
題目： 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
推
09/08 09:57, 1年前 , 1F
((209mod53)^3)mod53 但應該有更好的算法
09/08 09:57, 1F
→
09/08 10:57, 1年前 , 2F
兩題都差不多就解第二題 因 209跟50 mod53
09/08 10:57, 2F
→
09/08 10:58, 1年前 , 3F
所 209^263跟50^263 mod 53 ; 53歐拉函數為52
09/08 10:58, 3F
→
09/08 11:00, 1年前 , 4F
263 = 52*3 + 3 算 50^3/53 的餘數得26
09/08 11:00, 4F
→
09/08 11:01, 1年前 , 5F
最後餘數我一秒能算出來 所以沒有很簡化 大概就這樣
09/08 11:01, 5F
→
09/08 23:24, 1年前 , 6F
謝謝
09/08 23:24, 6F
‣ 更多 codepo 的文章
文章代碼(AID): #1Z6K0sPk (Grad-ProbAsk)