作者spits (遙遠的距離)
看板Grad-ProbAsk
標題Re: [問題] 96中山資工離散
時間Wed Mar 25 22:30:00 2009
※ 引述《MysterySW (飯糰丸)》之銘言：
: 第8題
: p=61, q=127, n=pq=7747
: 求最小整數d使得
: (1237^17)^d mod n = 1234
: 抱歉我數論很弱@@
: 這題不知道該怎麼做
: 感謝大家
題目你打錯了 是 (1234^17)^d mod n = 1234
1234^17d == 1234 (mod n) // "=="應該是要寫成三橫 打不出來
1234^(17d-1) == 1 (mod n)
1234^(17d-1) == 1 (mod p)
1234^(17d-1) == 1 (mod q)
根據費馬小定理( gcd(m,p)=1 則 m^(p-1) == 1 (mod p) )
(1234 跟 61, 127 皆互質)
1234^60 == 1 (mod p) => 17d-1 = a*60
1234^126 == 1 (mod q) => 17d-1 = b*126
即 17d-1 = c*60*126 =c*7560 => 17d == 1 mod 7560 (d為最小正整數)
7560 = 17*444 + 12
17 = 12* 1 + 5
12 = 5*2 + 2
5 = 2*2 + 1
1 = 5 - 2*2
= 5 - 2*(12 - 5*2) = 5*5 -2*12
= 5*(17 -12) - 2*12 = 5*17 - 7*12
= 5*17 - 7*(7560 - 17*444) = -7*7560 + 3113*17
所以d=3113
應該沒算錯吧 很怕計算錯誤
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.170.243.188
1F：推 mathmanliu:17x≡1 (mod 7560) => x≡3113 (mod 7560)沒錯! 03/25 23:08
2F：推 MysterySW:喔喔 非常感謝^^ 03/26 00:42
3F：推 greedbo:可以請問一下為什麼7650可以消去嗎? 書上寫7650=(三槓) 03/26 04:11
4F：→ greedbo:0,不懂三槓等號的實質意思? 03/26 04:11
5F：→ s987692:就是餘數的意思 (mod n ) ~之類 03/26 04:18
6F：→ loking:三橫應該是等價的意思 03/26 18:32
7F：→ ssccg:≡ (mod n)代表只有在(mod n) (代數裡面叫Zn)下是等價 03/26 23:51
8F：→ ssccg:這叫同餘關係 03/26 23:51
9F：推 ieaan:樓上真令人感動!你會有好報的! 03/27 07:13
10F：推 greedbo:感謝你,原來答案不太對 我一直對自己的解法看好久 03/27 16:05
11F：→ greedbo:兩個問題想請教,1.這題是哪裡有用到費馬小定理? 最後的d是 03/27 17:44
12F：→ greedbo:要在mod 後才是答案吧? 03/27 17:45