{"id":347,"date":"2018-02-05T15:08:30","date_gmt":"2018-02-05T06:08:30","guid":{"rendered":"http:\/\/tamatoyaku.com\/b\/?p=347"},"modified":"2018-02-05T15:08:30","modified_gmt":"2018-02-05T06:08:30","slug":"347","status":"publish","type":"post","link":"https:\/\/p-0.me\/b\/p\/347\/","title":{"rendered":"C\u8a00\u8a9e\u3067\u6955\u5186\u66f2\u7dda\u306e\u52c9\u5f37(3.\u62e1\u5f35Euclid\u4e92\u9664\u6cd5)"},"content":{"rendered":"<p>\u6709\u9650\u4f53Fp\u4e0a\u3067\u306e\u9664\u7b97\u3092\u62e1\u5f35Euclid\u4e92\u9664\u6cd5\u3092\u7528\u3044\u3066\u9ad8\u901f\u5316\u3059\u308b\uff0e<br \/>\n&nbsp;<br \/>\n<!--more--><br \/>\n\u6709\u9650\u4f53Fp\u3067a\u00f7b\u3057\u305f\u3044<br \/>\n\u2193<br \/>\npx+by=1\u3068\u306a\u308bx,y\u304c\u6c42\u307e\u308b\uff0e(p,b\u306f\u4e92\u3044\u306b\u7d20\u306a\u306e\u3067\uff0c\u62e1\u5f35Euclid\u306e\u4e92\u9664\u6cd5\u3092\u9069\u7528\u53ef)<br \/>\n\u2193<br \/>\nby=1\u3068\u306a\u308b\uff0e(\u6709\u9650\u4f53Fp\u4e0a\u3067\u306f\uff0cpx\u306f0\u3068\u306a\u308b)<br \/>\n\u2193<br \/>\nb^-1=y\u3068\u306a\u308b\uff0e<br \/>\n\u2193<br \/>\na\u00f7b=a*(b^-1)=a*y\u3068\u306a\u308b\uff0e<br \/>\n\u2193<br \/>\n\u9664\u7b97\u304c\u4e57\u7b97\u306b\u306a\u3063\u3066\u3046\u308c\u3057\u3044\uff0e<br \/>\n&nbsp;<br \/>\n\u30bd\u30fc\u30b9\u30b3\u30fc\u30c9\u306f\u4ee5\u4e0b\u306e\u3088\u3046\u306b\u306a\u308b\uff0e<\/p>\n<pre class=\"lang:c decode:true \" title=\"div\">#include &lt;stdio.h&gt;\nvoid extgcd(int a,int b,int* x,int* y,int* d){\n\tint u,v,q,t;\n\t*x=1;\n\t*y=0;\n\tu=0;\n\tv=1;\n\twhile(b&gt;0){\n\t\tq=a\/b;\n\t\tt=u;u=*x-q*u;*x=t;\n\t\tt=v;v=*y-q*v;*y=t;\n\t\tt=b;b=a-q*b;a=t;\n\t}\n\t*d=a;\n}\nint main(){\n\tint a,b,p;\n\tint x,y,d;\n\tprintf(\"a:\");scanf(\"%d\",&amp;a);\n\tprintf(\"b:\");scanf(\"%d\",&amp;b);\n\tprintf(\"p:\");scanf(\"%d\",&amp;p);\n\textgcd(p,b,&amp;x,&amp;y,&amp;d);\n\tprintf(\"%d\/%d=%d\\n\",a,b,(a*y)%p);\n\treturn 0;\n}<\/pre>\n<p>&nbsp;<br \/>\n&nbsp;<br \/>\n&nbsp;<br \/>\n<a href=\"https:\/\/github.com\/pome1618\/elliptic_curve_study\/blob\/master\/1\/2\/div.c\">Github\u306e\u65b9<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u6709\u9650\u4f53Fp\u4e0a\u3067\u306e\u9664\u7b97\u3092\u62e1\u5f35Euclid\u4e92\u9664\u6cd5\u3092\u7528\u3044\u3066\u9ad8\u901f\u5316\u3059\u308b\uff0e &nbsp;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-347","post","type-post","status-publish","format-standard","hentry","category-4"],"_links":{"self":[{"href":"https:\/\/p-0.me\/b\/wp-json\/wp\/v2\/posts\/347","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/p-0.me\/b\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/p-0.me\/b\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/p-0.me\/b\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/p-0.me\/b\/wp-json\/wp\/v2\/comments?post=347"}],"version-history":[{"count":0,"href":"https:\/\/p-0.me\/b\/wp-json\/wp\/v2\/posts\/347\/revisions"}],"wp:attachment":[{"href":"https:\/\/p-0.me\/b\/wp-json\/wp\/v2\/media?parent=347"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/p-0.me\/b\/wp-json\/wp\/v2\/categories?post=347"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/p-0.me\/b\/wp-json\/wp\/v2\/tags?post=347"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}