Math Pro 數學補給站

標題: [代數] 一代數問題(應用於密碼學中) [打印本頁]

作者: weiye 時間: 2006-3-5 23:28 標題: [代數] 一代數問題(應用於密碼學中)

引用:

連結：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

歡迎光臨 Math Pro 數學補給站 (https://math.pro/db/)

論壇程式使用 Discuz! 6.1.0