發佈時間:2013-02-07
There is a new "largest known prime number".
Extra footage:
http://youtu.be/o0ZOs7sMS7k
More on Mersenne Primes:
http://www.youtube.com/watch?v=PLL0mo...
Perfect Numbers:
http://www.youtube.com/watch?v=ZfKTD5...
Googolplex:
http://www.youtube.com/watch?v=8GEebx...
Graham's Number:
http://www.youtube.com/watch?v=XTeJ64...
This video features Dr Tony Padilla from the University of Nottingham.
Website:
http://www.numberphile.com/
Numberphile on Facebook:
http://www.facebook.com/numberphile
Numberphile tweets:
https://twitter.com/numberphile
Google Plus:
http://bit.ly/numberGplus
Videos by Brady Haran
類別
科學與技術
http://sa.ylib.com/MagCont.aspx?Unit=columns&id=1519
為什麼要學質數?
RSA演算法終於讓質數有了大應用,但何以質數要納入基礎數學的學習大綱?
撰文/張海潮
我在讀小學的時候,有一陣子對質數非常著迷。我的生日17號是質數,圍棋棋盤19路是質數,人過世了做7是質數,黑色13號星期五是質數,甚至當年有一線到三張犁的公車43路,也是質數。
著迷歸著迷,不過是發現了身邊有些數恰好是質數,仔細想來,常見的數中,非質數反而更多。
進了數學系之後,頗有一些質數的理論要學,但是似乎與應用沾不上邊。以與數學最靠近的物理來說,大致沒有什麼物理概念是跟質數扯上關係的。假想某一個實驗的結果是「粒子A的質量是粒子B質量的23倍」,23是質數這件事,應該不會牽拖到任何物理意涵吧?
的確,有很長的一段時間,質數理論只局限在純數學的範疇。一直到1978年,美國麻省理工學院的瑞維斯特、希米爾、艾德曼聯手出擊,將質數帶進密碼系統,發明了「RSA密碼演算法」(RSA cipher algorithm),並廣泛在商業上使用,人們才如夢初醒:原來,純數學的研究也可以開啟巨大的商機。
RSA密碼演算法可簡短描述如下:
銀行為了讓客戶可以利用電子通訊來進行客戶與銀行之間私密的商業行為,對外公佈兩個數N、e,其中N=pq是兩個質數p、q的乘積,e是一個與(p-1)(q-1)互質的數,亦即e和(p-1)(q-1)除了1以外,無任何公因數。N與e稱為公鑰,每個人都可以看到,但是卻無法知道N背後的p和q,當然也不知道(p-1)(q-1)的值。
客戶先把委託銀行處理的文件(例如要求匯出一筆款項)數位化之後,得到一個小於p、q的數目a,a稱為明文。然後將ae除以N之後的餘數r傳給銀行,r稱為密文。從a得到r的過程稱為加密,截密者可以截到r,但是無法知道a。
銀行本身則保留一個密鑰d,滿足ed除以(p-1)(q-1)的餘數是1。在接到客戶送來的密文r之後,銀行計算rd,然後再除以N,餘數就是客戶原始的明文a。
整個保密的關鍵在於截密者不知道p和q,如果知道,就可以據以算出(p-1)(q-1),並且透過e來算d。因此p和q必須是一個「至少數百位的大質數」,讓截密者永遠無法將N分解為p、q的乘積。
【欲閱讀更豐富內容,請參閱科學人2010年第95期1月號】
http://en.wikipedia.org/wiki/Prime_number
The smallest 168 prime numbers (all the prime numbers under 1000) are:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 (sequence A000040 in OEIS).
The set of all primes is often denoted P.
Type |
Prime |
Number of decimal digits |
Date |
Found by |
---|
[url=/wiki/Mersenne_prime]Mersenne prime[/url] |
257,885,161 − 1 |
17,425,170 |
January 25, 2013 |
[url=/wiki/Great_Internet_Mersenne_Prime_Search]Great Internet Mersenne Prime Search[/url] |
not a Mersenne prime ([url=/wiki/Proth_number]Proth number[/url]) |
19,249 × 213,018,586 + 1 |
3,918,990 |
March 26, 2007 |
[url=/wiki/Seventeen_or_Bust]Seventeen or Bust[/url] |
[url=/wiki/Factorial_prime]factorial prime[/url] |
150209! + 1 |
712,355 |
October 2011 |
[url=/wiki/PrimeGrid]PrimeGrid[/url][url=#cite_note-21][21][/url] |
[url=/wiki/Primorial_prime]primorial prime[/url] |
1098133# - 1 |
476,311 |
March 2012 |
[url=/wiki/PrimeGrid]PrimeGrid[/url][url=#cite_note-22][22][/url] |
[url=/wiki/Twin_prime]twin primes[/url] |
3756801695685 × 2666669 ± 1 |
200,700 |
December 2011 |
[url=/wiki/PrimeGrid]PrimeGrid[/url][url=#cite_note-23][23][/url] |