{"id":3751,"date":"2019-08-08T10:25:55","date_gmt":"2019-08-08T02:25:55","guid":{"rendered":"https:\/\/damogame.cn\/wordpress\/?p=3751"},"modified":"2019-08-08T10:25:55","modified_gmt":"2019-08-08T02:25:55","slug":"%e5%a6%82%e4%bd%95%e6%b7%b1%e5%85%a5%e6%b5%85%e5%87%ba%e5%9c%b0%e8%ae%b2%e8%a7%a3rsa%e5%af%86%e7%a0%81%ef%bc%9f","status":"publish","type":"post","link":"https:\/\/i007.cc\/wordpress\/archives\/3751","title":{"rendered":"\u5982\u4f55\u6df1\u5165\u6d45\u51fa\u5730\u8bb2\u89e3RSA\u5bc6\u7801\uff1f"},"content":{"rendered":"<div><a href=\"https:\/\/www.zhihu.com\/question\/304030251\/answer\/543201982\">\u539f\u6587\u5730\u5740<\/a><\/p>\n<div>\n<h2>\u4e00\u3001\u5bf9\u79f0\u52a0\u5bc6\u4e0e\u975e\u5bf9\u79f0\u52a0\u5bc6<\/h2>\n<p>\u4ece\u524d\u6709\u4e2a\u5973\u5b69\u53eb\u505aAlice\uff0c\u5979\u60f3\u544a\u8bc9Bob\u4e00\u4e2a\u79d8\u5bc6\u3002<\/p>\n<p>\u7136\u800c\u6709\u4e2a\u53ebEve\u7684\u4eba\u60f3\u8981\u5077\u542c\u3002\u6240\u4ee5Alice\u9700\u8981\u60f3\u529e\u6cd5<b>\u52a0\u5bc6<\/b>\u8fd9\u6761\u4fe1\u606f\uff0c\u9632\u6b62Eve\u5077\u542c\u3002<\/p>\n<figure data-size=\"normal\"><noscript><img decoding=\"async\" src=\"https:\/\/pic4.zhimg.com\/50\/v2-c041637f8c45a947162c9644f15c3f92_hd.jpg\" data-rawwidth=\"480\" data-rawheight=\"360\" data-size=\"normal\" data-caption=\"\" data-default-watermark-src=\"https:\/\/pic2.zhimg.com\/50\/v2-2d966e401fb9c3b32d61bd04d54752eb_hd.jpg\" class=\"origin_image zh-lightbox-thumb\" width=\"480\" data-original=\"https:\/\/pic4.zhimg.com\/v2-c041637f8c45a947162c9644f15c3f92_r.jpg\"\/><\/noscript><img decoding=\"async\" class=\"origin_image zh-lightbox-thumb lazy\" src=\"https:\/\/pic4.zhimg.com\/80\/v2-c041637f8c45a947162c9644f15c3f92_hd.jpg\" width=\"480\" data-rawwidth=\"480\" data-rawheight=\"360\" data-size=\"normal\" data-caption=\"\" data-default-watermark-src=\"https:\/\/pic2.zhimg.com\/50\/v2-2d966e401fb9c3b32d61bd04d54752eb_hd.jpg\" data-original=\"https:\/\/pic4.zhimg.com\/v2-c041637f8c45a947162c9644f15c3f92_r.jpg\" data-actualsrc=\"https:\/\/pic4.zhimg.com\/50\/v2-c041637f8c45a947162c9644f15c3f92_hd.jpg\" \/><\/figure>\n<p>\u53e4\u5178\u7684\u601d\u8def\u662f\uff1aAlice\u548cBob\u63d0\u524d\u51c6\u5907\u4e86\u4e00\u4e2a\u76d2\u5b50\uff0c\u5e76\u914d\u4e86\u4e24\u628a\u94a5\u5319\u3002\u6bcf\u6b21Alice\u628a\u79d8\u5bc6\u88c5\u8fdb\u76d2\u5b50\u91cc\uff0c\u7136\u540e\u7528\u94a5\u5319\u9501\u8d77\u6765\u5bc4\u7ed9Bob\u3002Bob\u63a5\u5230\u76d2\u5b50\u540e\u7528\u94a5\u5319\u6253\u5f00\uff0c\u4fbf\u53ef\u4ee5\u77e5\u9053\u8fd9\u4e2a\u79d8\u5bc6\u4e86\u3002<\/p>\n<p>\u8fd9\u79cd\u65b9\u5f0f\u53eb\u505a<b>\u5bf9\u79f0\u52a0\u5bc6<\/b>\u3002<\/p>\n<p>\u5176\u4e2d\uff0c\u8fd9\u4e2a\u79d8\u5bc6\u672c\u8eab\u53eb\u505a<b>\u660e\u6587<\/b>\uff0c\u7528\u6765\u52a0\u5bc6\u7684\u94a5\u5319\u53eb\u505a<b>\u5bc6\u94a5<\/b>\uff0c\u9501\u597d\u4e86\u7684\u4fe1\u606f\u53eb\u505a<b>\u5bc6\u6587<\/b>\u3002<\/p>\n<p>Alice\u548cBob\u90fd\u6709\u5bc6\u94a5\uff0c\u6240\u4ee5\u4ed6\u4eec\u90fd\u53ef\u4ee5\u968f\u610f\u5730\u628a\u660e\u6587\u7ffb\u8bd1\u6210\u5bc6\u6587\uff0c\u6216\u662f\u628a\u5bc6\u6587\u7ffb\u8bd1\u6210\u660e\u6587\u3002\u4f46Eve\u6ca1\u6709\u5bc6\u94a5\uff0c\u6240\u4ee5\u65e0\u6cd5\u7834\u89e3\u5bc6\u6587\u3002<\/p>\n<figure data-size=\"normal\"><noscript><img decoding=\"async\" src=\"https:\/\/pic3.zhimg.com\/50\/v2-4e440a0cac998b96dc74f584cf7f24b3_hd.jpg\" data-rawwidth=\"960\" data-rawheight=\"540\" data-size=\"normal\" data-caption=\"\" data-default-watermark-src=\"https:\/\/pic2.zhimg.com\/50\/v2-a9f2acc1a24b1bd3531af03ad1f1da98_hd.jpg\" class=\"origin_image zh-lightbox-thumb\" width=\"960\" data-original=\"https:\/\/pic3.zhimg.com\/v2-4e440a0cac998b96dc74f584cf7f24b3_r.jpg\"\/><\/noscript><img decoding=\"async\" class=\"origin_image zh-lightbox-thumb lazy\" src=\"https:\/\/pic3.zhimg.com\/80\/v2-4e440a0cac998b96dc74f584cf7f24b3_hd.jpg\" width=\"960\" data-rawwidth=\"960\" data-rawheight=\"540\" data-size=\"normal\" data-caption=\"\" data-default-watermark-src=\"https:\/\/pic2.zhimg.com\/50\/v2-a9f2acc1a24b1bd3531af03ad1f1da98_hd.jpg\" data-original=\"https:\/\/pic3.zhimg.com\/v2-4e440a0cac998b96dc74f584cf7f24b3_r.jpg\" data-actualsrc=\"https:\/\/pic3.zhimg.com\/50\/v2-4e440a0cac998b96dc74f584cf7f24b3_hd.jpg\" \/><\/figure>\n<p>\u7136\u800c\uff0c\u5728\u73b0\u4ee3\u7f51\u7edc\u7684\u5b9e\u9645\u5e94\u7528\u4e2d\uff0c\u8fd9\u79cd<b>\u5bf9\u79f0\u52a0\u5bc6\u5374\u6709\u5f88\u591a\u5f88\u591a\u7684\u95ee\u9898<\/b>\uff01<\/p>\n<p>\u5176\u4e2d\uff0c\u6700\u5927\u7684\u95ee\u9898\u662f\uff1a<b>\u5f88\u591a\u60c5\u51b5\u4e0b\uff0cAlice\u548cBob\u53ef\u80fd\u6ca1\u6709\u673a\u4f1a\u63d0\u524d\u5546\u91cf\uff0c\u6240\u4ee5\u65e0\u6cd5\u751f\u6210\u76f8\u540c\u5bc6\u94a5\uff01<\/b><\/p>\n<p>\u6bd4\u5982\uff0c\u5982\u679c\u4f60\u60f3\u8981\u53d1\u9001\u4e00\u6761\u79d8\u5bc6\u4fe1\u606f\u7ed9\u6211\u3002\u5982\u679c\u91c7\u7528\u5bf9\u79f0\u52a0\u5bc6\u7684\u8bdd\uff0c\u54b1\u4eec\u7684\u624b\u673a\u5728\u5546\u8ba8\u5bc6\u7801\u7684\u65f6\u5019\uff0c\u9ed1\u5ba2\u53ef\u80fd\u5df2\u7ecf\u5728\u7a83\u542c\u4e86\u3002\u90a3\u6837\u7684\u8bdd\uff0c\u5bc6\u94a5\u5c31\u4f1a\u88ab\u9ed1\u5ba2\u7a83\u53d6\u4e86\u3002(\u2299\ufe4f\u2299)<\/p>\n<p>\u6240\u4ee5\u6211\u4eec\u9700\u8981\u66f4\u597d\u7684\u529e\u6cd5\uff0c\u5c31\u662f\u2014\u2014<b>\u975e\u5bf9\u79f0\u52a0\u5bc6<\/b>\u3002RSA\u662f\u5c31\u662f<b>\u975e\u5bf9\u79f0\u52a0\u5bc6<\/b>\u3002<\/p>\n<p>\u4e00\u822c\u7684\u94a5\u5319\u90fd\u662f\u65e2\u80fd\u4e0a\u9501\u3001\u4e5f\u80fd\u5f00\u9501\u7684\u3002<\/p>\n<p>\u4f46\u662f\uff0c\u975e\u5bf9\u79f0\u52a0\u5bc6\u4e2d\uff0c\u5bc6\u94a5\u6709\u4e24\u79cd\uff1a<b>\u516c\u6709\u5bc6\u94a5<\/b>\u3001<b>\u79c1\u6709\u79d8\u94a5<\/b>\u3002<\/p>\n<p><b>\u516c\u6709\u5bc6\u94a5\u7528\u4e8e\u4e0a\u9501\uff08\u52a0\u5bc6\uff09\u3002<\/b><\/p>\n<p><b>\u79c1\u6709\u5bc6\u94a5\u7528\u4e8e\u89e3\u9501\uff08\u89e3\u5bc6\uff09\u3002<\/b><\/p>\n<p>\u56e0\u4e3aAlice\u53ea\u9700\u8981\u4e0a\u9501\uff0c\u6240\u4ee5\u5979\u53ea\u9700\u8981\u516c\u6709\u5bc6\u5319\u5c31\u591f\u4e86\u3002\u79c1\u6709\u5bc6\u5319\u53ea\u6709Bob\u62e5\u6709\u3002<\/p>\n<p>Alice\u4f1a\u5148\u901a\u77e5Bob\uff1a\u6211\u8981\u544a\u8bc9\u4f60\u4e00\u4ef6\u4e8b\u3002\u7136\u540eBob\u63a5\u7740\u5c31\u4f1a\u751f\u6210\u4e00\u628a\u9501\uff0c\u5e76\u5236\u4f5c\u4e24\u79cd\u94a5\u5319\uff1a\u516c\u6709\u5bc6\u94a5\u548c\u79c1\u6709\u79d8\u94a5\u3002Bob\u4f1a\u628a\u516c\u6709\u5bc6\u94a5\u53d1\u7ed9Alice\uff0c\u7136\u540eAlice\u4f1a\u7528\u516c\u6709\u5bc6\u94a5\u52a0\u5bc6\u4fe1\u606f\u3002Alice\u628a\u4e0a\u9501\u7684\u5bc6\u6587\u53d1\u56de\u6765\u540e\uff0cBob\u518d\u7528\u81ea\u5df1\u7684\u79c1\u6709\u5bc6\u94a5\u89e3\u5bc6\uff0c\u5e76\u5f97\u5230\u660e\u6587\u3002<\/p>\n<p>\u6574\u4e2a\u8fc7\u7a0b\u4e2d\uff0c<b>\u53ea\u6709Bob\u62e5\u6709\u79c1\u6709\u5bc6\u94a5\u3002<\/b><\/p>\n<p><b>Bob\u7684\u79c1\u6709\u79d8\u94a5\u4e0d\u4f1a\u4ea4\u7ed9\u4efb\u4f55\u4eba\u7684\u3002<\/b><\/p>\n<p>\u7eb5\u4f7fEve\u83b7\u5f97\u4e86\u660e\u6587\u548c\u516c\u5f00\u5bc6\u94a5\uff0cEve\u4e5f\u65e0\u6cd5\u89e3\u5bc6\u3002\u56e0\u4e3a\u53ea\u6709\u79c1\u6709\u5bc6\u5319\u624d\u53ef\u4ee5\u89e3\u5bc6\u3002<\/p>\n<figure data-size=\"normal\"><noscript><img decoding=\"async\" src=\"https:\/\/pic4.zhimg.com\/50\/v2-7c44ed7c8dc938947fd7e30d44eabf04_hd.jpg\" data-rawwidth=\"960\" data-rawheight=\"540\" data-size=\"normal\" data-caption=\"\" data-default-watermark-src=\"https:\/\/pic4.zhimg.com\/50\/v2-4b9b407de56f2041ef1e325ad2623173_hd.jpg\" class=\"origin_image zh-lightbox-thumb\" width=\"960\" data-original=\"https:\/\/pic4.zhimg.com\/v2-7c44ed7c8dc938947fd7e30d44eabf04_r.jpg\"\/><\/noscript><img decoding=\"async\" class=\"origin_image zh-lightbox-thumb lazy\" src=\"https:\/\/pic4.zhimg.com\/80\/v2-7c44ed7c8dc938947fd7e30d44eabf04_hd.jpg\" width=\"960\" data-rawwidth=\"960\" data-rawheight=\"540\" data-size=\"normal\" data-caption=\"\" data-default-watermark-src=\"https:\/\/pic4.zhimg.com\/50\/v2-4b9b407de56f2041ef1e325ad2623173_hd.jpg\" data-original=\"https:\/\/pic4.zhimg.com\/v2-7c44ed7c8dc938947fd7e30d44eabf04_r.jpg\" data-actualsrc=\"https:\/\/pic4.zhimg.com\/50\/v2-7c44ed7c8dc938947fd7e30d44eabf04_hd.jpg\" \/><\/figure>\n<p>\u975e\u5bf9\u79f0\u52a0\u5bc6\u7684\u57fa\u672c\u539f\u7406\u5c31\u662f\u8fd9\u6837\u3002(\uff0d\u2200\uff1d)<\/p>\n<p>\u4e3a\u4e86\u6253\u9020\u8fd9\u4e24\u628a\u94a5\u5319\uff0c\u4e00\u628a\u7528\u4e8e\u4e0a\u9501\uff0c\u4e00\u628a\u7528\u4e8e\u5f00\u9501\uff0c\u6211\u4eec\u8fd8\u9700\u8981\u5229\u7528\u4e00\u4e9b\u8ba1\u7b97\u673a\u548c\u6570\u8bba\u65b9\u9762\u7684\u77e5\u8bc6\u3002(o\uff9fv\uff9f)\u30ce<\/p>\n<h2>\u4e8c\u3001\u8ba1\u7b97\u7406\u8bba\u7bc7<\/h2>\n<p>1\u3001\u65f6\u95f4\u590d\u6742\u5ea6<\/p>\n<p>\u6211\u4eec\u90fd\u77e5\u9053\u8ba1\u7b97\u673a\u7684\u8ba1\u7b97\u901f\u5ea6\u975e\u5e38\u5feb\uff0c\u8ba1\u7b97\u51e0\u5341\u4f4d\u6570\u7684\u52a0\u51cf\u6cd5\u90fd\u662f\u79d2\u51fa\u3002<\/p>\n<p>\u7136\u800c\uff0c\u867d\u7136\u8ba1\u7b97\u673a\u5f88\u5feb\uff0c\u4f46\u518d\u5feb\u4e5f\u662f\u6709\u4e0a\u9650\u7684\u3002\uff08\u256f\uff3f\u2570\uff09<\/p>\n<p>\u6bd4\u5982\u6211\u7535\u8111\u7684CPU\u4e3b\u9891\u662f2.40GHz\uff0c\u4e5f\u5c31\u662f\u8bf4\u6211\u7684\u7535\u8111\u6bcf\u79d2\u53ef\u4ee5\u8fdb\u884c2400000000\u6b21\u6700\u57fa\u672c\u7684\u8fd0\u884c\u3002<\/p>\n<figure data-size=\"normal\"><noscript><img decoding=\"async\" src=\"https:\/\/pic3.zhimg.com\/50\/v2-297884b1db0f01d5c7c4bb0dae7fb144_hd.jpg\" data-rawwidth=\"369\" data-rawheight=\"167\" data-size=\"normal\" data-default-watermark-src=\"https:\/\/pic2.zhimg.com\/50\/v2-63de0438cf0a22dabd8e16a998604220_hd.jpg\" class=\"content_image\" width=\"369\"\/><\/noscript><img decoding=\"async\" class=\"content_image lazy\" src=\"https:\/\/pic3.zhimg.com\/80\/v2-297884b1db0f01d5c7c4bb0dae7fb144_hd.jpg\" width=\"369\" data-rawwidth=\"369\" data-rawheight=\"167\" data-size=\"normal\" data-default-watermark-src=\"https:\/\/pic2.zhimg.com\/50\/v2-63de0438cf0a22dabd8e16a998604220_hd.jpg\" data-actualsrc=\"https:\/\/pic3.zhimg.com\/50\/v2-297884b1db0f01d5c7c4bb0dae7fb144_hd.jpg\" \/><figcaption>\u6b22\u8fce\u5927\u5bb6\u7ed9\u7b54\u4e3b\u6350\u94b1(\u273f\u25e1\u203f\u25e1)<\/figcaption><\/figure>\n<p>\u5bf9\u4e8e\u8ba1\u7b97\u673a\u6765\u8bf4\uff0c\u50cf\u52a0\u51cf\u4e58\u9664\u3001\u6bd4\u8f83\u5927\u5c0f\u3001\u5224\u65ad\u6761\u4ef6\u8fd9\u6837\u7684\u8fd0\u7b97\u90fd\u662f\u9700\u8981\u6d88\u8017\u65f6\u95f4\u7684\u3002\u800c\u8ba1\u7b97\u673a\u7684\u8ba1\u7b97\u80fd\u529b\u662f\u6709\u9650\u7684\uff0c\u5c31\u7b97\u662f\u8d85\u7ea7\u8ba1\u7b97\u673a\u201c\u5929\u6cb3\u4e8c\u53f7\u201d\uff0c\u6bcf\u79d2\u4e5f\u53ea\u80fd\u7b973.39\u4ebf\u4ebf\u6b21\u3002<\/p>\n<p>\u6240\u4ee5\u5bf9\u4e8e\u8ba1\u7b97\u673a\u7b97\u6cd5\u6765\u8bf4\uff0c\u6211\u4eec\u9700\u8981\u5229\u7528<b>\u65f6\u95f4\u590d\u6742\u5ea6<\/b>\u6765\u8861\u91cf\u4e00\u4e2a\u7a0b\u5e8f\u7684\u7b97\u6cd5\u6709\u591a\u8017\u65f6\u3002<\/p>\n<p>\u7b97\u6cd5\u590d\u6742\u5ea6\u6709\u5404\u79cd\u5404\u6837\u7684\uff0c\u6709 <img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=O%281%29\" alt=\"[\u516c\u5f0f]\" data-formula=\"O(1)\" \/> \u7684\uff0c <img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=O%28logn%29\" alt=\"[\u516c\u5f0f]\" data-formula=\"O(logn)\" \/>\u7684, <img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=O%28n%29\" alt=\"[\u516c\u5f0f]\" data-formula=\"O(n)\" \/>\u7684, <img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=O%28n%5E2%29\" alt=\"[\u516c\u5f0f]\" data-formula=\"O(n^2)\" \/>\u7684, <img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=O%282%5En%29\" alt=\"[\u516c\u5f0f]\" data-formula=\"O(2^n)\" \/>\u7684\u2026\u2026<\/p>\n<p>\u4e0a\u8ff0\u51e0\u4e2a\u590d\u6742\u5ea6\u7684\u7b97\u6cd5\u4e00\u4e2a\u6bd4\u4e00\u4e2a\u6162\u3002\u901a\u4fd7\u7684\u8bb2\uff0c\u5927O\u540e\u9762\u62ec\u53f7\u91cc\u9762<b>\u51fd\u6570\u7684\u589e\u957f\u901f\u5ea6\u8d8a\u5feb\uff0c\u7b97\u6cd5\u8d8a\u8017\u65f6<\/b>\u3002<\/p>\n<p>\u51c6\u786e\u5b9a\u4e49\u7684\u8bdd\u662f\u8fd9\u6837\u7684\uff1a\u5b58\u5728\u5e38\u6570 c \u548c\u51fd\u6570 f(N)\uff0c\u4f7f\u5f97\u5f53 N &gt;= c \u65f6 T(N) &lt;= f(N)\uff0c\u8868\u793a\u4e3a T(n) = O(f(n)) \u3002<\/p>\n<p>\u4e3e\u4e2a\u901a\u4fd7\u7684\u4f8b\u5b50\uff0c\u5982\u679c\u5bf9\u4e8e\u4e00\u4e2a\u7a0b\u5e8f\u6765\u8bf4\uff0c\u8f93\u5165\u89c4\u6a21 <img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=n%3D10%5E9\" alt=\"[\u516c\u5f0f]\" data-formula=\"n=10^9\" \/> \u7684\u8bdd\uff1a<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=O%281%29\" alt=\"[\u516c\u5f0f]\" data-formula=\"O(1)\" \/>\u7684\u7b97\u6cd5\u5927\u7ea6\u53ea\u75281\u6b21\u8fd0\u7b97\uff0c\u666e\u901a\u7535\u8111 <img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=10%5E%7B-9%7D\" alt=\"[\u516c\u5f0f]\" data-formula=\"10^{-9}\" \/> \u79d2\u5c31\u80fd\u7b97\u5b8c\u3002<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=O%28logn%29\" alt=\"[\u516c\u5f0f]\" data-formula=\"O(logn)\" \/> \u5927\u7ea6\u4f1a\u752830\u6b21\u8ba1\u7b97\uff08log\u7684\u5e95\u6570\u662f2\uff09\uff0c\u666e\u901a\u7535\u8111 <img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=10%5E%7B-8%7D\" alt=\"[\u516c\u5f0f]\" data-formula=\"10^{-8}\" \/> \u79d2\u7b97\u5b8c\u3002<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=O%28n%29\" alt=\"[\u516c\u5f0f]\" data-formula=\"O(n)\" \/>\u5927\u7ea6\u5c31\u662f <img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=10%5E9\" alt=\"[\u516c\u5f0f]\" data-formula=\"10^9\" \/> \u6b21\u8ba1\u7b97\uff0c\u666e\u901a\u7535\u8111\u9700\u8981\u4e00\u79d2\u5de6\u53f3\u3002<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=+O%28n%5E2%29\" alt=\"[\u516c\u5f0f]\" data-formula=\" O(n^2)\" \/> \u5927\u7ea6\u662f <img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=10%5E%7B18%7D\" alt=\"[\u516c\u5f0f]\" data-formula=\"10^{18}\" \/> \u6b21\u8ba1\u7b97\uff0c\u666e\u901a\u7535\u8111\u5927\u6982\u898130\u5e74\u3002<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=O%28n%21%29\" alt=\"[\u516c\u5f0f]\" data-formula=\"O(n!)\" \/> \u7684\u8bdd\uff0c\u4eba\u7c7b\u6240\u6709\u7535\u8111\u52a0\u5728\u4e00\u8d77\uff0c\u7b49\u592a\u9633\u70b8\u4e86\u90fd\u7b97\u4e0d\u5b8c\u3002\u2511(\uffe3\u0414 \uffe3)\u250d<\/p>\n<p>\uff08\u8fd9\u4e2a\u4f8b\u5b50\u5176\u5b9e\u975e\u5e38\u7684\u4e0d\u4e25\u683c\uff0c\u53ea\u662f\u6bd4\u8f83\u597d\u7406\u89e3\u800c\u5df2\uff0c\u60f3\u8981\u771f\u6b63\u7406\u89e3\u5927O\u8bf7\u8ba4\u771f\u8bfb\u5b9a\u4e49\u3002\uff09<\/p>\n<p>\u6211\u4eec\u53ef\u4ee5\u53d1\u73b0\uff0c \u65f6\u95f4\u590d\u6742\u5ea6\u76f4\u63a5\u5f71\u54cd\u4e86\u7a0b\u5e8f\u5b8c\u6210\u7684\u901f\u5ea6\u3002\u4ece\u4e0b\u56fe\u53ef\u77e5\uff0c\u5f53n\u589e\u5927\u7684\u65f6\u5019\uff0c\u4e0d\u540c\u65f6\u95f4\u590d\u6742\u5ea6\u7684\u8017\u65f6\u5dee\u8ddd\u7acb\u7aff\u89c1\u5f71\u3002<\/p>\n<figure data-size=\"normal\"><noscript><img decoding=\"async\" src=\"https:\/\/pic2.zhimg.com\/50\/v2-354b52193b7dccc3272d49f90931cb4c_hd.jpg\" data-rawwidth=\"600\" data-rawheight=\"368\" data-size=\"normal\" data-caption=\"\" data-default-watermark-src=\"https:\/\/pic2.zhimg.com\/50\/v2-6bdd3900e7f22378ea0d02a2193284cd_hd.jpg\" class=\"origin_image zh-lightbox-thumb\" width=\"600\" data-original=\"https:\/\/pic2.zhimg.com\/v2-354b52193b7dccc3272d49f90931cb4c_r.jpg\"\/><\/noscript><img decoding=\"async\" class=\"origin_image zh-lightbox-thumb lazy\" src=\"https:\/\/pic2.zhimg.com\/80\/v2-354b52193b7dccc3272d49f90931cb4c_hd.jpg\" width=\"600\" data-rawwidth=\"600\" data-rawheight=\"368\" data-size=\"normal\" data-caption=\"\" data-default-watermark-src=\"https:\/\/pic2.zhimg.com\/50\/v2-6bdd3900e7f22378ea0d02a2193284cd_hd.jpg\" data-original=\"https:\/\/pic2.zhimg.com\/v2-354b52193b7dccc3272d49f90931cb4c_r.jpg\" data-actualsrc=\"https:\/\/pic2.zhimg.com\/50\/v2-354b52193b7dccc3272d49f90931cb4c_hd.jpg\" \/><\/figure>\n<figure data-size=\"normal\"><noscript><img decoding=\"async\" src=\"https:\/\/pic4.zhimg.com\/50\/v2-5cb60be6a855dad326a3cc0ca189fcbc_hd.jpg\" data-rawwidth=\"879\" data-rawheight=\"624\" data-size=\"normal\" data-caption=\"\" data-default-watermark-src=\"https:\/\/pic3.zhimg.com\/50\/v2-5c42a173c152bee29b425b7ccbb8012e_hd.jpg\" class=\"origin_image zh-lightbox-thumb\" width=\"879\" data-original=\"https:\/\/pic4.zhimg.com\/v2-5cb60be6a855dad326a3cc0ca189fcbc_r.jpg\"\/><\/noscript><img decoding=\"async\" class=\"origin_image zh-lightbox-thumb lazy\" src=\"https:\/\/pic4.zhimg.com\/80\/v2-5cb60be6a855dad326a3cc0ca189fcbc_hd.jpg\" width=\"879\" data-rawwidth=\"879\" data-rawheight=\"624\" data-size=\"normal\" data-caption=\"\" data-default-watermark-src=\"https:\/\/pic3.zhimg.com\/50\/v2-5c42a173c152bee29b425b7ccbb8012e_hd.jpg\" data-original=\"https:\/\/pic4.zhimg.com\/v2-5cb60be6a855dad326a3cc0ca189fcbc_r.jpg\" data-actualsrc=\"https:\/\/pic4.zhimg.com\/50\/v2-5cb60be6a855dad326a3cc0ca189fcbc_hd.jpg\" \/><\/figure>\n<p>\u7b97\u6cd5\u590d\u6742\u5ea6\u5404\u79cd\u5404\u6837\u7684\u90fd\u6709\uff0c\u6709\u65f6\u5206\u6790\u8d77\u6765\u6bd4\u8f83\u5927\u4e0b\u4f1a\u7279\u522b\u56f0\u96be\uff0c\u4e0d\u8fc7\u4e0b\u9762\u4e24\u4ef6\u4e8b\u662f\u80af\u5b9a\u7684\uff0c\u800c\u4e14\u975e\u5e38\u91cd\u8981\uff1a<\/p>\n<p><b>\u5bf9\u6570\u65f6\u95f4\u590d\u6742\u5ea6<\/b>\u6bd4<b>\u591a\u9879\u5f0f\u65f6\u95f4\u590d\u6742\u5ea6<\/b>\u5feb\u5f97\u591a\u3002<\/p>\n<p><b>\u591a\u9879\u5f0f\u65f6\u95f4\u590d\u6742\u5ea6<\/b>\u6bd4<b>\u6307\u6570\u65f6\u95f4\u590d\u6742\u5ea6<\/b>\u5feb\u5f97\u591a\u3002<\/p>\n<figure data-size=\"normal\"><noscript><img decoding=\"async\" src=\"https:\/\/pic2.zhimg.com\/50\/v2-ac85d6f784937895393518de4116d729_hd.jpg\" data-rawwidth=\"530\" data-rawheight=\"251\" data-size=\"normal\" data-caption=\"\" data-default-watermark-src=\"https:\/\/pic4.zhimg.com\/50\/v2-572048bd04e914f6fca6fde49d454bda_hd.jpg\" class=\"origin_image zh-lightbox-thumb\" width=\"530\" data-original=\"https:\/\/pic2.zhimg.com\/v2-ac85d6f784937895393518de4116d729_r.jpg\"\/><\/noscript><img decoding=\"async\" class=\"origin_image zh-lightbox-thumb lazy\" src=\"https:\/\/pic2.zhimg.com\/80\/v2-ac85d6f784937895393518de4116d729_hd.jpg\" width=\"530\" data-rawwidth=\"530\" data-rawheight=\"251\" data-size=\"normal\" data-caption=\"\" data-default-watermark-src=\"https:\/\/pic4.zhimg.com\/50\/v2-572048bd04e914f6fca6fde49d454bda_hd.jpg\" data-original=\"https:\/\/pic2.zhimg.com\/v2-ac85d6f784937895393518de4116d729_r.jpg\" data-actualsrc=\"https:\/\/pic2.zhimg.com\/50\/v2-ac85d6f784937895393518de4116d729_hd.jpg\" \/><\/figure>\n<p>\u4e8b\u5b9e\u4e0a\uff0c\u5728\u5bc6\u7801\u5b66\u4e2d\uff0c\u5f88\u591a\u65f6\u5019<b>\u5bc6\u7801\u4e0d\u662f\u4e0d\u53ef\u4ee5\u7834\u89e3\u7684\uff0c\u53ea\u4e0d\u8fc7\u7834\u89e3\u5bc6\u7801\u9700\u8981\u5927\u91cf\u7684\u65f6\u95f4<\/b>\u3002<\/p>\n<p>\u6bd4\u5982RSA\u6700\u5173\u952e\u7684\u4e00\u6b65\uff0c\u662fBob\u751f\u6210\u4e24\u4e2a\u8d28\u6570p1\u548cp2\uff0c\u7136\u540e\u8ba1\u7b97\u5b83\u4eec\u7684\u79efn\uff0c\u7528<b>\u4e58\u6cd5n=p1*p2<\/b>\uff0c\u968f\u540e\u544a\u8bc9Alice\u8fd9\u4e2an\u7684\u503c\u3002\u7136\u800c\u5982\u679cEve\u60f3\u8981\u7834\u89e3\u5bc6\u7801\uff0c\u4ed6\u5fc5\u987b\u5728\u5df2\u77e5n\u7684\u60c5\u51b5\u4e0b\u6c42\u51fap1\u548cp2\uff0c\u4ed6\u9700\u8981<b>\u5c06n\u56e0\u6570\u5206\u89e3\u5206\u89e3\u4e3an=p1*p2<\/b>\u3002<\/p>\n<p>\u5982\u679c\u5bf9\u4e8e\u8f93\u5165\u89c4\u6a21\u6765\u8bf4\uff0c\u4e58\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662f<b>\u591a\u9879\u5f0f\u7ea7<\/b>\u7684\uff0c\u800c\u5206\u89e3\u8d28\u56e0\u6570\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662f<b>\u6307\u6570\u7ea7<\/b>\u7684\u3002<\/p>\n<p>\u6240\u4ee5\uff0c<b>\u5206\u89e3\u8d28\u56e0\u6570\u8981\u6bd4\u4e58\u6cd5\u6162\u5f97\u591a<\/b>\u3002\u6240\u4ee5\u53ea\u8981Bob\u751f\u6210\u7684p1\u548cp2\u8db3\u591f\u5927\uff0c\u7b49\u5230Eve\u5206\u89e3\u5b8cn\u7684\u65f6\u5019\uff0c\u5730\u7403\u6050\u6015\u5df2\u7ecf\u90fd\u4e0d\u5b58\u5728\u4e86\u3002<\/p>\n<p>\u5bc6\u7801\u672c\u8d28\u4e0a\u5c31\u662f\u62c9\u5f00\u4e86\u65f6\u95f4\u590d\u6742\u5ea6\u7684\u5dee\u8ddd\uff0c\u4f7f\u5f97<b>\u7834\u89e3\u5bc6\u7801\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u9ad8\u4e8e\u52a0\u5bc6\u7684\u65f6\u95f4\u590d\u6742\u5ea6<\/b>\uff0c\u4ee5\u8fbe\u6210\u4fdd\u5bc6\u7684\u76ee\u7684\u3002<\/p>\n<p>2\u3001RSA\u7528\u5230\u7684\u51e0\u4e2a\u7b97\u6cd5\u4ee5\u53ca\u5b83\u4eec\u7684\u590d\u6742\u5ea6\uff08\u8fd9\u91cc\u5c31\u4e0d\u89e3\u91ca\u8fd9\u51e0\u4e2a\u7b97\u6cd5\u7684\u5b9e\u73b0\u6b65\u9aa4\u4e86\u2026\u2026\uff09<\/p>\n<p>a. <b>\u4e58\u6cd5<\/b><\/p>\n<p>\u4f5c\u7528\uff1a\u8ba1\u7b97\u4e24\u4e2a\u6570\u7684\u79ef\u3002<\/p>\n<p>\u65f6\u95f4\u590d\u6742\u5ea6\uff1a<b>\u591a\u9879\u5f0f\u7ea7<\/b>\uff08\u76f8\u5bf9\u4e8e\u8f93\u5165\u89c4\u6a21\uff09<\/p>\n<p>b. <b>\u968f\u673a\u6570\u751f\u6210\u7b97\u6cd5<\/b><\/p>\n<p>\u4f5c\u7528\uff1a\u751f\u6210\u968f\u673a\u6570\uff08\u5176\u5b9e\u662f\u4f2a\u968f\u673a\u6570\uff09<\/p>\n<p>\u65f6\u95f4\u590d\u6742\u5ea6\uff1a<b>\u591a\u9879\u5f0f\u7ea7<\/b>\uff08\u76f8\u5bf9\u4e8e\u8f93\u51fa\u89c4\u6a21\uff09<\/p>\n<p>c. <b>Miller-Rabin\u6d4b\u8bd5<\/b><\/p>\n<p>\u4f5c\u7528\uff1a\u6d4b\u8bd5\u4e00\u4e2a\u6570\u662f\u5426\u662f\u8d28\u6570\u3002\uff08<b>\u6709\u6982\u7387\u8bef\u5224\uff0c\u4f2a\u7d20\u6570\u53ef\u80fd\u8499\u6df7\u8fc7\u5173\u3002\u5355\u6b21\u6d4b\u8bd5\u7684\u53ef\u4fe1\u5ea6\u8fd8\u4e0d\u662f\u975e\u5e38\u9ad8\u3002\u9700\u8981\u7528\u4e0d\u540c\u7684\u53c2\u6570\u8fdb\u884c\u591a\u6b21\u72ec\u7acb\u6d4b\u8bd5\uff0c\u8ba9\u8bef\u6982\u7387\u5c0f\u5230\u53ef\u4ee5\u5ffd\u7565\u4e0d\u8ba1\u3002<\/b>\uff09<\/p>\n<p>\u65f6\u95f4\u590d\u6742\u5ea6\uff1a<b>\u591a\u9879\u5f0f\u7ea7<\/b>\uff08\u76f8\u5bf9\u4e8e\u8f93\u5165\u89c4\u6a21\uff09<\/p>\n<p>d. <b>\u5feb\u901f\u5e42<\/b><\/p>\n<p>\u4f5c\u7528\uff1a\u5feb\u901f\u8ba1\u7b97 <img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=a%5Ex\" alt=\"[\u516c\u5f0f]\" data-formula=\"a^x\" \/> mod n\u7684\u503c<\/p>\n<p>\u65f6\u95f4\u590d\u6742\u5ea6\uff1a<b>\u591a\u9879\u5f0f\u7ea7<\/b>\uff08\u76f8\u5bf9\u4e8e\u8f93\u5165\u89c4\u6a21\uff09<\/p>\n<p>e. <b>\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5<\/b><\/p>\n<p>\u4f5c\u7528\uff1a\u5feb\u901f\u6c42\u51faax+by=1\u7684\u4e00\u7ec4\u89e3\u3002\uff08a\u548cb\u662f\u5e38\u6570\u4e14\u4e92\u8d28\u3002\u89e3\u4e0d\u552f\u4e00\uff0c\u8fd9\u91cc\u53ea\u662f\u7b97\u51fa\u6765\u4e00\u7ec4\u3002\uff09<\/p>\n<p>\u65f6\u95f4\u590d\u6742\u5ea6\uff1a<b>\u591a\u9879\u5f0f\u7ea7<\/b>\uff08\u76f8\u5bf9\u4e8e\u8f93\u5165\u89c4\u6a21\uff09<\/p>\n<p>3\u3001\u7834\u89e3RSA\u65e0\u6cd5\u7ed5\u5f00\u7684\u4e00\u4e2a\u6b65\u9aa4<\/p>\n<p><b>\u5206\u89e3\u8d28\u56e0\u6570<\/b><\/p>\n<p>\u65f6\u95f4\u590d\u6742\u5ea6\uff1a<b>\u6307\u6570\u7ea7<\/b>\uff08\u76f8\u5bf9\u4e8e\u8f93\u5165\u89c4\u6a21\uff09<\/p>\n<p>\u8fd9\u5c31\u662f\u4e3a\u4ec0\u4e48RSA\u7406\u8bba\u4e0a\u975e\u5e38\u5b89\u5168\uff0c\u56e0\u4e3a\u7834\u89e3RSA\u6240\u8981\u4ed8\u51fa\u5730\u8ba1\u7b97\u6210\u672c\u8fdc\u8fdc\u9ad8\u4e8e\u4f7f\u7528RSA\u8fdb\u884c\u52a0\u5bc6\u7684\u8ba1\u7b97\u6210\u672c\u3002<\/p>\n<p>\u81f3\u4e8e\u5982\u4f55\u5229\u7528Miller-Rabin\u6d4b\u8bd5\u3001\u5feb\u901f\u5e42\u3001\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b49\u7b97\u6cd5\u8fdb\u884cRSA\uff0c\u6211\u4eec\u9700\u8981\u5148\u518d\u4ecb\u7ecd\u4e00\u4e9b\u6570\u8bba\u3002<\/p>\n<h2>\u4e09\u3001\u6570\u8bba\u7bc7<\/h2>\n<p>_( \uff9f\u0414\uff9f)\uff89\u5148\u819c\u62dc\u4e00\u4f4d\u5de8\u795e\u3002<\/p>\n<figure data-size=\"normal\"><noscript><img decoding=\"async\" src=\"https:\/\/pic1.zhimg.com\/50\/v2-a8e22b33ac7de207306b009fa57daaa0_hd.jpg\" data-rawwidth=\"388\" data-rawheight=\"310\" data-size=\"normal\" data-default-watermark-src=\"https:\/\/pic2.zhimg.com\/50\/v2-119221cc380e0f47ccd4386ae21308f9_hd.jpg\" class=\"content_image\" width=\"388\"\/><\/noscript><img decoding=\"async\" class=\"content_image lazy\" src=\"https:\/\/pic1.zhimg.com\/80\/v2-a8e22b33ac7de207306b009fa57daaa0_hd.jpg\" width=\"388\" data-rawwidth=\"388\" data-rawheight=\"310\" data-size=\"normal\" data-default-watermark-src=\"https:\/\/pic2.zhimg.com\/50\/v2-119221cc380e0f47ccd4386ae21308f9_hd.jpg\" data-actualsrc=\"https:\/\/pic1.zhimg.com\/50\/v2-a8e22b33ac7de207306b009fa57daaa0_hd.jpg\" \/><figcaption>\u83b1\u6602\u54c8\u5fb7\u00b7\u6b27\u62c9<\/figcaption><\/figure>\n<p>1\u3001\u6b27\u62c9\u51fd\u6570\u2014\u2014\u03c6()<\/p>\n<p><b>\u03c6(n)\u8868\u793a\uff1a\u5c0f\u4e8en\u7684\u6b63\u6574\u6570\u4e2d\u4e0en\u4e92\u8d28\u7684\u6570\u7684\u6570\u76ee\u3002<\/b>\uff08\u4e92\u8d28\u8868\u793a\u516c\u56e0\u6570\u4e3a1\uff09<\/p>\n<p>\u6bd4\u5982\u60f3\u8981\u77e5\u9053\u03c6(10)\u7684\u8bdd\uff0c\u6211\u4eec\u5c31\u53ef\u4ee5\u770b[1, 10)\u4e2d\u548c10\u4e92\u8d28\u7684\u6574\u6570\uff0c\u4e5f\u5c31\u662f1\u30013\u30017\u30019\u8fd9\u56db\u4e2a\u6570\u3002\uff082\u30014\u30016\u30018\u548c10\u6709\u516c\u56e0\u65702\uff0c\u800c5\u548c10\u6709\u516c\u56e0\u657010\uff09\u3002\u6240\u4ee5\u03c6(10)=4\u3002<\/p>\n<p>\u6bd4\u5982\u60f3\u8981\u77e5\u9053\u03c6(21)\u7684\u8bdd\uff0c\u6211\u4eec\u5c31\u53ef\u4ee5\u770b[1, 21)\u4e2d\u548c21\u4e92\u8d28\u7684\u6574\u6570\uff0c\u4e5f\u5c31\u662f1\u30012\u30014\u30015\u30018\u300110\u300111\u300113\u300116\u300117\u300119\u300120\u8fd912\u4e2a\u6570\u3002\uff083\u30016\u30019\u300112\u300115\u300118\u548c21\u6709\u516c\u56e0\u65703\uff0c\u800c7\u300114\u548c21\u6709\u516c\u56e0\u65707\uff09\u3002\u6240\u4ee5\u03c6(21)=12\u3002<\/p>\n<p>\u6211\u4eec\u60ca\u559c\u5730\u53d1\u73b0\u2570(*\u00b0\u203f\u00b0*)\u256f\uff1a<\/p>\n<p><b>\u5982\u679cn\u80fd\u5199\u4f5c\u4e24\u4e2a\u4e0d\u540c\u8d28\u6570 <\/b><img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=p_1\" alt=\"[\u516c\u5f0f]\" data-formula=\"p_1\" \/><b> \u4e0e <\/b><img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=p_2\" alt=\"[\u516c\u5f0f]\" data-formula=\"p_2\" \/><b> \u7684\u4e58\u79ef<\/b>\uff0c\u90a3\u4e48<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=++%CF%86%28n%29%3D%28p_1-1%29%28p_2-1%29\" alt=\"[\u516c\u5f0f]\" data-formula=\"  \u03c6(n)=(p_1-1)(p_2-1)\" \/><\/p>\n<p>(\u8fd9\u4e2a\u5927\u5bb6\u81ea\u5df1\u8bc1\u660e\u5427(\uffe3\u25bd\uffe3))<\/p>\n<p>\u6bd4\u598210=2*5\uff0c2\u548c5\u662f\u4e24\u4e2a\u8d28\u6570\uff0c\u6240\u4ee5\u03c6(10)=(2-1)*(5-1)=4\u3002<\/p>\n<p>\u6bd4\u598221=3*7\uff0c3\u548c7\u662f\u4e24\u4e2a\u8d28\u6570\uff0c\u6240\u4ee5\u03c6(21)=(3-1)*(7-1)=12\u3002<\/p>\n<p>2\u3001\u540c\u4f59\u5f0f<\/p>\n<p>\u76f8\u4fe1\u5404\u4f4d\u540c\u5b66\u90fd\u77e5\u9053\u4f59\u6570\u662f\u4ec0\u4e48\u3002<\/p>\n<p>\u6bd4\u5982\u8bf4\uff0c23\u00f77=3\u2026\u20262<\/p>\n<p>\u518d\u6bd4\u5982\uff0c65\u00f77=9\u2026\u20262<\/p>\n<p>\u6211\u4eec\u53d1\u73b0\uff0c\u8fd9\u4e24\u4e2a\u6570\u9664\u4ee57\u90fd\u4f592\uff0c\u4e8e\u662f\u6211\u4eec\u5c31\u53ef\u4ee5\u8fd9\u6837\u5199\uff1a<\/p>\n<p>23 <b>\u2261 <\/b>65\uff08mod 7\uff09<\/p>\n<p>\u5f53\u7136\u4e5f\u53ef\u4ee5\u8fd9\u6837\uff1a<\/p>\n<p>23 <b>\u2261 <\/b>2\uff08mod 7\uff09<\/p>\n<p>65 <b>\u2261 <\/b>2\uff08mod 7\uff09<\/p>\n<p>\u51c6\u786e\u5730\u8bf4\uff0c\u5982\u679ca=b+km\u7684\u8bdd\uff0ca <b>\u2261 <\/b>b\uff08mod m\uff09<\/p>\n<p>\u540c\u4f59\u5f0f\u6709\u8fd9\u6837\u4e24\u4e2a\u6027\u8d28\uff1a<\/p>\n<p>\u540c\u4f59\u5f0f\u53ef\u4ee5\u4e92\u76f8\u52a0\uff1a\u82e5a <b>\u2261 <\/b>b\uff08mod m\uff09\u3001c <b>\u2261 <\/b>d\uff08mod m\uff09\uff0c\u5219a+c <b>\u2261 <\/b>b+d\uff08mod m\uff09<\/p>\n<p>\u540c\u4f59\u5f0f\u53ef\u4ee5\u4e92\u76f8\u4e58\uff1a\u82e5a <b>\u2261 <\/b>b\uff08mod m\uff09\u3001c <b>\u2261 <\/b>d\uff08mod m\uff09\uff0c\u5219a*c <b>\u2261 <\/b>b*d\uff08mod m\uff09<\/p>\n<p>\u4e3e\u4e2a\u4f8b\u5b50\uff0c\u65e2\u7136\u6211\u4eec\u77e5\u905323\u00d7(23<b>+<\/b>65)\u2261 2\u00d7(2+2) \u2261 8 \u2261 1\uff08mod 7\uff09<\/p>\n<p>\u56e0\u4e3a23\u00d7(23<b>+<\/b>65) =2024\uff0c\u4e5f\u5c31\u662f\u8bf42024\u00f77\u4f59\u6570\u662f1\u3002\uff08\u4e0d\u4fe1\u81ea\u5df1\u52a8\u624b\u7b97\u7b97\u770b(^\u25bd^ )\uff09<\/p>\n<p>3\u3001\u6b27\u62c9\u516c\u5f0f<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=%E8%8B%A5a%E4%B8%8En%E4%BA%92%E8%B4%A8%EF%BC%8C%E5%88%99a%5E%7B%CF%86%28n%29%7D%E2%89%A11+\" alt=\"[\u516c\u5f0f]\" data-formula=\"\u82e5a\u4e0en\u4e92\u8d28\uff0c\u5219a^{\u03c6(n)}\u22611 \" \/> (mod n)<\/p>\n<p>(\u81ea\u5b66\u4e86\u62c9\u683c\u6717\u65e5\u5b9a\u7406\u7684\u9ad8\u4e2d\u751f\u8bf7\u81ea\u5df1\u8bc1\u660e^_~)<\/p>\n<p>4\u3001\u4e58\u6cd5\u9006\u5143<\/p>\n<p>\u5982\u679cab <b>\u2261 <\/b>1\uff08mod m\uff09\uff0c\u5219\u79f0a\u548cb\u4e3a\u5173\u4e8em\u4e92\u4e3a\u4e58\u6cd5\u9006\u5143\u3002<\/p>\n<p>\u5df2\u77e5a\u6c42b\u7684\u65b9\u6cd5\uff1a<\/p>\n<p>\u56e0\u4e3aab <b>\u2261 <\/b>1\uff08mod m\uff09\uff0c\u6240\u4ee5\u4e0d\u59a8\u8bbeab+mk=1\uff0c\u5176\u4e2da\u548cm\u4e3a\u5df2\u77e5\u6570\u3002<\/p>\n<p>\u53ef\u4ee5\u5229\u7528<b>\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5<\/b>\uff0c\u53ef\u4ee5\u5728\u591a\u9879\u5f0f\u65f6\u95f4\u5185\uff0c\u8ba1\u7b97\u51fa\u6765\u4e00\u4e2a\u4e58\u6cd5\u9006\u5143b\u3002<\/p>\n<p>(\u4e8b\u5b9e\u4e0a\uff0cb\u7684\u89e3\u4e0d\u552f\u4e00\uff0c\u8fd9\u91cc\u53ea\u662f\u6c42\u51fa\u4e86\u4e00\u4e2ab\u3002)<\/p>\n<h2><b>\u56db\u3001\u4e24\u628a\u94a5\u5319<\/b><\/h2>\n<p>\u6211\u4eec\u7ec8\u4e8e\u5f00\u59cb\u6784\u9020\u54b1\u4eec\u9700\u8981\u7684\u4e24\u628a\u94a5\u5319\u4e86\u3002\u30fe(\u2267\u25bd\u2266*)o<\/p>\n<p>\u7b2c\u4e00\u628a\uff1a\u516c\u94a5\uff0c\u7528\u4e8e\u52a0\u5bc6\uff0c\u9001\u7ed9Alice\u3002<\/p>\n<p>\u7b2c\u4e8c\u628a\uff1a\u5bc6\u94a5\uff0c\u7528\u4e8e\u89e3\u5bc6\uff0cBob\u81ea\u5df1\u7559\u597d\u3002<\/p>\n<p>1\u3001Bob\u968f\u673a\u751f\u6210\u4e86\u4e00\u4e9b\u975e\u5e38\u975e\u5e38\u5927\u7684\u6574\u6570\uff0c\u5e76\u7528Miller-Rabin\u7b97\u6cd5\u68c0\u6d4b\u5b83\u4eec\u662f\u4e0d\u662f\u8d28\u6570\uff0c\u76f4\u5230\u627e\u5230\u4e24\u4e2a\u5927\u8d28\u6570\u2014\u2014<img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=p_1\" alt=\"[\u516c\u5f0f]\" data-formula=\"p_1\" \/> \u548c <img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=p_2\" alt=\"[\u516c\u5f0f]\" data-formula=\"p_2\" \/> \u3002\uff08\u968f\u673a\u6570\u751f\u6210\uff1a\u591a\u9879\u5f0f\u65f6\u95f4\uff1bMiller-Rabin: \u591a\u9879\u5f0f\u65f6\u95f4\uff09<\/p>\n<p>2\u3001Bob\u8ba1\u7b97\u4e24\u4e2a\u8d28\u6570\u7684\u4e58\u79ef <img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=n%3Dp_1p_2\" alt=\"[\u516c\u5f0f]\" data-formula=\"n=p_1p_2\" \/> \uff08\u4e58\u6cd5: \u591a\u9879\u5f0f\u65f6\u95f4\uff09<\/p>\n<p>3\u3001Bob\u8ba1\u7b97 <img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=%CF%86%28n%29%3D%28p_1-1%29%28p_2-1%29\" alt=\"[\u516c\u5f0f]\" data-formula=\"\u03c6(n)=(p_1-1)(p_2-1)\" \/> \uff08\u4e58\u6cd5: \u591a\u9879\u5f0f\u65f6\u95f4\uff09<\/p>\n<p><b>\u8bf7\u6ce8\u610f\uff01\u56e0\u4e3an\u592a\u5927\u4e86\uff0c\u800c\u5206\u89e3\u8d28\u56e0\u6570\u9700\u8981\u6307\u6570\u65f6\u95f4\uff0c\u6240\u4ee5\u6ca1\u6709\u4eba\u80fd\u591f\u5c06n\u8d28\u56e0\u6570\u5206\u89e3\u3002<\/b><\/p>\n<p><b>\u56e0\u6b64\uff0c\u4efb\u4f55\u4eba\u90fd\u65e0\u6cd5\u5229\u7528n\u63a8\u51fa\u03c6(n)\u3002\uff08\u7406\u8bba\u4e0a\u5728\u592a\u9633\u7206\u70b8\u4e4b\u524d\u53ef\u80fd\u6027\u6781\u5c0f\uff09<\/b><\/p>\n<p><b>\u03c6(n)\u7684\u503c\u53ea\u6709Bob\u81ea\u5df1\u77e5\u9053\u3002<\/b><\/p>\n<p>4\u3001Bob\u6784\u9020\u4e86\u4e00\u4e2a\u6bd41\u5927\u3001\u6bd4\u03c6(n)\u5c0f\u3001\u4e0d\u7b49\u4e8e <img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=p_1\" alt=\"[\u516c\u5f0f]\" data-formula=\"p_1\" \/> \u6216 <img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=p_2\" alt=\"[\u516c\u5f0f]\" data-formula=\"p_2\" \/> \u7684\u6574\u6570e\u3002\uff08\u968f\u673a\u6570\uff1a\u591a\u9879\u5f0f\u65f6\u95f4\uff09<\/p>\n<p>5\u3001Bob\u6c42\u51fa\u4e86e\u5bf9\u4e8e\u03c6(n)\u7684\u4e58\u6cd5\u9006\u5143d\uff0c\u4e5f\u5c31\u662f\u8bf4<b>ed \u2261 1\uff08mod \u03c6(n)\uff09<\/b>\uff0c\u4e5f\u5c31\u662f\u8bf4ed=k\u03c6(n)+1 (\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\uff0c\u591a\u9879\u5f0f\u65f6\u95f4)<\/p>\n<p><b>\u8bf7\u6ce8\u610f\uff01\u73b0\u5728\u795e\u5947\u7684\u4e8b\u60c5\u53d1\u751f\u4e86\uff01\u5bf9\u4e8e\u4e00\u4e2a\u4e0en\u4e92\u8d28\u7684\u6570a\uff1a<\/b><\/p>\n<p>\u56e0\u4e3a <img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=a%5E%7B%CF%86%28n%29%7D%E2%89%A11+\" alt=\"[\u516c\u5f0f]\" data-formula=\"a^{\u03c6(n)}\u22611 \" \/> (mod n)<\/p>\n<p>\u6240\u4ee5 <img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=a%5E%7Bk%CF%86%28n%29%7D%E2%89%A11\" alt=\"[\u516c\u5f0f]\" data-formula=\"a^{k\u03c6(n)}\u22611\" \/> (mod n)<\/p>\n<p>\u6240\u4ee5 <img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=a%5E%7Bk%CF%86%28n%29%2B1%7D%E2%89%A1a\" alt=\"[\u516c\u5f0f]\" data-formula=\"a^{k\u03c6(n)+1}\u2261a\" \/> (mod n)<\/p>\n<p>\u6240\u4ee5 <img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=a%5E%7Bed%7D%E2%89%A1a\" alt=\"[\u516c\u5f0f]\" data-formula=\"a^{ed}\u2261a\" \/> (mod n)<\/p>\n<p>\u6240\u4ee5\uff0c\u82e5 <img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=c%5Cequiv+a%5Ee\" alt=\"[\u516c\u5f0f]\" data-formula=\"c\\equiv a^e\" \/> (mod n), \u5219<img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=c%5Ed%5Cequiv+a%5E%7Bed%7D+%5Cequiv+a\" alt=\"[\u516c\u5f0f]\" data-formula=\"c^d\\equiv a^{ed} \\equiv a\" \/>\uff08mod n\uff09<\/p>\n<p><b>\u5230\u8fd9\u91cc\uff0c\u4e24\u628a\u94a5\u5319\u6784\u9020\u5b8c\u6210\uff01\u311f(\u2267\u25c7\u2266)\u310f<\/b><\/p>\n<p><b>\u516c\u94a5\uff1a\uff08n, e\uff09<\/b><\/p>\n<p><b>\u5bc6\u94a5\uff1a\uff08n, d\uff09<\/b><\/p>\n<p>\u4e8e\u662f\uff0c\u5bf9\u4e8e\u660e\u6587a\uff0cAlice\u5229\u7528\u516c\u94a5\uff08n, e\uff09\u5c31\u53ef\u4ee5\u52a0\u5bc6\u4e3a\u5bc6\u6587c\u4e86\u3002<\/p>\n<p>\u5979\u53ea\u7528\u8ba1\u7b97<img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=c%5Cequiv+a%5Ee\" alt=\"[\u516c\u5f0f]\" data-formula=\"c\\equiv a^e\" \/> (mod n) (\u5feb\u901f\u5e42\u7b97\u6cd5\uff0c\u591a\u9879\u5f0f\u65f6\u95f4)<\/p>\n<p>\u800cBob\u5229\u7528\u53ea\u6709\u81ea\u5df1\u77e5\u9053\u7684\u5bc6\u94a5\uff08n, d\uff09\uff0c\u53ef\u4ee5\u8ba1\u7b97<img decoding=\"async\" src=\"https:\/\/www.zhihu.com\/equation?tex=a%5Cequiv++c%5Ed\" alt=\"[\u516c\u5f0f]\" data-formula=\"a\\equiv  c^d\" \/>\uff08mod n\uff09<\/p>\n<p><b>\u9664\u4e86Bob\uff0c\u6ca1\u6709\u4efb\u4f55\u4eba\u53ef\u4ee5\u77e5\u9053\u03c6(n)\uff0c\u6240\u4ee5\u6ca1\u6709\u4eba\u53ef\u4ee5\u6c42\u51fae\u5173\u4e8e\u03c6(n)\u7684\u4e58\u6cd5\u9006\u5143d\u3002\u4e5f\u5c31\u662f\u8bf4d\u7684\u503c\u4ece\u5934\u5230\u5c3e\u53ea\u6709Bob\u81ea\u5df1\u77e5\u9053\uff0c\u4e0d\u53ef\u80fd\u6cc4\u9732\u3002<\/b><\/p>\n<p>\u73b0\u5728\uff0cBob\u9700\u8981\u505a\u7684\uff0c\u4ec5\u4ec5\u662f\u628a\u516c\u94a5(n, e)\u4ea4\u7ed9Alice\uff0c\u8ba9Alice\u628a\u5bc6\u6587a\u52a0\u5bc6\u6210c\uff0c\u5f97\u5230\u5bc6\u6587c\u540e\u518d\u7528\u81ea\u5df1\u7684\u5bc6\u94a5\u89e3\u5bc6\u3002<\/p>\n<p>Eve\u5c31\u4e0d\u53ef\u80fd\u7a83\u542c\u4e86\u3002&lt;(\uffe3\u02c7\uffe3)\/<\/p>\n<figure data-size=\"normal\"><noscript><img decoding=\"async\" src=\"https:\/\/pic2.zhimg.com\/50\/v2-b82f53af1604de023afd04c3d3d0ae98_hd.jpg\" data-rawwidth=\"960\" data-rawheight=\"540\" data-size=\"normal\" data-caption=\"\" data-default-watermark-src=\"https:\/\/pic3.zhimg.com\/50\/v2-0eacf663407fff31c613628384423848_hd.jpg\" class=\"origin_image zh-lightbox-thumb\" width=\"960\" data-original=\"https:\/\/pic2.zhimg.com\/v2-b82f53af1604de023afd04c3d3d0ae98_r.jpg\"\/><\/noscript><img decoding=\"async\" class=\"origin_image zh-lightbox-thumb lazy\" src=\"https:\/\/pic2.zhimg.com\/80\/v2-b82f53af1604de023afd04c3d3d0ae98_hd.jpg\" width=\"960\" data-rawwidth=\"960\" data-rawheight=\"540\" data-size=\"normal\" data-caption=\"\" data-default-watermark-src=\"https:\/\/pic3.zhimg.com\/50\/v2-0eacf663407fff31c613628384423848_hd.jpg\" data-original=\"https:\/\/pic2.zhimg.com\/v2-b82f53af1604de023afd04c3d3d0ae98_r.jpg\" data-actualsrc=\"https:\/\/pic2.zhimg.com\/50\/v2-b82f53af1604de023afd04c3d3d0ae98_hd.jpg\" \/><\/figure>\n<hr \/>\n<p>\u5927\u529f\u544a\u6210\u4e86\uff01(\/\u2267\u25bd\u2266)\/<\/p>\n<p>\u4e0d\u8fc7\u4e8b\u60c5\u8fd8\u6ca1\u6709\u7ed3\u675f\uff0c\u63a5\u4e0b\u6765\u8fd8\u6709\u5f88\u591a\u95ee\u9898\u3002<\/p>\n<p>\u6bd4\u65b9\u8bf4\u5728RSA\u4e2d\uff0c\u663e\u7136a\u4e0d\u80fd\u592a\u5927\uff0c\u56e0\u4e3an\u9700\u8981\u6bd4a\u8fd8\u8981\u5927\u7684\u3002\u800c\u4e14\u5982\u679ca\u592a\u5927\u7684\u8bdd\uff0cRSA\u901f\u5ea6\u6349\u6025\u3002<\/p>\n<p>\u6240\u4ee5\u5982\u679c\u52a0\u5bc6\u957f\u4fe1\u606f\u7684\u65f6\u5019\uff0c\u901a\u5e38\u662f\u7528RSA\u6765\u4f20\u9012\u79cd\u5b50\uff0c\u7136\u540e\u7528\u4f2a\u968f\u673a\u6570\u7b97\u6cd5\u5c55\u5f00\uff0c\u7136\u540e\u518d\u5229\u7528AES\u7b49\u5bf9\u79f0\u5bc6\u7801\u8fdb\u884c\u4e00\u6b21\u4e00\u5bc6\u7684\u52a0\u5bc6\u3002\u4e0d\u8fc7\u90a3\u5c31\u662f\u53e6\u5916\u4e00\u4e2a\u6545\u4e8b\u4e86\u2026\u2026<\/p>\n<p>\u800c\u4e14RSA\u53ea\u662f\u7406\u8bba\u4e0a\u4e0d\u53ef\u7834\u800c\u5df2\uff0c\u5b9e\u8df5\u4e2d\u56e0\u4e3a\u64cd\u4f5c\u4e0d\u5f53\uff0c\u53ef\u80fd\u4f1a\u6709\u5404\u79cd\u5404\u6837\u7684\u95ee\u9898\u3002\u6bd4\u5982\u5982\u679c\u4e24\u4e2a\u8d28\u6570p1\u548cp2\u5982\u679c\u592a\u8fc7\u63a5\u8fd1\u7684\u8bdd\uff0c\u5206\u89e3\u8d28\u56e0\u6570\u4e5f\u662f\u5f88\u5bb9\u6613\u7684\u2026\u2026RSA\u5728\u5b9e\u9645\u5e94\u7528\u4e2d\u7684\u653b\u9632\u8fd8\u662f\u53ef\u4ee5\u7ee7\u7eed\u8ba8\u8bba\u7684\u3002( \uffe3 \uffe3)<\/p>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>\u539f\u6587\u5730\u5740 \u4e00\u3001\u5bf9\u79f0\u52a0\u5bc6\u4e0e\u975e\u5bf9\u79f0\u52a0\u5bc6 \u4ece\u524d<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"colormag_page_container_layout":"default_layout","colormag_page_sidebar_layout":"default_layout","footnotes":""},"categories":[],"tags":[119],"class_list":["post-3751","post","type-post","status-publish","format-standard","hentry","tag-03-"],"_links":{"self":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/3751","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/comments?post=3751"}],"version-history":[{"count":0,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/3751\/revisions"}],"wp:attachment":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/media?parent=3751"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/categories?post=3751"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/tags?post=3751"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}