Re: [問題] 96中山資工離散

看板Grad-ProbAsk作者spits (遙遠的距離)時間15年前 (2009/03/25 22:30)推噓5(5推 0噓 7→)

留言12則, 7人參與討論串4/5 (看更多)

※ 引述《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

推

mathmanliu

03/25 23:08, , 1^F

03/25 23:08, 1^F

推

MysterySW

03/26 00:42, , 2^F

03/26 00:42, 2^F

推

greedbo

03/26 04:11, , 3^F

03/26 04:11, 3^F