作者codepo (codenfu)
看板Grad-ProbAsk
标题[理工] [资工][离散] 数论
时间Thu Sep 8 09:07:00 2022
题目：
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1662599222.A.66E.html
1F：推 jacksoncsie: ((209mod53)^3)mod53 但应该有更好的算法 09/08 09:57
2F：→ TaiwanFight: 两题都差不多就解第二题 因 209跟50 mod53 09/08 10:57
3F：→ TaiwanFight: 所 209^263跟50^263 mod 53 ; 53欧拉函数为52 09/08 10:58
4F：→ TaiwanFight: 263 = 52*3 + 3 算 50^3/53 的余数得26 09/08 11:00
5F：→ TaiwanFight: 最後余数我一秒能算出来 所以没有很简化 大概就这样 09/08 11:01
6F：→ codepo: 谢谢 09/08 23:24
7F：→ st000an: 虽然隔了很久才看到这篇 但我看不出第一题要怎麽用留言 01/21 10:42
8F：→ st000an: 提到的方式解欸 我是用中国剩余定理 想请问一下其他人是 01/21 10:42
9F：→ st000an: 怎麽算的？ 01/21 10:42
10F：→ st000an: 我的算法 是11x [3^111 mod 13] x 13 [3^111 mod 11] mod 01/21 10:43
11F：→ st000an: 143 01/21 10:43