引用:
連結：http://www.ptt.cc/bbs/Math/M.1176630948.A.DF1.html
作者 bbsky (每天為小灰祈福=人=) 看板 Math
標題 [代數] 一代數問題(應用於密碼學中)
時間 Sun Apr 15 17:55:47 2007
───────────────────────────────────────
(x + y) <------------------這是g的次方
若一數值B = g mod p
(R在括號外喔)
↓
-y R xR
則 ﹝B‧g ﹞ mod p = g mod p
這兩個式子相等 是為什麼呢?
其中p為一大質數 x和y也都想成是很大的整數
R和g都是可以隨便代的數
這問題我百思不得其解啊....只知道有用到diffie-hellman的概念
希望有高手為我解答 謝謝orz
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.162.67.95
連結：
http://www.ptt.cc/bbs/Math/M.1176715513.A.5FE.html
作者 weiye (^__^) 看板 Math
標題 Re: [代數] 一代數問題(應用於密碼學中)
時間 Mon Apr 16 17:25:12 2007
───────────────────────────────────────
待會要引用的：
因為 p 是質數，所以對於任意非 p 的倍數的整數 m
皆存在整數 n 使得 m‧n=1 mod p
此時若限定 n in {1,2,...,p-1}
可將 n 表示成 n = m^{-1}
(同餘的乘法反元素)
證明：
因為 p 為質數，且 m 非其倍數
所以 gcd(m,p)=1
故，存在整數 m,s
使得 m‧n + s‧p = 1 ，因此 m‧n=1 mod p
: (x + y) <------------------這是g的次方
: 若一數值B = g mod p
若 g 非 p 的倍數
則存在 g^{-1} 使得 g‧g^{-1}=1 mod p
左右同時 y 次方，可得 g^{y}‧g^{-y}=1 mod p
╰──┬─╯
╰→∵整數乘法交換率可得 (a‧b)^n=a^n‧b^n
因此將
(x + y) <------------------這是g的次方
B = g mod p
左右同時乘上 g^{-y} 可得
-y x
B‧g mod p = g mod p
在同時 R 次方，則
(R在括號外喔)
↓
-y R xR
﹝B‧g ﹞ mod p = g mod p
