0

0
0

文字

分享

0
0
0

做個除法吧:307位數的除法

科景_96
・2011/02/10 ・715字 ・閱讀時間約 1 分鐘 ・SR值 511 ・六年級

Original publish date:Jun 05, 2007

編輯 John C. H. Chen 報導

一群德國數學家藉由數百台電腦的協助,終於把一個長達307位的整數分解成三個質數的乘積。

目前網路上把資料加密的方法,簡單的說就是把你要傳送的資料轉換成一個質數(數A),然後乘上另外一個很大的數(數B)來做加密的動作,而這個數B則是兩個很大的質數的乘積。目前普遍使用的RSA加密方式在傳送資料的時候會有一個公鑰(public key),還有一組由兩個質數所構成的私鑰(privite key)。要解開由公鑰加密的訊息,就要用到由私鑰中的兩個質數來把這個公鑰解開。目前已知要破解這種加密方式的唯一作法就是硬上,把一個一個的質數拿來試。這是絕對的硬碰硬,不但考驗挑戰者的程式技術,更現實的考驗就是挑戰者的硬體設備。

這次這群由德國波昂大學的Thorsten Kleinjung領軍的數學家挑戰的是個307位長的整數,如果用二進位碼來記這個數,長度是1017位,距離我們目前所使用的1024位已經不是太遠了。為什麼現在用的是1024呢?因為上個公用標準512已經在1999年的時候被破解了…

這次的挑戰,他們利用了上百台電腦來解決這個問題。那麼解決這個問題要讓這些電腦計算多久呢?合計所有的電腦計算時間,大約是95年。這個結果簡單的說就是,這個問題可以解決,不過代價驚人。而這次成功解決這個問題的關鍵之一是技術方面的突破,解決了其中”matrix step”的限制。

瑞士Swiss Federal Institute of Technology的Arjen Lenstra則表示目前市面上的電視遊樂器Play Station 3,由於是專門設計用來處理數字運算,所以可能在處理分解質數上會有很好的表現。因此Kleinjung就表示,他考慮集合上千台或是上萬台PS3來實際測試PS3的能力。

對於密碼有遭破解的風險,RSA的發明人之一,MIT的Ronald Rivest就認為數學家對分解質數的進展當然會是編碼技術的威脅。不過他似乎並不在意,只簡單的表示:他們早就建議用2048位的編碼了。「程式是很有彈性的」。

參考來源:

文章難易度
科景_96
426 篇文章 ・ 7 位粉絲
Sciscape成立於1999年4月,為一非營利的專業科學新聞網站。

0

2
2

文字

分享

0
2
2
【成語科學】運籌帷幄:古人不用筆算數學?一隻小竹棍居然可以開三次方根、解方程式!
張之傑_96
・2023/07/28 ・1261字 ・閱讀時間約 2 分鐘

劉邦(漢高祖)打敗項羽,取得天下,建立漢朝。一天舉行盛大宴會,他問群臣:「我為什麼會勝?項羽為什麼會敗?」群臣都說劉邦善於用人,項羽恰恰相反。劉邦點頭稱是,司馬遷在《史記‧高祖本紀》記下劉邦說的一段話

夫運籌帷幄之中,決勝於千里之外,吾不如子房。

帷幄,指營帳子房,是張良的字籌,指算籌,是古時的運算工具。這段話的意思是說,張良在營帳中運用算籌計算,就能決勝千里之外,這方面我(劉邦)不如張良。因此,這個成語的原意是在營帳中策劃謀略,後來泛指謀劃或指揮。讓我們造兩個句吧。

要不是孔明運籌帷幄,劉備哪有三分天下的機會!

在里長的運籌帷幄下,為社區更新取得有利的條件。

不用筆,那用什麼?

成語的出典說了,句子也造了,接下去就要談談這個成語的科學意義。我們現在演算數學,都是用筆在紙上運算,也就是筆算。古人呢?古人從來不用筆算,而是使用工具運算。元代以前使用算籌,元代以後使用算盤

算盤一直使用到 1980 年代,小朋友家裡可能還有。至於算籌,只有少數博物館裡才能看到。

國立自然科學博物館內藏的漢朝骨製算籌複製品。圖/wikipedia

其實算籌只是一根根小竹棍,外形和筷子差不多。小朋友千萬不要看輕這些小竹棍,中國古代的數學曾經輝煌一時,就是用這些小竹棍運算出來的。

驚人的運算能力 曾經輝煌一時的數學成就

算盤被木框框住,計算能力受到限制。凡是算盤能算的,算籌一定能算。反過來,算籌所能算的,算盤就不見得勝任。算盤主要是生意人用的,算籌可作各種運算,數學家喜歡用它。中國的數學宋代發展到顛峰,元代以後不進反退,到了明代已沒人懂得宋代的數學了。

算籌平時放在算袋裡,繫在腰上,運算時取出,在席子上或桌子上擺弄。除了加減乘除,還能開平方、開立方,甚至解高次方程等高中才學得到的數學!關於算袋,有個小故事,傳說秦皇島東巡時,把算袋扔到海裡,變成了烏賊,所以烏賊又稱算袋魚。

十四世紀朱世傑《四元玉鑒》中的「古法七乘方圖」,紀錄宋代展出的「楊輝三角形」,就是我們現在所說的「巴斯卡三角形」。圖中一根根長條物就是當時用來計算的「算籌」。楊輝三角形的產生也顯見宋代數學已經發展出高次多項式的乘法。圖/wikipedia

數學家用算籌運算時,有時擺弄得極快,不要說外行人,連內行人的眼睛幾乎都跟不上,所以古人用「運籌如飛」來形容。因此,用算籌運算,運算過程不會留下記錄,一陣擺弄之後,最後得出答案。這對一般才質的人來說,學起來的確有點困難。

張之傑_96
98 篇文章 ・ 221 位粉絲
張之傑,字百器,出入文理,著述多樣,其中以科普和科學史較為人知。

0

3
2

文字

分享

0
3
2
密碼怕被盜,不用密碼驗證反而更可靠? Passkeys 甩開帳密規則
PanSci_96
・2023/03/18 ・2610字 ・閱讀時間約 5 分鐘

永豐銀行在過年期間傳出多位卡友信用卡被盜刷,而且明明都使用 OTP 一次性密碼驗證了,卻還是難逃駭客魔爪。難道,我們已經沒有安全的交易方法了嗎?

好消息是,Google 、 Apple 、 Microsoft 都不約而同宣布導入「Passkeys」無密碼驗證技術,只要使用生物辨識,使用者不需要再創作密碼,大幅減少被破解或是被側錄盜帳號的機率。

Passkeys 用作原理

也許你會提出疑問,指紋登入不是早就有了嗎?又與二階段驗證(Two-Factor Authentication, 2FA)看上去十分類似,這套「無密碼驗證」機制,我們真的可以相信嗎?

首先,我們先來釐清Passkeys 的運作原理。在 Passkeys 的運作之中,一共有三個重要的角色:使用者 Device、平台供應商 Authenticator、應用服務 Relying Party。

在第一次申請 Passkeys 功能並使用生物驗證時,便會生成一組對應的公鑰與私鑰,公鑰存放在應用服務端(如:網路銀行)、而私鑰則保存在使用者的硬體裝置上(如:手機);每當未來要進行 Passkeys 登入時,應用程式便會發起一個驗證請求,要求使用者利用裝置內的私鑰進行簽章,以證明自己的身分。

當然,為了確保當下持有手機的是使用者本人,手機裝置就會要求透過指紋等生物驗證機制,完成識別後,再使用裝置內的私鑰進行簽章回傳給應用服務,應用服務端則利用他們所持有的公鑰,來驗證簽章的效力。

我們可以把登入情境變成一張如下的邏輯架構:

密碼與鑰匙

更進一步討論,就得要先知道「公開金鑰密碼」(Public Key Cryptography, PKC)與「公鑰」(Public Key)、「私鑰」(Private Key)的概念。

一般所說的「加密」概念,就是希望只有對方能夠「解密」。

早期的「對稱式密碼學」,在加密和解密時均使用同一把鑰匙,如此一來便衍生了一個小問題——多了一個「額外的秘密」需要被傳遞,這樣既麻煩也不安全。

後來就出現了「非對稱密碼學」,也就是前述提到的公開金鑰密碼學。在這個理論中將用到兩把不同的鑰匙——「公鑰」及「私鑰」;私鑰僅留存給使用者,公鑰則是公開給所有人。演算法分別使用這兩把鑰匙進行加密與解密,具有單向、無法回推等特徵。

「加密」概念就是希望只有對方能夠用「鑰匙」「解密」。圖/Envato Elements

如此一來,可以達到不同的應用方式:

第一種是「傳遞秘密」,每個人都持有一把自己的私鑰、向大家公開一把成對的公鑰,任何人都可以「用公鑰加密訊息」給我、並且只有我可以「用私鑰解密訊息」看到秘密訊息的內容。

第二種常見的應用方式則是 Passkeys 架構中所用到的「數位簽章」。數位簽章的邏輯正好和傳遞秘密相反:「用私鑰加密簽章」並「用公鑰解密驗章」;如此一來,任何人都能持有的公鑰,便能用以驗證訊息是否確實由世上唯一擁有私鑰的使用者所簽名發出。

重新回來看 Passkeys 的架構,就不難理解為什麼 Passkeys 在不使用密碼的前提下,也能透過裝置上的私鑰,來向應用服務進行身分驗證。當然,Passkeys 的安全與強大之處並不只在於公鑰密碼系統,而是可以完全擺脫掉「帳號密碼」的概念,進而避免非常多的威脅。

從根本上解決問題

一般來說,在登入帳號時所使用的「密碼」,並不會直接被明文儲存在應用服務的伺服器裡,會透過編碼、雜湊、加密等各種方式進行儲存。

即便如此,太過簡單的弱密碼容易被暴力或查表破解。此外,駭客也可以透過網站釣魚(Phishing)或鍵盤側錄(KeyLogger)等方式偷取使用者的密碼,再轉手將偷來的資訊傳給應用服務進行中間人攻擊(Man-in-the-Middle Attack);常見的簡訊驗證碼等二階段驗證方式,也可能受此攻擊的影響。

Passkeys 則從根本上解決了釣魚網站的威脅。存在使用者裝置中的 Passkeys 並不僅是一把私鑰,它連帶也儲存了應用服務網址、使用者帳號等資訊;無論釣魚網站做的與原服務有多相像,只要來源並非原本的服務網站,Passkeys 功能就不會被啟動,駭客自然就無法執行驗證或偷取到任何資訊。

而在跨裝置登入上,流程會是:使用者在筆電上開啟應用服務網站,選擇以 Passkeys 登入,網站會跳出一個 QRCode,使用者只要用存有私鑰的那隻手機掃描 QRCode,便會開啟 Passkeys 功能,讓使用者透過生物驗證完成登入。

手機掃描 QRCode 便會開啟 Passkeys 功能。圖/Envato Elements

這個過程不需要用到任何的「帳號」,因為 Passkeys 本身就儲存了使用者是誰的身分資訊,而使用 Passkeys 跨裝置登入時需要掃描 QRCode 來啟動的這一點,是為了避免駭客利用來進行中間人攻擊;Passkeys 要求這兩個裝置之間必須有藍牙連接,也就是必須在一定的物理範圍之內,裝置之間才能夠順利啟動 Passkeys 認證。

帶來的便利

對一般使用者來說,除了安全性以外,便利性也非常重要。

前述提及 Passkeys 的無密碼驗證機制,其實就等同於讓「裝置」擁有代表使用者本人的效力,那麼,若裝置不慎遺失、還能簡單地取回自己的身分嗎?答案是可以的。

使用者與提供 Passkeys 功能的平台供應商之間,原則上本來就會有相互驗證的方式,例如本來的帳號密碼登入、或者是額外的找回帳號機制,透過這些方式找回並登入帳號後,就可以進行設置,停用舊有 Passkeys 或啟用新的 Passkeys。

此外,Passkeys 提供多裝置同步私鑰的功能,以使用者對平台提供商的信任為前提,平台可能會在其雲端中儲存使用者的私鑰,以便在使用者需要的時候,可以將該私鑰輕鬆地同步到相同作業系統的其他裝置上,讓使用者也可以利用平板或電腦等裝置進行驗證登入。

Passkeys 帶來的便利性,可謂使用者的一大福音。圖/Envato Elements

另外,使用不同作業系統的裝置,一樣能用原本的私鑰登入;系統會在新的裝置上生成一組新的公私鑰繼續運作。也就是說,不管你是 Android 轉 iOS,還是 iOS 轉 Android,都不需重新設定,對使用者來說,可謂一大福音!

歡迎訂閱 Pansci Youtube 頻道 獲取更多深入淺出的科學知識!

PanSci_96
1190 篇文章 ・ 1751 位粉絲
PanSci的編輯部帳號,會發自產內容跟各種消息喔。

2

2
2

文字

分享

2
2
2
買樂透真的可以賺錢?大數法則揭示了賭博的真相!——《統計,讓數字說話》
天下文化_96
・2023/03/05 ・2394字 ・閱讀時間約 4 分鐘

  • id S. Moore、諾茨 William I. Notz
  • 譯者:鄭惟厚、吳欣蓓

什麼是大數法則?

期望值的定義是:它是可能結果的一種平均,但在計算平均時,機率大的結果占的比重較高。我們認為期望值也是另一種意義的平均結果,它代表了如果我們重複賭很多次,或者隨機選出很多家戶,實際上會看到的長期平均。這並不只是直覺而已。數學家只要用機率的基本規則就可以證明,用機率模型算出來的期望值,真的就是「長期平均」。這個有名的事實叫做大數法則。

大數法則
大數法則(law of large numbers)是指,如果結果為數值的隨機現象,獨立重複執行許多次,實際觀察到的結果的平均值,會趨近期望值。

大數法則和機率的概念密切相關。在許多次獨立的重複當中,每個可能結果的發生比例會接近它的機率,而所得到的平均結果就會接近期望值。這些事實表達了機遇事件的長期規律性。正如我們在第 17 章提過的,它們是真正的「平均數定律」。

大數法則解釋了:為什麼對個人來說是消遣甚至是會上癮的賭博,對賭場來說卻是生意。經營賭場根本就不是在賭博。大量的賭客贏錢的平均金額會很接近期望值。賭場經營者事先就算好了期望值,並且知道長期下來收入會是多少,所以並不需要在骰子裡灌鉛或者做牌來保證利潤。

賭場只要花精神提供不貴的娛樂和便宜的交通工具,讓顧客川流不息進場就行了。只要賭注夠多,大數法則就能保證賭場賺錢。保險公司的運作也很像賭場,他們賭買了保險的人不會死亡。當然有些人確實會死亡,但是保險公司知道機率,並且依賴大數法則來預測必須給付的平均金額。然後保險公司就把保費訂得夠高,來保證有利潤。

  • 在樂透彩上做手腳

我們都在電視上看過樂透開獎的實況轉播,看到號碼球上下亂跳,然後由於空氣壓力而隨機彈跳出來。我們可以怎麼樣對開出的號碼做手腳呢? 1980 年的時候,賓州樂透就曾被面帶微笑的主持人以及幾個舞台工作人員動了手腳。

他們把 10 個號碼球中的 8 顆注入油漆,這樣做會把球變重,因此可保證開出中獎號碼的 3 個球必定有那 2 個沒被注入油漆的號碼。然後這些傢伙就下注買該 2 個號碼的所有組合。當 6-6-6 跳出來的時候,他們贏了 120 萬美元。是的,他們後來全被逮到。

歷史上曾有主持人在樂透上做手腳,後來賺了 120 萬美元隨後被逮捕。圖/envatoelements

深入探討期望值

跟機率一樣,期望值和大數法則都值得再花些時間,探討相關的細節問題。

  • 多大的數才算是「大數」?

大數法則是說,當試驗的次數愈來愈多,許多次試驗的實際平均結果會愈來愈接近期望值。可是大數法則並沒有說,究竟需要多少次試驗,才能保證平均結果會接近期望值。這點是要看機結果的變異性決定。

結果的變異愈大,就需要愈多次的試驗,來確保平均結果接近期望值。機遇遊戲一定要變化大,才能保住賭客的興趣。即使在賭場待上好幾個鐘頭,結果也是無法預測的。結果變異性極大的賭博,例如累積彩金數額極大但極不可能中獎的州彩券,需要極多次的試驗,幾乎要多到不可能的次數,才能保證平均結果會接近期望值。

(州政府可不需要依賴大數法則,因為樂透彩金不像賭場的遊戲,樂透彩用的是同注分彩系統。在同注分彩系統裡面,彩金和賠率是由實際下注金額決定的。舉例來說,各州所辦的樂透彩金,是由全部賭金扣除州政府所得部分之後的剩餘金額來決定的。賭馬的賠率則是決定於賭客對不同馬匹的下注金額。)

雖然大部分的賭博遊戲不及樂透彩這樣多變化,但要回答大數法則的適用範圍,較實際的答案就是:賭場的贏錢金額期望值是正的,而賭場玩的次數夠多,所以可以靠著這個期望值贏錢。你的問題則是,你贏錢金額的期望值是負的。全體賭客玩的次數合起來算的話,當然和賭場一樣多,但因為期望值是負的,所以以賭客整體來看,長期下來一定輸錢。

然而輸的金額並不是由賭客均攤。有些人贏很多錢,有些人輸很多,而有些人沒什麼輸贏。賭博帶給人的誘惑,大部分是來自賭博結果的無法預測。而賭博這門生意仰賴的則是:對賭場來說,結果並非不可測的。

對賭場來說,贏錢金額期望值為正。圖/envatoelements
  • 有沒有保證贏錢的賭法?

把賭博很當回事的賭客常常遵循某種賭法,這種賭法每次下注的金額,是看前幾次的結果而定。比如說,在賭輪盤時,你可以每次把賭注加倍,直到你贏為止—或者,當然,直到你輸光為止。即使輪盤並沒有記憶,這種玩法仍想利用你有記憶這件事來贏。

你可以用一套賭法來戰勝機率嗎?不行,數學家建立的另一種大數法則說:如果你沒有無窮盡的賭本,那麼只要遊戲的各次試驗(比如輪盤的各次轉動)之間是獨立的,你的平均獲利(期望值)就會是一樣的。抱歉啦!

  • 高科技賭博

全美國有超過 700,000 台吃角子老虎(拉霸)。從前,你丟硬幣進去再拉下把手,轉動三個輪子,每個輪子有 20 個圖案。但早就不是這樣了。現在的機器是電動遊戲,會閃出許多很炫的畫面,而結果是由隨機數字產生器決定的。

機器可以同時接受許多硬幣,有各種讓你眼花撩亂的中獎結果,還可以多台連線,共同累積成連線大獎。賭徒仍在尋找可以贏錢的賭法,但是長期下來,隨機數字產生器會保證賭場有 5% 的利潤。

——本文摘自《統計,讓數字說話》,2023 年 1 月,天下文化出版,未經同意請勿轉載。

所有討論 2
天下文化_96
129 篇文章 ・ 614 位粉絲
天下文化成立於1982年。一直堅持「傳播進步觀念,豐富閱讀世界」,已出版超過2,500種書籍,涵括財經企管、心理勵志、社會人文、科學文化、文學人生、健康生活、親子教養等領域。每一本書都帶給讀者知識、啟發、創意、以及實用的多重收穫,也持續引領台灣社會與國際重要管理潮流同步接軌。