{"id":484,"date":"2020-11-01T21:04:34","date_gmt":"2020-11-01T13:04:34","guid":{"rendered":"http:\/\/123.57.142.208\/?p=484"},"modified":"2020-11-01T21:04:34","modified_gmt":"2020-11-01T13:04:34","slug":"%e4%bf%a1%e5%ae%89%e5%ae%9e%e9%aa%8c1-fermat%e7%b4%a0%e6%80%a7%e6%a3%80%e6%b5%8b%e7%ae%97%e6%b3%95","status":"publish","type":"post","link":"http:\/\/43.142.23.155\/?p=484","title":{"rendered":"Fermat\u7d20\u6027\u68c0\u6d4b\u7b97\u6cd5"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">\u68c0\u6d4b\u662f\u5426\u4e3a\u7d20\u6570\uff0c\u8be5\u7b97\u6cd5\u4ee5\u5b89\u5168\u7cfb\u6570k\u4e3a\u53c2\u6570\u8ba1\u7b97\u662f\u5426\u4e3a\u7d20\u6570\u7684\u6982\u7387<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>from random import random \n\n#\u5229\u7528\u8f97\u8f6c\u76f8\u9664\u6cd5\u6c42\u6700\u5927\u516c\u56e0\u6570\ndef BFactor(a,b):\n    #\u82e5b &gt; a\uff0c\u5219\u4ea4\u6362\u4e24\u4e2a\u6570\u7684\u503c\n    if(b &gt; a):\n        t = a\n        a = b\n        b = t\n    r = b #\u521d\u59cb\u5316r\n    while(r != 0):\n        r = a%b #r\u4e3aa\/b\u7684\u4f59\u6570\n        a = b\n        b = r\n    return a #\u5f97\u5230\u6700\u540e\u7684a\u4e3a(a,b)\n            \n\nm = int(input(\"\u8f93\u5165\u68c0\u6d4b\u6574\u6570m\uff1a\"))\nK = int(input(\"\u8f93\u5165\u5b89\u5168\u7cfb\u6570k\uff1a\"))\nk = 0\nwhile(k &lt; K):\n    flag = False\n    while(not flag):\n        b = int(random()*(m-2)) #\u751f\u6210\u4e00\u4e2a&#91;2,m-2]\u4e4b\u95f4\u7684\u968f\u673a\u6574\u6570\n        if(b &gt;= 2 and b &lt;= m-2):\n            flag = 5\n    factor = BFactor(b,m)#\u8ba1\u7b97(b,m)\n    r = (b**(m-1)) % m #\u8ba1\u7b97b^(m-1)modm\n    print(\"k = \" + str(k+1) + \"\u65f6,\u53d6b = \" + str(b),end = \",\")\n    print(\"g = (\" + str(b) + \",\"+ str(m) + \") = \" + str(factor),end = ',')\n    print(\"r = \" + str(b) + \"^\" + str(m-1) + \"(mod \" + str(m) + \") = \" + str(r),end = ',')\n    if(factor &gt; 1): \n        print(\"m = \" + str(m) + \"\u4e3a\u5408\u6570 \u6740\u6b7b\u6bd4\u8d5b\")\n        break\n    elif(r != 1):\n        print(\"m = \" + str(m) + \"\u4e3a\u5408\u6570 \u6740\u6b7b\u6bd4\u8d5b\")\n        break\n    else:        \n        print(\"m = \" + str(m) + \"\u53ef\u80fd\u4e3a\u7d20\u6570\")\n        k += 1\nif(k == K):\n    print(\"m = \" + str(m) + \"\u5f88\u53ef\u80fd\u4e3a\u7d20\u6570,\u4e14m\u4e3a\u7d20\u6570\u7684\u6982\u7387\u4e3a\"+str((1-1\/(2**k))*100)+\"%\")\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u68c0\u6d4b\u662f\u5426\u4e3a\u7d20\u6570\uff0c\u8be5\u7b97\u6cd5\u4ee5\u5b89\u5168\u7cfb\u6570k\u4e3a\u53c2\u6570\u8ba1\u7b97\u662f\u5426\u4e3a\u7d20\u6570\u7684\u6982\u7387<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10],"tags":[],"class_list":["post-484","post","type-post","status-publish","format-standard","hentry","category-10"],"_links":{"self":[{"href":"http:\/\/43.142.23.155\/index.php?rest_route=\/wp\/v2\/posts\/484","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/43.142.23.155\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/43.142.23.155\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/43.142.23.155\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/43.142.23.155\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=484"}],"version-history":[{"count":0,"href":"http:\/\/43.142.23.155\/index.php?rest_route=\/wp\/v2\/posts\/484\/revisions"}],"wp:attachment":[{"href":"http:\/\/43.142.23.155\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=484"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/43.142.23.155\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=484"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/43.142.23.155\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=484"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}