為什麼這篇質因數分解公式鄉民發文收入到精華區：因為在質因數分解公式這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者greatwall ()看板Math標題[其他] 數學白癡問質因數分解時間Thu Jun 27 ...
質因數分解公式 在 乙烯的讀書帳⌬ Instagram 的最讚貼文
2021-05-30 07:28:38
❀✿𝕡𝕣𝕖𝕡𝕒𝕣𝕖 𝕗𝕠𝕣數理資優班考試❀✿#烯數資準備方法 「不論是否榜上有名，都要相信自己是生命的饋贈」 複試： 化學-酸鹼中和、反應式平衡、加熱硫酸銅的重量變化、水溶液 出現一些從來沒有看過的化學式，然後數字也不好算ಠ_ಠ不要卡一題卡太久，反正有空著是正常的，就去看後面有沒有會的先寫 地...
我是人文科系畢業的，看到張益唐對孿生質數猜想的證明做出很大貢獻的新聞
以外行人看熱鬧的心情來看待這件事
這新聞忽然引發我的疑問，希望這裡的高手能否以「科普」的方式來解答
我的疑問是：為何質因數分解（尤其是非常大的數字）如此困難？
就一個數學只學到高中社會組數學的我來說，在小學學到的質因數分解
就是用短除法來分解，不過除此方法外，從國中數學課本到高中社會組數學課本
完全就沒提到其他方法了
因為質因數分解是在國小就學了，所以用一種「感覺上」的判斷，會誤以為質因數分解
好像不難，應有規則可循
但弔詭在這裡，以社會組數學所能學到的來說，真的去做質因數分解，而且是對
不小的整數做分解，比如 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