中央論壇 - CENTER BBS

標題: 傳說中的魔王題 [打印本頁]

作者: 兔寶寶 時間: 2007-7-16 14:56
標題: 傳說中的魔王題
我們小學時都學過：如果一個比1大的整數，只能被1和本身整除，稱之為質數。
例如：2 、 3 、 5 、 7 、 13...等

判斷一個給定數是否為質數，最簡單的方法就是將所有不大於給定數開根號的那些數來除除看，但這一種方法一旦給定數很大時，計算量就非常驚人。

講了一大堆，我們的問題要問的是：給定一個數，解出它是由哪兩個質數相乘所得，
例如：給定143，你要回答這是由11乘以13所得的數。

回到正題，我們要分解的數不只是143這麼短的一個數，我們要分解的題目在下面：

請將以下這個數質因數分解----

18819881292060796383869723946165043980716356337941
73827007633564229888597152346654853190606065047430
45317388011303396716199692321205734031879550656996
221305168759307650257059

意思就是上面那個一大串的數字是由兩哪個相異質數相乘所構成。

[ 本帖最後由兔寶寶於 2007-7-17 17:37 編輯 ]

作者: 鬼願 時間: 2007-7-16 15:38
這應該是出來整人亂打的...最離譜到67位數相成...

作者: 兔寶寶 時間: 2007-7-16 16:48
<嘻~>飄大可以在想想喔!!

這個有解^0^~

作者: 展２ 時間: 2007-7-16 23:20
這個難度已經超過高中數學的領域了...投降投降= =
:(
我在電視中曾經看過最大質數還附加算法
是不是跟這個有關阿!?

作者: herryl1 時間: 2007-7-17 12:27
網路找的資料，給大家做參考
答案：
P1 = 39807508642406493739712550055038649119906436234252
6708406385189575946388957261768583317

P2 = 47277214610743530253622307197304822463291469530209
7116459852171130520711256363590397527

上面的 Q = P1 X P2 是迄今為止已知的最大的用通用演算法分解的大數，上述分解結果是由的德國的 J. Franke 和 T. Kleinjung 在 2003 年12月 3 號得到的。有興起可以去Google搜尋RSA Security - The RSA Challenge Numbers。

這樣的問題稱為大數分解(factoring)問題。大數分解對於加密的可靠性非常重要，如果你可以找到一個分解大數的快速演算法，那麼你就可以輕而易舉地破解現在的基於 RSA 演算法的加密系統。

任意給兩個大質數，我們可以很容易地算出它們的乘積。但反過來，給出該乘積，求它的分解卻非常難。
人們把這樣的函數稱為“單向函數(one-way function)”。但現在還沒有人能夠從理論上證明單向函數的存在。

大數分解顯然是屬於 NP(Nondeterministic Polynomial，非決定型多項式的) 的。但迄今為止，我們還不知道它是否屬於 P(deterministic Polynomial，決定型多項式的)，還沒有人發現大數分解的多項式演算法。數學家們懷疑，大數分解根本上不存在一個通用的多項式演算法，但這一點也沒有得到證明。

Peter Shor 給出了一個能在量子電腦(quantum computer)上進行大數分解的多項式演算法，Shor's algorithm。但目前為止它還只是於理論上存在，實際中人們還不知道如何構造一台量子電腦。

作者: williambrian 時間: 2007-7-17 14:00
太誇張了辣:time:
這題我算的出來我也不會只在台灣了

作者: 兔寶寶 時間: 2007-7-17 17:36
答案：
P1 = 39807508642406493739712550055038649119906436234252
6708406385189575946388957261768583317

P2 = 47277214610743530253622307197304822463291469530209
7116459852171130520711256363590397527

上面的 Q = P1 X P2 是迄今為止已知的最大的用通用演算法分解的大數，上述分解結果是由的德國的 J. Franke 和 T. Kleinjung 在 2003 年12月 3 號得到的。有興起可以去Google搜尋RSA Security - The RSA Challenge Numbers。

這樣的問題稱為大數分解(factoring)問題。大數分解對於加密的可靠性非常重要，如果你可以找到一個分解大數的快速演算法，那麼你就可以輕而易舉地破解現在的基於 RSA 演算法的加密系統。

任意給兩個大質數，我們可以很容易地算出它們的乘積。但反過來，給出該乘積，求它的分解卻非常難。
人們把這樣的函數稱為“單向函數(one-way function)”。但現在還沒有人能夠從理論上證明單向函數的存在。

大數分解顯然是屬於 NP(Nondeterministic Polynomial，非決定型多項式的) 的。但迄今為止，我們還不知道它是否屬於 P(deterministic Polynomial，決定型多項式的)，還沒有人發現大數分解的多項式演算法。數學家們懷疑，大數分解根本上不存在一個通用的多項式演算法，但這一點也沒有得到證明。

Peter Shor 給出了一個能在量子電腦(quantum computer)上進行大數分解的多項式演算法，Shor's algorithm。但目前為止它還只是於理論上存在，實際中人們還不知道如何構造一台量子電腦。

---------------------------------------------------------------------------

話說，herryl1大人答對了..:victory:

題目終了~

歡迎光臨中央論壇 - CENTER BBS (https://www.centerbbs.com/)