Re: 質數的極限

看板ask-why (知識奧秘)作者ronnywang (大家捐血吧)時間21年前 (2003/12/28 22:06)推噓3(3推 0噓 0→)

留言3則, 2人參與討論串1/1

※ 引述《hanshiuan (黃皮)》之銘言： : ※ 引述《same (慢慢)》之銘言： : : 有實作啦，不過到現在都還只做出幾個 bit 而已，因為干擾很嚴重， : : 很不好實作，所以真要實用，除非再來一個曼哈坦計劃等級的趕工， : : 不然十年內應該還看不到一台可用的產品。 : 請問一下，什麼是①質數加密法～ : 　　　　　　　　②量子電腦～　啊？？　　　謝謝 (1) 質數加密法今天選兩個質數 P,Q (ex: P=3,P=5 ) 另 N = P x Q ( N=15 ) 再取一個與 P-1 Q-1 互質的 E ( E = 3 ) P和Q是自己知道的, 別人都無法知道 N,E是任何人都可以知道的今天別人有一個數字M要傳給我 (M=12) 我要他加密後再傳給我他要做 C = M^E mod N (M^E=1728, (1728 mod N) = 3) 然後再把 C 丟給我 (C = 3, 由上式) C就是經過加密的資料我收到C後,只要先找到一個D, 符合下式 E * D mod (P-1)x(Q-1) = 1 (D = 3) 然後再做 M = C^D (mod N) (C^D=27 ,(27 mod N) = 12) 就得回 M 了 (M = 12) 很神奇吧..中間的C被人得走的話..他也無法解碼.. 因為解碼最重要的一步就是要找出一個 D D符合 E * D mod (P-1)x(Q-1) = 1 但是別人不知道 P,Q 分別是多少只知道 N = P x Q 你可能會認為 N = P x Q 因式分解馬上就能找出來兩個質數.. 但是當P,Q選的是數百位數, 數千位數的兩個質數呢?? 隨便找個質數很快..好像有聽說一百位數的話平均六百個數字就有一個質數用亂數亂選很快就能找出一個很大的質數但是要從一個很大的數字 N 中找出他是哪兩個質數相乘就要很久的時間.. 所以質數加密法是很難破解的需要很長很長很長的時間 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.95.27