{"id":361,"date":"2018-04-20T16:51:17","date_gmt":"2018-04-20T07:51:17","guid":{"rendered":"http:\/\/tamatoyaku.com\/b\/?p=361"},"modified":"2018-04-20T16:51:17","modified_gmt":"2018-04-20T07:51:17","slug":"361","status":"publish","type":"post","link":"https:\/\/p-0.me\/b\/p\/361\/","title":{"rendered":"PARI GP\u3067Montgomery curves\u306e\u52a0\u7b97\uff0c2\u500d\u7b97\u516c\u5f0f\u3092\u3064\u304f\u3063\u3066\u307f\u308b"},"content":{"rendered":"

[mathjax]\u4eca\u56de\u306fPARI GP\u3067Montgomery curves\u306e\u52a0\u7b97\uff0c2\u500d\u7b97\u306e\u5b9f\u88c5\u3092\u884c\u3046\uff0e
\n
\n\u3082\u3068\u3082\u3068PARI GP\u306b\u306fWeierstrass\u6a19\u6e96\u5f62\u306e\u95a2\u6570\u3057\u304b\u7528\u610f\u3055\u308c\u3066\u3044\u306a\u3044\u305f\u3081\uff0c\u66f2\u7dda\u3084\u70b9\u3092\u76f8\u4e92\u306b\u5909\u63db\u3059\u308b\u3053\u3068\u306b\u3088\u308a\u52d5\u4f5c\u78ba\u8a8d\u3092\u884c\u3044\u3064\u3064\u5b9f\u88c5\u3092\u884c\u3046\uff0eWeierstass\uff0cMontgomery\u9593\u306e\u66f2\u7dda\u3068\u70b9\u306e\u5909\u63db\u306fWikipedia<\/a>\u306b\u8a18\u8f09\u3055\u308c\u3066\u3044\u308b\u624b\u9806\u306b\u3088\u308a\u884c\u3046\u3053\u3068\u304c\u3067\u304d\u308b\uff0eMontgomery curves\u306e\u52a0\u7b97\uff0c2\u500d\u7b97\u306b\u3064\u3044\u3066\u3082Wikipedia<\/a>\u306b\u8a18\u8f09\u3055\u308c\u3066\u3044\u308b\u3082\u306e\u3092\u5b9f\u88c5\u3059\u308b\uff0e
\n\u305f\u3060\u3057\uff0c\u52a0\u7b97\u306b\u3064\u3044\u3066\u306f\\(mP+nP\\)\u306e\u3068\u304d\\(m>n\\)\u304b\u3064\\(m-n=1\\)\u3068\u3057\u3066\u7c21\u7565\u5316\u3057\u3066\u8a18\u8f09\u3059\u308b\uff0e\u306a\u305c\u306a\u3089\uff0cMontgomery ladder\u3092\u4f7f\u7528\u3059\u308b\u969b\u306b\u306fm-n=1\u304c\u5e38\u306b\u6210\u308a\u7acb\u3064\u305f\u3081\uff0c\u5b9f\u7528\u4e0a\u306f\u554f\u984c\u306a\u3044\u305f\u3081\u3067\u3042\u308b\uff0e
\n 
\n1.\u52a0\u7b97\u306e\u5b9f\u88c5<\/strong>
\n\u4ee5\u4e0b\u306e\u5f0f\u306b\u5f93\u3044\u30b3\u30fc\u30c9\u3092\u66f8\u304f\uff0e
\n$$ X_{m+n}=Z_{m-n}((X_m-Z_m)(X_n+Z_n)+(X_m+Z_m)(X_n-Z_n))^2 $$
\n$$ Z_{m+n}=X_{m-n}((X_m-Z_m)(X_n+Z_n)-(X_m+Z_m)(X_n-Z_n))^2 $$
\n <\/p>\n

add(X1,Z1,Xm,Zm,Xn,Zn,p)={\n\tlocal(a,b,c,d,Xmn,Zmn);\n\ta=Xm+Zm;\n\tb=Xm-Zm;\n\tc=Xn+Zn;\n\td=Xn-Zn;\n\tXmn=Mod(Z1*((b*c+a*d)^2),p);\n\tZmn=Mod(X1*((b*c-a*d)^2),p);\n\treturn([Xmn,Zmn]);\n}\n<\/pre>\n
 
\n2.2\u500d\u7b97\u306e\u5b9f\u88c5<\/strong>
\n\u4ee5\u4e0b\u306e\u5f0f\u306b\u5f93\u3044\u30b3\u30fc\u30c9\u3092\u66f8\u304f\uff0e
\n$$4X_nZ_n=(X_n+Z_n)^2-(X_n-Z_n)^2$$
\n$$X_{2n}=(X_n+Z_n)^2(X_n-Z_n)^2$$
\n$$Z_{2n}=4X_nZ_n((X_n-Z_n)^2+((A+2)\/4)(4X_nZ_n))$$
\n <\/p>\n
dbl(A,X,Z,p)={\n\tlocal(tmp1,tmp2,tmp3,X2,Z2);\n\ttmp1=(X+Z)^2;\n\ttmp2=(X-Z)^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}\n<\/pre>\n
 
\n3.y\u5ea7\u6a19\u306e\u5fa9\u5143<\/strong>
\n\u52d5\u4f5c\u78ba\u8a8d\u306e\u305f\u3081\u306b\u5fc5\u8981\u306a\u306e\u3067\uff0cy\u5ea7\u6a19\u306e\u5fa9\u5143\u3092\u884c\u3046\uff0e\u5f0f\u306fHandbook of Elliptic and Hyperelliptic Curve Cryptography\u306b\u8a18\u8f09\u3057\u3066\u3042\u308b\u4ee5\u4e0b\u306e\u5f0f\u3092\u4f7f\u3046\uff0e
\n$$y_n = \\frac{(x_1 x_n +1)(x_1 + x_n +2A)-2A-(x_1-x_n)^2x_{n+1}}{2By_1}$$
\n\u30b3\u30fc\u30c9\u3068\u3057\u3066\u306f\u4ee5\u4e0b\u306e\u3088\u3046\u306b\u306a\u308b\uff0e<\/p>\n
recover(A,B,x1,y1,xn,xn1,p)={\n\tlocal(up,down);\n\tup=(x1*xn+1)*(x1+xn+2*A)-2*A-((x1-xn)^2)*xn1;\n\tdown=2*B*y1;\n\treturn(Mod(up\/down,p));\n}<\/pre>\n
 
\n4.\u52d5\u4f5c\u78ba\u8a8d<\/strong>
\n4.1.\u66f2\u7dda\u306e\u6c7a\u5b9a\u3068\u5909\u63db<\/strong>
\n\u4eca\u56de\u306f\u4f8b\u3068\u3057\u3066Montgomery curves\u306e1\u3064\u3067\u3042\u308b\\(y^2=x^3+84x^2+x\\)\u3092\u4f7f\u3063\u3066\u52d5\u4f5c\u78ba\u8a8d\u3092\u884c\u3046\uff0e\u6700\u521d\u306b\\(y^2=x^3+84x^2+x\\)\u3092Weierstrass\u6a19\u6e96\u5f62\u306b\u3059\u308b\uff0e
\n\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0<\/a>\u3088\u308a\\(A=84,B=1\\)\u3068\u306a\u308b\u305f\u3081\uff0c
\n$$\\begin{array}{rcl}a&=&\\frac{3-A^2}{3B^2}\\\\&=&-2351\\end{array}$$
\n$$\\begin{array}{rcl}b&=&\\frac{2A^3-9A}{27B^3}\\\\&=&43876\\end{array}$$
\n\u3068\u306a\u308a\uff0cMontgomery curves\u306e\\(y^2=x^3+84x^2+x\\)\u306fWeierstrass\u6a19\u6e96\u5f62\u3067\u306f\\(y^2=x^3-2351x+43876\\)\u3068\u306a\u308b\uff0e
\n 
\n4.2.\u30d9\u30fc\u30b9\u30dd\u30a4\u30f3\u30c8\\(P_W\\)\u306e\u751f\u6210\u3068\\(2P_W\\)\u306e\u78ba\u8a8d<\/strong>
\n\u6b21\u306b\uff0cPARI GP\u306e\u6a5f\u80fd\u3092\u7528\u3044\u3066Weierstrass\u6a19\u6e96\u5f62\u3067\u30e9\u30f3\u30c0\u30e0\u306a\u70b9\\(P_W\\)\u3092\u751f\u6210\u3057\uff0c\\(P_W,2P_W\\)\u3092\u78ba\u8a8d\u3059\u308b\uff0e
\n\u306a\u304a\uff0c\\(p=251\\)\u3068\u3057\uff0c\u6709\u9650\u4f53\\(F_{251}\\)\u4e0a\u306e\u6955\u5186\u66f2\u7dda\u3068\u3059\u308b\uff0e<\/p>\n
(17:41) gp > e=ellinit([0,0,0,-2351,43876],251)\n%88 = [Mod(0, 251), Mod(0, 251), Mod(0, 251), Mod(159, 251), Mod(202, 251), Mod(0, 251), Mod(67, 251), Mod(55, 251), Mod(70, 251), Mod(149, 251), Mod(168, 251), Mod(133, 251), Mod(170, 251), Vecsmall([3]), [251, [244, 215, [6, 0, 0, 0]]], [0, 0, 0, 0]]\n(17:46) gp > Pw=random(e)\n%89 = [Mod(201, 251), Mod(28, 251)]\n(17:46) gp > ellmul(e,Pw,2)\n%90 = [Mod(50, 251), Mod(154, 251)]<\/pre>\n
\\(P_W=(201,28),2P_W=(50,154)\\)\u3068\u306a\u3063\u305f\uff0e
\n 
\n4.3.\\(P_W\\)\u3092Montgomery curves\u306e\u70b9\\(P_M\\)\u306b\u5909\u63db<\/strong>
\nWeierstrass\u6a19\u6e96\u5f62\u306e\u70b9\\(P_W=(t,v)\\)\u3092Montgomery curve\u306e\u70b9\\(P_M=(x,y)\\)\u306b\u5909\u63db\u3059\u308b\uff0e
\n\\(s=1,\\alpha=28\\)\u3068\u306a\u308b\u305f\u3081\uff0c
\n$$\\begin{array}{rcl}(t,v)&=>&(x,y)\\\\&=&(s(t-\\alpha),sv)\\\\&=&(t-28,v)\\end{array}$$
\n$$(201,28)=>(173,28)$$
\n\u3088\u3063\u3066\uff0c\\(P_W=(201,28)\\)\u306f\\(P_M=(173,28)\\)\u3068\u5909\u63db\u3067\u304d\u308b\uff0e
\n 
\n4.4.\\(P_M\\)\u3092\u5c04\u5f71\u5ea7\u6a19\u306b\u5909\u63db<\/strong>
\n\\(P_M=(x,y)=(173,28)\\)\u3092\u5c04\u5f71\u5ea7\u6a19\u306b\u5909\u63db\u3059\u308b\u3068\uff0c\\(P_M=(X_1,Y_1,Z_1)=(173,28,1)\\)\u3068\u306a\u308b\uff0e\u3055\u3089\u306by\u5ea7\u6a19\u306f\u6f14\u7b97\u306b\u5fc5\u8981\u306a\u3044\u305f\u3081\u3053\u308c\u3092\u7c21\u7565\u5316\u3057\u3066\uff0c\u4ee5\u964d\u306f\\(P_M=(X_1,Z_1)=(173,1)\\)\u3068\u3059\u308b\uff0e
\n 
\n4.5.\\(2P_M,3P_M\\)\u306e\u78ba\u8a8d<\/strong>
\n\u5148\u307b\u3069\u4f5c\u6210\u3057\u305f\u30b3\u30fc\u30c9\u3092\u3064\u304b\u3063\u3066\uff0c\\(2P_M=dbl(P_M),3P_M=add(2P_M,P_M)\\)\u3092\u6c42\u3081\u308b\uff0e\u306a\u304a\uff0c\\(3P_M\\)\u3092\u6c42\u3081\u308b\u306e\u306f\\(2P_M\\)\u306ey\u5ea7\u6a19\u3092\u5fa9\u5143\u3059\u308b\u305f\u3081\u3067\u3042\u308b\uff0e
\n <\/p>\n
(14:51) gp > dbl(84,173,1,251)\n%4 = [Mod(218, 251), Mod(124, 251)]\n(14:52) gp > add(173,1,218,124,173,1,251)\n%5 = [Mod(93, 251), Mod(219, 251)]<\/pre>\n
 
\n\u3088\u3063\u3066\uff0c
\n$$P_M=(173,1)\\\\2P_M=(218,124)\\\\3P_M=(93,219)$$
\n\u3068\u306a\u308b\u3053\u3068\u304c\u308f\u304b\u308b\uff0e
\n 
\n4.6.\\(2P_M=(x_2,y_2)\\)\u306e\\(y_2\\)\u306e\u5fa9\u5143<\/strong>
\n\\(2P_M\\)\u306ey\u5ea7\u6a19\u3092\u5fa9\u5143\u3059\u308b\uff0e\u305d\u306e\u6e96\u5099\u3068\u3057\u3066\uff0c\u5404\u70b9\u3092\u5c04\u5f71\u5ea7\u6a19\u304b\u3089\u30a2\u30d5\u30a3\u30f3\u5ea7\u6a19\u3078\u3068\u5909\u63db\u3059\u308b\uff0e\u5909\u63db\u306f\\((x,y)=(X\/Z,Y\/Z)\\)\u3068\u3057\u3066\u884c\u3046\uff0e\u306a\u304a\uff0c\\(2P_M,3P_M\\)\u306ey\u5ea7\u6a19\u306fY\u304c\u308f\u304b\u3089\u306a\u3044\u305f\u3081\u8a08\u7b97\u4e0d\u80fd\u3067\uff0c\u305d\u3053\u306f?\u3068\u3057\u3066\u3044\u308b\uff0e
\n 
\n$$\\begin{array}{rcl}P_M&=&(X_1,Z_1)&=&(173,1)&,&(x_1,y_1)&=&(173,28)\\\\2P_M&=&(X_2,Z_2)&=&(218,124)&,&(x_2,y_2)&=&(22,?)\\\\3P_M&=&(X_3,Z_3)&=&(93,219)&,&(x_3,y_3)&=&(52,?)\\end{array}$$
\n 
\n\\(x_1,y_1,x_2,x_3\\)\u304c\u63c3\u3063\u305f\u306e\u3067\\(y_2\\)\u306e\u5fa9\u5143\u3092\u884c\u3046\uff0e<\/p>\n
(15:22) gp > recover(84,1,173,28,22,52,251)\n%12 = Mod(154, 251)<\/pre>\n
\u305d\u306e\u7d50\u679c\uff0c\\(2P_M=(x_2,y_2)=(22,154)\\)\u3068\u306a\u308b\u3053\u3068\u304c\u308f\u304b\u3063\u305f\uff0e
\n 
\n4.7.\\(2P_M\\)\u304c\\(2P_W\\)\u3068\u7b49\u3057\u304f\u306a\u308b\u3053\u3068\u306e\u78ba\u8a8d<\/strong>
\n\\(2P_M=(x_2,y_2)=(22,154)=>(22+28,154)=(50,154)=2P_W\\)\u3068\u306a\u308b\u305f\u3081\uff0c\u70b9\u306e2\u500d\u7b97\u306f\u6b63\u3057\u304f\u5b9f\u884c\u3067\u304d\u305f\u3053\u3068\u304c\u5206\u304b\u308b\uff0e\u307e\u305f\uff0cy\u5ea7\u6a19\u3092\u5fa9\u5143\u3059\u308b\u305f\u3081\u306b\u70b9\u306e\u52a0\u7b97\u3092\u884c\u3063\u305f\u305f\u3081\uff0c\u70b9\u306e\u52a0\u7b97\u306b\u3064\u3044\u3066\u3082\u6b63\u3057\u304f\u5b9f\u88c5\u3067\u304d\u305f\u3068\u8003\u3048\u308b\uff0e
\n 
\n5.\u4eca\u56de\u306e\u30bd\u30fc\u30b9\u30b3\u30fc\u30c9<\/strong><\/p>\n
add(X1,Z1,Xm,Zm,Xn,Zn,p)={\n\tlocal(a,b,c,d,Xmn,Zmn);\n\ta=Xm+Zm;\n\tb=Xm-Zm;\n\tc=Xn+Zn;\n\td=Xn-Zn;\n\tXmn=Mod(Z1*((b*c+a*d)^2),p);\n\tZmn=Mod(X1*((b*c-a*d)^2),p);\n\treturn([Xmn,Zmn]);\n}\ndbl(A,X,Z,p)={\n\tlocal(tmp1,tmp2,tmp3,X2,Z2);\n\ttmp1=(X+Z)^2;\n\ttmp2=(X-Z)^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);\n\tup=(x1*xn+1)*(x1+xn+2*A)-2*A-((x1-xn)^2)*xn1;\n\tdown=2*B*y1;\n\treturn(Mod(up\/down,p));\n}\n<\/pre>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
[mathjax]\u4eca\u56de\u306fPARI GP\u3067Montgomery curves\u306e\u52a0\u7b97\uff0c2\u500d\u7b97\u306e\u5b9f\u88c5\u3092\u884c\u3046\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-361","post","type-post","status-publish","format-standard","hentry","category-4"],"_links":{"self":[{"href":"https:\/\/p-0.me\/b\/wp-json\/wp\/v2\/posts\/361","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=361"}],"version-history":[{"count":0,"href":"https:\/\/p-0.me\/b\/wp-json\/wp\/v2\/posts\/361\/revisions"}],"wp:attachment":[{"href":"https:\/\/p-0.me\/b\/wp-json\/wp\/v2\/media?parent=361"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/p-0.me\/b\/wp-json\/wp\/v2\/categories?post=361"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/p-0.me\/b\/wp-json\/wp\/v2\/tags?post=361"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}