[其他] 數學白癡問質因數分解

看板Math作者時間11年前 (2013/06/27 01:53), 編輯推噓8(8推 0噓 50→)
留言58則, 13人參與, 4年前最新討論串1/1
我是人文科系畢業的，看到張益唐對孿生質數猜想的證明做出很大貢獻的新聞 以外行人看熱鬧的心情來看待這件事 這新聞忽然引發我的疑問，希望這裡的高手能否以「科普」的方式來解答 我的疑問是：為何質因數分解（尤其是非常大的數字）如此困難？ 就一個數學只學到高中社會組數學的我來說，在小學學到的質因數分解 就是用短除法來分解，不過除此方法外，從國中數學課本到高中社會組數學課本 完全就沒提到其他方法了 因為質因數分解是在國小就學了，所以用一種「感覺上」的判斷，會誤以為質因數分解 好像不難，應有規則可循 但弔詭在這裡，以社會組數學所能學到的來說，真的去做質因數分解，而且是對 不小的整數做分解，比如 88370753，就根本是異常困難的事。因為即使社會組數學 學的很好的學生，面對這數字只能用「試誤法」逐一用小的質數去除除看，搞不好試了 好幾天仍然分解不出來 這就是我最大的疑問，一個從國小就學的質因數分解（當然是分解像407、4183 這種較小的數字），居然可以是個很大的難題。這難題的弔詭偏偏在於，有些在 高中才開始學的圓錐曲線，居然沒有比質因數分解困難（因為我們在小學就學了） 所以這個看似簡單，卻實際異常困難的質因數分解（因為即使高中數學很厲害的 似乎也只能用試誤法逐一驗算），到底是什麼理由可以如此複雜？ 請高手用深入淺出的方式為我解惑，感謝。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 180.218.155.43
→
06/27 01:59, , 1F
你所謂的困難跟簡單之區別，好奇怪喔
06/27 01:59, 1F
→
06/27 02:04, , 2F
題目出得很好分解=>簡單, 圓錐曲線不熟=>難
06/27 02:04, 2F
推
06/27 03:04, , 3F
舉例:求 x^2/a^2 - y^2/b^2 = 1的漸進線?
06/27 03:04, 3F
→
06/27 03:06, , 4F
我們都知道漸進線公式是 bx+ay=0 and bx-ay=0
06/27 03:06, 4F
→
06/27 03:07, , 5F
推導這公式可能讓妳覺得比國小質因數分解難
06/27 03:07, 5F
→
06/27 03:09, , 6F
可是如果今天a和b都是10位數的質數
06/27 03:09, 6F
→
06/27 03:10, , 7F
而題目直接給a^2,b^2的值(不知道a,b是多少)
06/27 03:10, 7F
→
06/27 03:12, , 8F
那質因數分解a^2,b^2求出a,b
06/27 03:12, 8F
→
06/27 03:12, , 9F
就顯得比推導漸進線公式難
06/27 03:12, 9F
→
06/27 03:13, , 10F
結論:漸進線推導公式其結果是一定的
06/27 03:13, 10F
→
06/27 03:15, , 11F
而分解a^2,b^2會隨著位數增加而以級數成長複雜
06/27 03:15, 11F
→
06/27 03:17, , 12F
在數學上這種沒有有效的求解問題 往往才是大難題
06/27 03:17, 12F
→
06/27 11:09, , 13F
就如排列組合..明明只是數數..你可以很容易算的出來?
06/27 11:09, 13F
→
06/27 12:26, , 14F
不會得最難...
06/27 12:26, 14F
→
06/27 12:26, , 15F
的
06/27 12:26, 15F
推
06/27 12:59, , 16F
都很難很複雜的哦
06/27 12:59, 16F
推
06/27 13:15, , 17F
數論一向是理解題目很簡單,如何解卻很難
06/27 13:15, 17F
推
06/27 18:25, , 18F
質因數分解真的不難啊，只要會做整數的除法就可以了
06/27 18:25, 18F
→
06/27 18:26, , 19F
一個一個慢慢來，不管多大的數字總有一天都可以讓你
06/27 18:26, 19F
→
06/27 18:26, , 20F
分解出來的
06/27 18:26, 20F
→
06/27 18:27, , 21F
困難的是，如果你嫌簡單的方法慢死人，那有沒有其他
06/27 18:27, 21F
→
06/27 18:27, , 22F
方法去做
06/27 18:27, 22F
推
06/27 19:08, , 23F
不管多大的數字總有一天可以分解出來,這好像不太妥當
06/27 19:08, 23F
→
06/27 19:09, , 24F
目前幾乎所有銀行都用RSA1024,如果妳可以分解出來
06/27 19:09, 24F
→
06/27 19:09, , 25F
全銀行所有帳戶的錢都可以輕鬆進入妳的口袋
06/27 19:09, 25F
→
06/27 19:11, , 26F
RSA1024在密碼安全度上被歸類為絕對安全
06/27 19:11, 26F
→
06/27 19:12, , 27F
也就是一個人從出生開始,讓"電腦"來分解RSA1024
06/27 19:12, 27F
→
06/27 19:12, , 28F
到這個人死亡電腦還分解不出來
06/27 19:12, 28F
→
06/27 19:13, , 29F
何況妳用手算,要跟電腦比
06/27 19:13, 29F
→
06/27 20:29, , 30F
給定任何數字，的確是可以用笨方法在有限時間內分解
06/27 20:29, 30F
→
06/27 20:29, , 31F
完沒錯啊
06/27 20:29, 31F
→
06/27 20:31, , 32F
RSA的安全性是建立在「沒辦法在有意義的短時間內破
06/27 20:31, 32F
→
06/27 20:31, , 33F
解」，而不是「無法破解」
06/27 20:31, 33F
→
06/27 20:32, , 34F
如果你的密碼要讓電腦跑上十年才能用暴力破掉，然後
06/27 20:32, 34F
→
06/27 20:33, , 35F
你兩三年換一次密碼，這就是安全了
06/27 20:33, 35F
→
06/27 20:34, , 36F
任何使用public key的加密系統都一定會把系統的加密
06/27 20:34, 36F
→
06/27 20:35, , 37F
鑰匙曝露出來，因為public key跟private key之間的
06/27 20:35, 37F
→
06/27 20:36, , 38F
對應關係都是一對一可逆。
06/27 20:36, 38F
→
06/27 20:36, , 39F
所以RSA靠的不是把門鎖死不讓人進來，而是大門開開
06/27 20:36, 39F
→
06/27 20:36, , 40F
但是把路弄得很長很難走
06/27 20:36, 40F
→
06/27 22:38, , 41F
日本科學教育館XD
06/27 22:38, 41F
→
06/27 22:41, , 42F
打錯了，是日本科學未來館
06/27 22:41, 42F
推
06/27 22:42, , 43F
認真講起來 RSA 應該比較像是挖了一個大坑讓你掉
06/27 22:42, 43F
→
06/27 22:42, , 44F
如果要徒手爬上來很費力 但如果有梯子(private key)
06/27 22:42, 44F
→
06/27 22:42, , 45F
就可以輕鬆解決了 而在沒有梯子時找梯子也是費工的
06/27 22:42, 45F
→
06/27 22:43, , 46F
這種類型的東西在計算數學上有個名詞叫單向函數
06/27 22:43, 46F
→
06/27 22:43, , 47F
就是算過去很簡單, 但算回來除非給提示不然很費工
06/27 22:43, 47F
→
06/27 22:58, , 48F
大姊姊就是沒得到提示（泣）
06/27 22:58, 48F
→
06/27 23:04, , 49F
其實是沒給梯子，但是一定會給做梯子的材料和工具
06/27 23:04, 49F
→
06/27 23:04, , 50F
只是你花一輩子的時間也不見得做得出來這樣
06/27 23:04, 50F
推
06/28 18:34, , 51F
我有說是RSA1024,重要的是1024
06/28 18:34, 51F
→
06/28 18:35, , 52F
另外,絕對安全跟相對安全跟不安全的定義是什麼
06/28 18:35, 52F
→
06/28 18:37, , 53F
請查查一些入門的密碼學書,不難找到他們的定義
06/28 18:37, 53F
→
06/28 22:01, , 54F
我看不太懂你們的描述衝突在哪？
06/28 22:01, 54F
推
06/30 18:45, , 55F
而不是「無法破解」 我想他不清楚"絕對安全"的定義
06/30 18:45, 55F
→
11/10 11:59, , 56F
都很難很複雜的哦 https://daxiv.com
11/10 11:59, 56F
→
01/02 15:27, 5年前 , 57F
其實是沒給梯子，但是一 https://daxiv.com
01/02 15:27, 57F
→
07/07 11:12, 4年前 , 58F
鑰匙曝露出來，因為pu https://noxiv.com
07/07 11:12, 58F
‣ 更多 greatwall 的文章
文章代碼(AID): #1HoogjRC (Math)