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