{"id":364,"date":"2018-04-21T21:26:56","date_gmt":"2018-04-21T12:26:56","guid":{"rendered":"http:\/\/tamatoyaku.com\/b\/?p=364"},"modified":"2018-04-21T21:26:56","modified_gmt":"2018-04-21T12:26:56","slug":"364","status":"publish","type":"post","link":"https:\/\/p-0.me\/b\/p\/364\/","title":{"rendered":"PARI GP\u306bMontgomery ladder\u3092\u5b9f\u88c5\u3059\u308b"},"content":{"rendered":"<p>[mathjax]<a href=\"https:\/\/tamatoyaku.com\/b\/p\/361\">\u524d\u56de<\/a>\u306e\u7d9a\u304d\uff0e\u4eca\u56de\u306fMontgomery ladder\uff0e<br \/>\n<!--more--><br \/>\n\u4eca\u56de\u306fMontgomery ladder\u3092\u5b9f\u88c5\u3059\u308b\uff0e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f<a href=\"https:\/\/en.wikipedia.org\/wiki\/Elliptic_curve_point_multiplication#Montgomery_ladder\">Wikipedia<\/a>\u306b\u3082\u8f09\u3063\u3066\u3044\u308b\uff0e\u898b\u308c\u3070\u5206\u304b\u308b\u3088\u3046\u306b\uff0c\u4ed5\u7d44\u307f\u3068\u3057\u3066\u306f\u30d0\u30a4\u30ca\u30ea\u6cd5\u3068\u540c\u3058\u7a0b\u5ea6\u306b\u7c21\u7d20\u306a\u3082\u306e\u3068\u306a\u3063\u3066\u3044\u308b\uff0e\u3057\u304b\u3057\uff0c\u30d0\u30a4\u30ca\u30ea\u6cd5\u3068\u6bd4\u8f03\u3057\u3066\u30b5\u30a4\u30c9\u30c1\u30e3\u30cd\u30eb\u653b\u6483\u306b\u5f37\u3044\u3068\u3044\u3046\u7279\u6027\u3092\u6301\u3064\uff0e\u30d0\u30a4\u30ca\u30ea\u6cd5\u3067\u306fk[i]\u306e\u5024\u304c1\u304b0\u304b\u3067\u52a0\u7b97\u306e\u6709\u7121\u304c\u6c7a\u307e\u308a\uff0c\u3053\u308c\u3092\u5916\u90e8\u304b\u3089\u89b3\u5bdf\u3059\u308b\u3068k\u304c\u5fa9\u5143\u3055\u308c\u308b\u3068\u3044\u3046\u5f31\u70b9\u304c\u4f1a\u3063\u305f\uff0e\u4e00\u65b9\u3067Montgomery ladder\u3067\u306fk[i]\u306e\u5024\u306b\u95a2\u308f\u3089\u305a\u52a0\u7b97\u30682\u500d\u7b97\u3092\u6bce\u56de\u884c\u3046\u306e\u3067\uff0c\u30b5\u30a4\u30c9\u30c1\u30e3\u30cd\u30eb\u653b\u6483\u306b\u8010\u6027\u3092\u6301\u3064\uff0e<br \/>\nMontgomery ladder\u306e\u30b3\u30fc\u30c9\u306f\u4ee5\u4e0b\u306e\u3088\u3046\u306b\u306a\u308b\uff0e<\/p>\n<pre class=\"lang:default decode:true \">ladder(A,P,k,p)={\n\tlocal(R0,R1,i,bin);\n\tbin=binary(k);\n\tR0=[0];\n\tR1=P;\n\tfor(i=1,length(bin),\n\t\tif(bin[i]==0,\n\t\t\tR1=add(P,R1,R0,p);\n\t\t\tR0=dbl(A,R0,p);,\n\t\t\tR0=add(P,R1,R0,p);\n\t\t\tR1=dbl(A,R1,p);\n\t\t);\n\t);\n\treturn([R1,R0]);\n}\n<\/pre>\n<p>&nbsp;<br \/>\n\u524d\u56de\u306e\u30b3\u30fc\u30c9\u3092\u4fee\u6b63\u3057\u3064\u3064Montgomery ladder\u306e\u30b3\u30fc\u30c9\u3092\u8db3\u3057\uff0c\u30c6\u30b9\u30c8\u7528\u306e\u30b3\u30fc\u30c9\u3082\u4ed8\u3051\u305f\u5168\u4f53\u306e\u30b3\u30fc\u30c9\u3092\u4ee5\u4e0b\u306b\u793a\u3059\uff0e<br \/>\n\u4fee\u6b63\u70b9\u3068\u3057\u3066\u306f\uff0cadd\u3068dbl\u306e\u5f15\u6570\u3092X,Z\u3068\u3044\u3046\u5f62\u5f0f\u304b\u3089\u70b9P\u306e\u5f62\u5f0f\u306b\u5909\u66f4\u3057\u305f\uff0e\u307e\u305f\uff0c\u7121\u9650\u9060\u70b9\u306b\u95a2\u308f\u308b\u5206\u5c90\u3092\u8ffd\u52a0\u3057\u305f\uff0erecover\u306b\u3064\u3044\u3066\u3082\\(P_{n+1}\\)\u304c<a href=\"https:\/\/tamatoyaku.com\/b\/p\/363\">\u7121\u9650\u9060\u70b9\u306e\u5834\u5408\u306e\u51e6\u7406<\/a>\u306b\u3064\u3044\u3066\u306e\u30b3\u30fc\u30c9\u3092\u8ffd\u52a0\u3057\u305f\uff0e<br \/>\n&nbsp;<\/p>\n<pre class=\"lang:default decode:true \">\\\\m-n==1\nadd(P1,Pm,Pn,p)={\n\tlocal(a,b,c,d,Xmn,Zmn);\n\tif(Pm==0||Pm[2]==0,return(Pn));\n\tif(Pn==0||Pn[2]==0,return(Pm));\n\ta=Pm[1]+Pm[2];\n\tb=Pm[1]-Pm[2];\n\tc=Pn[1]+Pn[2];\n\td=Pn[1]-Pn[2];\n\tXmn=Mod(P1[2]*((b*c+a*d)^2),p);\n\tZmn=Mod(P1[1]*((b*c-a*d)^2),p);\n\treturn([Xmn,Zmn]);\n}\ndbl(A,P,p)={\n\tlocal(tmp1,tmp2,tmp3,X2,Z2);\n\tif(P==0||P[2]==0,return([0]));\n\ttmp1=(P[1]+P[2])^2;\n\ttmp2=(P[1]-P[2])^2;\n\ttmp3=tmp1-tmp2;\n\tX2=Mod(tmp1*tmp2,p);\n\tZ2=Mod(tmp3*(tmp2+((tmp3*(A+2))\/4)),p);\n\treturn([X2,Z2]);\n}\nrecover(A,B,x1,y1,xn,xn1,p)={\n\tlocal(up,down,res);\n\tif(xn1==-1,\n\t\treturn(-y1);\n\t);\n\tup=(x1*xn+1)*(x1+xn+2*A)-2*A-((x1-xn)^2)*xn1;\n\tdown=2*B*y1;\n\tif(down==0,\n\t\tres=0;,\n\t\tres=Mod(up\/down,p);\n\t);\n\treturn(res);\n}\nladder(A,P,k,p)={\n\tlocal(R0,R1,i,bin);\n\tbin=binary(k);\n\tR0=[0];\n\tR1=P;\n\tfor(i=1,length(bin),\n\t\tif(bin[i]==0,\n\t\t\tR1=add(P,R1,R0,p);\n\t\t\tR0=dbl(A,R0,p);,\n\t\t\tR0=add(P,R1,R0,p);\n\t\t\tR1=dbl(A,R1,p);\n\t\t);\n\t);\n\treturn([R1,R0]);\n}\n{\nwhile(1,\n\tA=84;B=1;\n\tp=251;\n\te=ellinit([0,0,0,-2351,43876],p);\n\tP_W=random(e);\n\tP_M=[P_W[1]-28,1];\n\tk=random(p);\n\tkP_W=ellmul(e,P_W,k);\n\tpair=ladder(A,P_M,k,p);\n\tkP_M=pair[2];k1P_M=pair[1];\n\tif(kP_M!=[0]&amp;&amp;kP_M[2]==0,kP_M=[0]);\n\tif(k1P_M!=[0]&amp;&amp;k1P_M[2]==0,k1P_M=[0]);\n\tif(kP_M==[0]&amp;&amp;kP_M==kP_W,\n\t\t\/*print(\"GOOD!!\");*\/next();\n\t);\n\tif(kP_M!=[0],\n\t\tx_k=Mod(kP_M[1]\/kP_M[2],p);\n\t\tif(k1P_M==[0]||k1P_M[2]==0,\n\t\t\tx_k1=-1;,\n\t\t\tx_k1=Mod(k1P_M[1]\/k1P_M[2],p);\n\t\t);\n\t\ty_k=recover(A,B,P_M[1],P_W[2],x_k,x_k1,p);\n\t\tif(kP_W==[x_k+28,y_k],\n\t\t\t\/*print(\"GOOD!!\");*\/,\n\t\t\tprint(\"bad...\");\n\t\t\tprint(\"recover(\",A,\"  \",B,\"  \",P_M[1],\"  \",P_W[2],\"  \",x_k,\"  \",x_k1,\"  \",p,\")\");\n\t\t\tprint(\"P_W \",P_W);\n\t\t\tprint(\"P_M \",P_M);\n\t\t\tprint(\"k \",k);\n\t\t\tprint(\"kP_W \",kP_W);\n\t\t\tprint(\"pair \",pair\t);\n\t\t\tprint(\"kP_M \",kP_M);\n\t\t\tprint(\"k1P_M \",k1P_M);\n\t\t\tprint(\"x_k \",x_k);\n\t\t\tprint(\"y_k \",y_k);\n\t\t\tprint(kP_W,\"==\",[x_k+28,y_k]);\n\t\t);\n\t);\n);\n}<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>[mathjax]\u524d\u56de\u306e\u7d9a\u304d\uff0e\u4eca\u56de\u306fMontgomery ladder\uff0e<\/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-364","post","type-post","status-publish","format-standard","hentry","category-4"],"_links":{"self":[{"href":"https:\/\/p-0.me\/b\/wp-json\/wp\/v2\/posts\/364","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=364"}],"version-history":[{"count":0,"href":"https:\/\/p-0.me\/b\/wp-json\/wp\/v2\/posts\/364\/revisions"}],"wp:attachment":[{"href":"https:\/\/p-0.me\/b\/wp-json\/wp\/v2\/media?parent=364"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/p-0.me\/b\/wp-json\/wp\/v2\/categories?post=364"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/p-0.me\/b\/wp-json\/wp\/v2\/tags?post=364"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}