作者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