作者simonjen (狂)
看板Math
標題Re: [數論] mod基本概念
時間Sat Apr 23 09:41:11 2011
※ 引述《josephHPSH (阿尚)》之銘言：
: 小弟在念密碼學書籍的RSA
: 其中用到MOD運算
: 看了課本推導的一些步驟想了很久還是想不通，想上來請教一下各位
: a.
: [ (M)(M^f(p))^k(q-1) ] mod p
: = ( M mod p ) [ (M^f(p)) mod p ]^k(q-1)
: 為什麼這個次方寫在外面QAQ
單純的運算 你把M^f(p)看成b
所以式子就會變成M*b*b*...*b 其中b有k(q-1)個
所以用運算是換一下就會是 (M mod p)(b mod p)(b mod p)...(b mod p)
其中 b mod p 有k(q-1)個 所以得到你要的式子
: ※p,q 為質數
: ※f()為尤拉函數
: 模數基本運算 [( a mod n )( b mod n )] mod n = ( a x b ) mod n
: ----------------------------------------------------------------
: b.
: 如果 ed mod f(n) = 1 <=> ed 乘法反向 mod f(n)
: 在上述條件下為什麼 e d 都要與 f(n) 互質呢?
: ※f()為尤拉函數
: 抱歉小弟是個新手 如果有哪邊不太清楚的我在想辦法補 thx~
先令ed = k
所以就變成 k mod f(n) = 1
意謂著 k = f(n)*q + 1
依據中國餘式定理(好像是這一個名字) =>
( k , f(n) ) = ( f(n) , 1 ) = 1
所以 k 和 f(n) 互質
因此e 和 d 必然和 f(n) 互質
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.191.224
1F：推 josephHPSH :太感謝你了! 04/23 10:11
2F：推 josephHPSH :不過還有一個小小疑問 如果是依照基本模數運算 04/23 10:24
3F：→ josephHPSH : [( a mod n )( b mod n )] mod n = ( a x b ) mod n 04/23 10:24
4F：→ josephHPSH : 這個mod n消失了? 04/23 10:26
^^^^^^^^^???!!!
那來說明一下好了
令 a = np + k ; b = nq + r 0=< k,r < n
=> ab = pqnn + rpn + kqn + rk
所以由以上可以知道 a mod n = k b mod n = r ab mod n = rk
因此 ab mod n = (a mod n)*(b mod n)
※ 編輯: simonjen 來自: 111.249.62.92 (04/23 11:06)
※ 編輯: simonjen 來自: 111.249.62.92 (04/23 11:06)
5F：推 josephHPSH :thanks~ 04/23 11:22