Math Pro 數學補給站's Archiver

當你覺得自己很累的時候,
請記得,永遠有人比你更累。

weiye 發表於 2006-3-5 23:28

[代數] 一代數問題(應用於密碼學中)

[quote]
連結:[url=http://www.ptt.cc/bbs/Math/M.1176630948.A.DF1.html]http://www.ptt.cc/bbs/Math/M.1176630948.A.DF1.html[/url]

作者  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        [/quote]
連結:[url=http://www.ptt.cc/bbs/Math/M.1176715513.A.5FE.html]http://www.ptt.cc/bbs/Math/M.1176715513.A.5FE.html[/url]


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

頁: [1]

論壇程式使用 Discuz! Archiver 6.1.0  © 2001-2007 Comsenz Inc.