※ 本文轉寄自 ptt.cc 更新時間: 2015-03-08 23:49:15
看板 Gossiping
作者 標題 Re: [問卦] 質數到底有什麼用？
時間 Sun Mar 8 22:54:05 2015
※ 引述《ding2599 (gfdgdfgd)》之銘言：
: ※ 引述《kamelot ()》之銘言：
: : 以前數學課大家都學過質數，就是只能被1和本身整除的數字，還要背幾個基本的質數來考試用。理論上來說質數有無限多個，但是到底有什麼用？頂多是為了找出更多質數。
: : 有數學家很愛研究質數的八掛嗎？因為根據算術基本定理，正整數可以被"唯一"地分解成一堆質數
(整數的話則是差正負號而已)
很多時候，我們都偷偷地使用到算術基本定理而沒有察覺
例如計算100的因數的數目，會將其分解成2^2*5^2，再計算3*3=9
回到正題，因為算術基本定理的關係，
我們要研究一個關於正整數命題的時候，"有時候"可以逐步從其質因數擊破，
最後再用這些被擊破的部分(質因數)，回擊原本的整個命題(原正整數)
最後再用這些被擊破的部分(質因數)，回擊原本的整個命題(原正整數)
例如費馬最後定理：
若整數x,y,z,N且N>2 滿足x^N+y^N=z^N → xyz=0
若N能整數分解成N=ab，則用指數律左式變成
(x^a)^b+(y^a)^b=(z^a)^b
令x^a=X, y^a=Y, z^a=Z，
這邊省略幾個敘述，原命題就等價於
若整數X,Y,Z,b且b>2 滿足X^b+Y^b=Z^b → XYZ=0
也就是說，對於費馬問題的正整數N，事實上只需要研究質數p≧3就好(4的另外處理)
反過來說，例如質數3，如果你能證明
若整數x,y,z 滿足x^3+y^3=z^3 → xyz=0
事實上已經證明了
若整數x,y,z 滿足x^N+y^N=z^N → xyz=0，對於所有Ｎ是３的倍數
如果說一個正整數是小智，那它的質因數是皮卡丘
只要能擊敗皮卡丘，小智就手到擒來
: 簡單的說就是 "密碼學"
: 軍事訊息的加密與解密~!
: 比如二次大戰德國自始自終不知"engama""謎"被盟軍破解
: 以至於所有的偷襲都被盟軍抓包而戰敗
: 現代社會
: 信用卡 及金融機構的加密與解密
: 其原理簡單的說，利用"質數無限多"特性 可製造出無限的RSA金鑰
: ~~~~~~~~~~~~~~~
: 可利用數論證明
: 質數相乘容易 但 質數相乘的積就難以被分解
: 利用此特性製造出RSA金鑰!
推 : 不過RSA編碼是二戰後才出現的03/08 21:53
→ : 不過也有人說 RSA編碼早在MIT那三位發表之前就存在了
據近年英國國安單位解密的情報（還是史諾燈爆料的？？我忘了）→ : 不過也有人說 RSA編碼早在MIT那三位發表之前就存在了
雖然英國國安單位內的人創用"RSA加密演算法" 確實比RSA三個人提出的還要早幾年
(RSA分別取自Ron Rivest，Adi Shamir，Leonard Adleman的字首，
Adleman認為他只是被抓來負責檢驗數學安全性的部分而已，所以說自己要排最後面)
但是RSA簽驗章的演算法 依然是RSA三個人較早創用
在密碼學裡面，不止於RSA，諸多密碼系統也都有對於「質數」的需求
例如說RSA的金鑰由兩個質數PQ構成，
如果今天不小心，P不是質數，RSA演算基本還是能用，
但是暴力搜尋法的複雜度(安全性)至少砍半，少很多，更不用說其他攻擊法
或是橢圓曲線加密的橢圓曲線群的大小，也會要求是質數，
所以說，不管是質數的檢驗，或者是橢圓曲線群的大小，都有一套演算做check
這都能讓我們看見質數的重要
如果想膜拜一下兩質數相乘的金鑰的話，HTTPS開頭的網址，旁邊都會有個鎖的圖案
點進憑證裡面的公開金鑰，沒意外應該都是
另外放到代數學中，也有類似質數的角色，normal gp跟ideal，就撲多說惹
有錯請勿指正，懶得改
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 58.114.194.148
※ 文章代碼(AID): #1K_6AGFM (Gossiping)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1425826448.A.3D6.html
→ : 文組看不懂怒噓1F 03/08 22:55
→ : 你錯了 還有妙蛙種子呢2F 03/08 22:55
推 : 你不是很會發廢文嗎?3F 03/08 22:55
最近發不出來很懊惱...推 : 認真文給推4F 03/08 22:55
→ : 請用中文講好嗎5F 03/08 22:56
※ 編輯: ma4wanderer (58.114.194.148), 03/08/2015 22:56:18推 : 跟我想的一樣6F 03/08 22:56
推 : 對阿 我也這麼覺得7F 03/08 22:56
推 : 專業文推8F 03/08 22:56
推 : 只好推了9F 03/08 22:57
推 : 不錯 不錯 跟我想的一樣10F 03/08 22:57
推 : 推11F 03/08 22:57
推 : ideal是什麼? 忘了12F 03/08 22:58
推 : 看不懂啦嗚嗚嗚13F 03/08 22:59
推 : 認真推 但我看不懂只好end14F 03/08 23:01
推 : ☎15F 03/08 23:02
推 : normal gp感覺不像質數 /的概念 比較像同除公因數的感覺16F 03/08 23:02
我是說面對群的處理上很像正整數之於質數的處理
做qutient之後的qutient gp會給我們一些原本群上的訊息，
只是除的越大 遺失的訊息也越多
如果是solvable或者nilpotent那上面的命題，還能用歸納法處理
推 : 快推 免得被人發現看不懂17F 03/08 23:02
推 : 要加密打中文不就得了18F 03/08 23:02
→ : 不對吧，若 x^3+y^3=z^3有整數解，不代表 x^(3k)+y^(3k19F 03/08 23:03
→ : )=z^(3k)有整數解啊，3^2+4^2=5^2->根號3^4+2^4=根號5^
→ : 4,但根號3和根號5不是整數
其實是省略滿多話→ : )=z^(3k)有整數解啊，3^2+4^2=5^2->根號3^4+2^4=根號5^
→ : 4,但根號3和根號5不是整數
如果x^3k+y^3k=z^3k有非零的正整數解
則x1^3+y1^3=z1^3也有
所以若後者沒有 則前者也沒有 這樣吧？
推 : 嗯嗯跟我想的一樣22F 03/08 23:04
推 : 不錯23F 03/08 23:05
推 : 說normal gp和ideal和質數的概念很像 你的代數老師應該會想哭24F 03/08 23:06
我是指得到訊息的觀點來看推 : 恩25F 03/08 23:07
推 : 看不懂但推就對了26F 03/08 23:08
推 : 某樓 你不能把N設成227F 03/08 23:09
推 : 我好像搞錯了..我想一下28F 03/08 23:09
推 : 果然如此 跟我想的都一樣 (嗯嗯29F 03/08 23:12
推 : Zp=Z/pZ 質數特性主要是不可分解 感覺起來不一樣啊30F 03/08 23:14
→ : 上面的式子 可以用Zn* 做尤拉的乘法群 也是會有normalgp
→ : 在乘法群裡/的感覺跟質數感覺不一樣 質數應該是比較後面
→ : prime ideal那個地方才有 p∣ab => p∣a or p∣b的fu
ideal的概念確實是從質數那邊來的沒錯→ : 上面的式子 可以用Zn* 做尤拉的乘法群 也是會有normalgp
→ : 在乘法群裡/的感覺跟質數感覺不一樣 質數應該是比較後面
→ : prime ideal那個地方才有 p∣ab => p∣a or p∣b的fu
當初要解決費馬問題 高斯原本做了一個證明 用分解不唯一來達成
結果後來發現不見得每個z[t]都是能唯一分解的
kummer就把不唯一分解的那些想放到一個更大的空間上，提出了ideal number，
讓不唯一分解的那些，再次分解，落入唯一分解的裡面
後來忘了誰，把ideal number的想法萃取成現在的ideal
我看neukirch的書寫的啦 希望沒看錯
→ : 你把質數/掉只是得到非質數的訊息 跟質數特性沒有fu34F 03/08 23:17
→ : 而且即使不是normal gp 技術上也是可以做/ 的感覺
→ : 類似module的樣子 感覺都跟質數明顯的特性不一樣
→ : 而且即使不是normal gp 技術上也是可以做/ 的感覺
→ : 類似module的樣子 感覺都跟質數明顯的特性不一樣
推 : 簡單說 81^2+0^2=81^2 等價於 9^4+0^4=9^437F 03/08 23:24
→ : 找2次方的解比找4次方的解 還要簡單
※ 編輯: ma4wanderer (58.114.194.148), 03/08/2015 23:27:40→ : 找2次方的解比找4次方的解 還要簡單
推 : 快推 不然人家以為我們看不懂39F 03/08 23:33
推 : 不推就要被抓包看不懂了40F 03/08 23:35
→ : "(整數的話則是差正負號而已)" 0何解?41F 03/08 23:40
→ : 啊~0不行~~漏了42F 03/08 23:47
--
※ 看板: K_hot 文章推薦值: 0 目前人氣: 0 累積人氣: 159
回列表(←)
分享