{"version":"https://jsonfeed.org/version/1.1","title":"苏迟但到的主页","home_page_url":"https://kexohproject.pages.dev","feed_url":"https://kexohproject.pages.dev/json/","description":"<p>你好，欢迎访问个人主页！</p><p>擅长密码学，安全分析，数字水印等技术。</p><p>你可以联系我通过:findmykexin@gmail.com或者知乎私信。</p><p>我的知乎链接：<a href=\"https://www.zhihu.com/people/su-chi-dan-dao\" rel=\"noopener noreferrer\" target=\"_blank\">苏迟但到 - 知乎 (zhihu.com)</a></p><p>我的github链接：<a href=\"https://github.com/kexinoh\" rel=\"noopener noreferrer\" target=\"_blank\">kexinoh</a></p>","icon":"https://kexohcdn.gptapi.cyou/kexohproject/production/images/channel-2e54d141ee195646ca12a9d16507a908.jpg","favicon":"https://kexohcdn.gptapi.cyou/kexohproject/production/images/favicon-340a2925d02a0386f3b954a032834917.jpg","authors":[{"name":"苏迟但到"}],"language":"zh-cn","items":[{"id":"gTvKKM7682r","title":"判断一个大数是否为素数有哪些算法？时间复杂度最低的是哪个？","content_html":"<p data-pid=\"EHzsF5uX\">判断素数算法有很多，但分类最主要有两类：<b>概率性算法（</b>Probabilistic PolynomialTime Algorithm<b>）</b>和<b>确定性算法</b>。</p><p data-pid=\"YvAR_I92\">概率性算法的缺陷就是在最坏情况下的耗时是无穷。</p><p data-pid=\"fvrLuG0v\">但是概率性算法的好处就是平均时间复杂度最低。</p><p data-pid=\"jnfysyWf\">概率性算法有：费马检测，米勒罗宾算法，Baillie–PSW</p><p data-pid=\"ysbR0H-q\">确定性算法有：试除法，改进后的试除法，ECPP，APR-CL（Adleman–Pomerance–Rumely-Cohen-Lenstra），以及AKS。</p><p data-pid=\"JQj9LLwl\">而AKS我想就是题主需要的答案了</p><blockquote data-pid=\"UjUqNHxT\">AKS最关键的重要性在于它是第一个被发表的<b>一般的</b>、<b>多项式的</b>、<b>确定性的</b>和<b>无仰赖的</b>素数判定算法。先前的算法至多达到了其中三点，但从未达到全部四个。AKS算法可以被用于检测任何<b>一般的</b>给定数字是否为素数。很多已知的高速判定算法只适用于满足特定条件的素数。例如，<a href=\"https://link.zhihu.com/?target=https%3A//baike.baidu.com/item/%25E5%258D%25A2%25E5%258D%25A1%25E6%2596%25AF-%25E8%258E%25B1%25E9%25BB%2598%25E6%25A3%2580%25E9%25AA%258C%25E6%25B3%2595%3FfromModule%3Dlemma_inlink\" class=\" wrap external\" target=\"_blank\" rel=\"nofollow noreferrer\">卢卡斯-莱默检验法</a>仅对<a href=\"https://link.zhihu.com/?target=https%3A//baike.baidu.com/item/%25E6%25A2%2585%25E6%25A3%25AE%25E7%25B4%25A0%25E6%2595%25B0/816141%3FfromModule%3Dlemma_inlink\" class=\" wrap external\" target=\"_blank\" rel=\"nofollow noreferrer\">梅森素数</a>适用，而Pépin测试仅对<span class=\"nolink\">费马数</span>适用。<br/>算法的最长运行时间可以被表为一个目标数字长度的<span class=\"nolink\">多项式</span>。ECPP和<span class=\"nolink\">APR</span>能够判断一个给定数字是否为素数，但无法对所有输入给出多项式时间范围。<br/>算法可以<a href=\"https://link.zhihu.com/?target=https%3A//baike.baidu.com/item/%25E7%25A1%25AE%25E5%25AE%259A%25E6%2580%25A7%3FfromModule%3Dlemma_inlink\" class=\" wrap external\" target=\"_blank\" rel=\"nofollow noreferrer\">确定性</a>地判断一个给定数字是否为素数。随机测试算法，例如<span class=\"nolink\">米勒-拉宾检验</span>和Baillie–PSW，可以在多项式时间内对给定数字进行校验，但只能给出概率性的结果。<br/>AKS算法并未“仰赖”任何未证明<a href=\"https://link.zhihu.com/?target=https%3A//baike.baidu.com/item/%25E7%258C%259C%25E6%2583%25B3%3FfromModule%3Dlemma_inlink\" class=\" wrap external\" target=\"_blank\" rel=\"nofollow noreferrer\">猜想</a>。一个反例是确定性米勒检验：该算法可以在多项式时间内对所有输入给出确定性结果，但其正确性却基于尚未被证明的<span class=\"nolink\">广义黎曼猜想</span>。【引用自百度百科】</blockquote><p data-pid=\"Tb21qarE\">AKS算法的时间复杂度是<img src=\"https://www.zhihu.com/equation?tex=O%28%5Clog%5E%7B12%7Dn%29\" alt=\"O(\\log^{12}n)\" eeimg=\"1\"/>，后来被改进到<img src=\"https://www.zhihu.com/equation?tex=O%28%5Clog%5E%7B6%7Dn%29\" alt=\"O(\\log^{6}n)\" eeimg=\"1\"/>。</p><p></p>","content_text":"判断素数算法有很多，但分类最主要有两类：概率性算法（Probabilistic PolynomialTime Algorithm）和确定性算法。\n\n概率性算法的缺陷就是在最坏情况下的耗时是无穷。\n\n但是概率性算法的好处就是平均时间复杂度最低。\n\n概率性算法有：费马检测，米勒罗宾算法，Baillie–PSW\n\n确定性算法有：试除法，改进后的试除法，ECPP，APR-CL（Adleman–Pomerance–Rumely-Cohen-Lenstra），以及AKS。\n\n而AKS我想就是题主需要的答案了\n\n> AKS最关键的重要性在于它是第一个被发表的一般的、多项式的、确定性的和无仰赖的素数判定算法。先前的算法至多达到了其中三点，但从未达到全部四个。AKS算法可以被用于检测任何一般的给定数字是否为素数。很多已知的高速判定算法只适用于满足特定条件的素数。例如，卢卡斯-莱默检验法仅对梅森素数适用，而Pépin测试仅对费马数适用。\n> 算法的最长运行时间可以被表为一个目标数字长度的多项式。ECPP和APR能够判断一个给定数字是否为素数，但无法对所有输入给出多项式时间范围。\n> 算法可以确定性地判断一个给定数字是否为素数。随机测试算法，例如米勒-拉宾检验和Baillie–PSW，可以在多项式时间内对给定数字进行校验，但只能给出概率性的结果。\n> AKS算法并未“仰赖”任何未证明猜想。一个反例是确定性米勒检验：该算法可以在多项式时间内对所有输入给出确定性结果，但其正确性却基于尚未被证明的广义黎曼猜想。【引用自百度百科】\n\nAKS算法的时间复杂度是O(\\log^{12}n)\n[https://www.zhihu.com/equation?tex=O%28%5Clog%5E%7B12%7Dn%29]，后来被改进到O(\\log^{6}n)\n[https://www.zhihu.com/equation?tex=O%28%5Clog%5E%7B6%7Dn%29]。\n\n","date_published":"2022-10-30T01:14:21.000Z","_microfeed":{"web_url":"https://kexohproject.pages.dev/i/判断一个大数是否为素数有哪些算法-时间复杂度最低的是哪个-gTvKKM7682r/","json_url":"https://kexohproject.pages.dev/i/gTvKKM7682r/json/","rss_url":"https://kexohproject.pages.dev/i/gTvKKM7682r/rss/","guid":"gTvKKM7682r","status":"published","itunes:title":"New Article Title for iTunes","date_published_short":"Sat Oct 29 2022","date_published_ms":1667092461000}}],"_microfeed":{"microfeed_version":"0.1.2","base_url":"https://kexohproject.pages.dev","categories":[{"name":"Education","categories":[{"name":"Language Learning"}]},{"name":"Technology"}],"subscribe_methods":[{"name":"RSS","type":"rss","url":"https://kexohproject.pages.dev/rss/","image":"https://kexohproject.pages.dev/assets/brands/subscribe/rss.png","enabled":true,"editable":false,"id":"4KlfbtkEfzy"},{"name":"JSON","type":"json","url":"https://kexohproject.pages.dev/json/","image":"https://kexohproject.pages.dev/assets/brands/subscribe/json.png","enabled":true,"editable":false,"id":"DVFm7TYiNSq"}],"description_text":"你好，欢迎访问个人主页！\n\n擅长密码学，安全分析，数字水印等技术。\n\n你可以联系我通过:findmykexin@gmail.com或者知乎私信。\n\n我的知乎链接：苏迟但到 - 知乎 (zhihu.com)\n\n我的github链接：kexinoh","copyright":"©2024","itunes:type":"episodic","items_sort_order":"newest_first"}}