※ 本文轉寄自 ptt.cc 更新時間: 2015-03-09 09:10:48
看板 Gossiping
作者 標題 Re: [問卦] 質數到底有什麼用？
時間 Sun Mar 8 23:58:36 2015
在密碼學裡面，不止於RSA，諸多密碼系統也都有對於「質數」的需求
例如說RSA的金鑰由兩個質數PQ構成，
如果今天不小心，P不是質數，RSA演算基本還是能用，
但是暴力搜尋法的複雜度(安全性)至少砍半，少很多，更不用說其他攻擊法
或是橢圓曲線加密的橢圓曲線群的大小，也會要求是質數，
--
恩~~在很多密碼系統中，所需要的是 group(群)，這個代數架構。
而剛好((Z/pZ)*,*) 剛好是一個group，所以就拿來在密碼系統用。
而group有什麼好處呢？因為group具有封閉性，你任拿其中兩個元素運算，他還會是
在這個group裡。所以我們不用怕會有什麼奇怪的東西跑出來。
然後要讓這個密碼系統難破的的話，我知道是使用所謂的離散對數的難題。
什麼是離散對數呢？ 任給兩個數a,b 求m a^m=b+Qp，用中文來說就是 a的多少次方除以
p餘數才會是b。 而在這通常p是質數，因為質數不可分的性質才會對任意的a都會有解
(ps.其實在這裡的group是要有特定條件的群，只是我忘了是什麼…不好意思，學藝不精)
也因為在密碼系統中，他們所需要的東西是代數架構這種東西，所以只要符合他們條件的
代數架構都可以拿來用。
在小談一下，費馬小定理的證明，那就是因為((Z/pZ)*,*) 是一個group Q.E.D.
這就是group的力量(被歐)
再來補充一下，橢圓曲線群 over Fp 的個數不一定會是質數是就了。
http://en.wikipedia.org/wiki/Counting_points_on_elliptic_curves
Counting points on elliptic curves - Wikipedia, the free encyclopedia E.g. the last row is computed as follows: If you insert in the equation you get as result (2nd column). This result can be achieved if . So the points for the last row are because is fixed as it is the result and if is positive and if is negative. Remember that equals over . ...
wiki裡有簡單的例子可以看一下。
大概就是這樣，如果有錯請多多指教。
--
「台灣 + 中國 = 經濟肯定會成長。我發現了一個非常漂亮的證明，
但 4 年實在太短，沒有足夠的時間容我來證明它。」
轉自 <廢馬大定理>-民明書坊
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.160.199.231
※ 文章代碼(AID): #1K_76vVr (Gossiping)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1425830329.A.7F5.html
推 : 我懂了 樓下不懂別裝1F 03/08 23:59
推 : 趕快推 不然別人以為我......2F 03/09 00:00
推 : ED3F 03/09 00:00
推 : 快推不然別人說我不懂4F 03/09 00:00
推 : 這很難嗎 怎麼可能有人不懂 對吧?樓下?5F 03/09 00:00
噓 : 看不懂噓6F 03/09 00:00
推 : 簡單來說就是質數很重要恩恩 我懂了7F 03/09 00:01
推 : 恩 對阿8F 03/09 00:02
推 : 快推 免得被人說看不懂9F 03/09 00:03
推 : 很好理解10F 03/09 00:04
推 : 推回來Y11F 03/09 00:04
→ : ...你離散對數問題好像搞錯了 費馬小定理也搞錯了12F 03/09 00:05
感謝指正 離散對數的問題→ : 費馬小定理沒錯 可以推過去13F 03/09 00:06
→ : 還要加個lagrange吧?14F 03/09 00:07
有largrange 是euler theorem嗎？a^(phi(m))= (1 mod m)
→ : 跟我想的差不多，就是這樣15F 03/09 00:07
推 : a^m=1+qb好像有看過啊..不過忘光了..16F 03/09 00:08
→ : 不用喔 triially Zp* is a finite group i.e. Z^(p-1)=117F 03/09 00:09
推 : 幫樓主修正一下，其實(Z/pZ,*)不是群，因為0沒有反元素...18F 03/09 00:11
→ : 妳要把零扣掉，變成((Z/pZ)^x,*)才是群 :)
→ : 妳要把零扣掉，變成((Z/pZ)^x,*)才是群 :)
感謝指正，自己在看的時候會知道，不過常常寫出來的時候就會忘記加
推 : 恩.................................... (爆炸20F 03/09 00:12
推 : 幫補充什麼是Lagrange's Theorem: H是G的subgroup且|G|有限21F 03/09 00:14
→ : 則 |H|整除|G|
→ : 則 |H|整除|G|
→ : lagrange是指子群的大小整除原本的23F 03/09 00:15
我知道這個定理(不過忘了名字，教授別罵我)，
但我不清楚這個定理跟費馬小定理之間的關係就是了
推 : 正規子群24F 03/09 00:16
→ : 所以一個元素的order=其循環群的大小 整除原本的25F 03/09 00:16
推 : 推一下 剛好是研究領域26F 03/09 00:18
→ : 我是這樣導啦@@ 不然你是怎導小定理的27F 03/09 00:19
推 : 和費馬小定裡的關係是這樣：給一個非零的a。那根據Lagrange28F 03/09 00:19
→ : 定理，<a>||G| = p-1，所以很快得到a^(p-1) = 1 => a^p = a
→ : (mod p) 如果 a = 0 是 trivial，證畢。
感謝指導。→ : 定理，<a>||G| = p-1，所以很快得到a^(p-1) = 1 => a^p = a
→ : (mod p) 如果 a = 0 是 trivial，證畢。
推 : 忘了講，上面的 a 非零是在 Z/pZ 中非零31F 03/09 00:23
→ : 啊 對了 補充一下 橢圓曲線群的大小不見得是質數沒錯32F 03/09 00:24
→ : 但會要求是質數
→ : 不然會被normal group作解析
→ : 但會要求是質數
→ : 不然會被normal group作解析
不知道要看什麼書還是paper，才能知道elliptic curve group over finite field
的個數需要被要求是質數？
推 : 好，我老實承認我看不懂35F 03/09 00:27
推 : 漏打 拍謝 我是要說"橢圓曲線加密"的橢圓曲線群36F 03/09 00:36
→ : 大小要求是質數
→ : 大小要求是質數
恩~~那有相關的資訊嗎？還是有什麼kye word 可以拿來google。謝謝
噓 : 好啦幹 我文組 嗆我嗆夠沒38F 03/09 00:43
→ : 應該是pohlig-hellman攻擊吧39F 03/09 00:48
感謝大大的提供。八掛版果然人才濟濟。
※ 編輯: jayfrog (118.160.199.231), 03/09/2015 00:51:42
推 : 早八第一堂網路安全 滑個PPT還看到這篇40F 03/09 08:44
--
※ 看板: K_hot 文章推薦值: 0 目前人氣: 0 累積人氣: 104
回列表(←)
分享