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

[spits (遙遠的距離)]

※ 引述《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:17x≡1 (mod 7560) => x≡3113 (mod 7560)沒錯!
推 MysterySW:喔喔  非常感謝^^
推 greedbo:可以請問一下為什麼7650可以消去嗎? 書上寫7650=(三槓)
→ greedbo:0,不懂三槓等號的實質意思?
→ s987692:就是餘數的意思 (mod n ) ~之類
→ loking:三橫應該是等價的意思
→ ssccg:≡ (mod n)代表只有在(mod n) (代數裡面叫Zn)下是等價
→ ssccg:這叫同餘關係
推 ieaan:樓上真令人感動!你會有好報的!
推 greedbo:感謝你,原來答案不太對 我一直對自己的解法看好久
→ greedbo:兩個問題想請教,1.這題是哪裡有用到費馬小定理? 最後的d是
→ greedbo:要在mod 後才是答案吧?