{"id":424,"date":"2026-02-15T22:21:16","date_gmt":"2026-02-15T14:21:16","guid":{"rendered":"http:\/\/www.triode.cc\/?p=424"},"modified":"2026-02-15T22:21:17","modified_gmt":"2026-02-15T14:21:17","slug":"echnp","status":"publish","type":"post","link":"https:\/\/www.triode.cc\/index.php\/2026\/02\/15\/echnp\/","title":{"rendered":"\u692d\u5706\u66f2\u7ebf\u9690\u85cf\u6570\u95ee\u9898\uff08Elliptic Curve Hidden Number Problem\uff09"},"content":{"rendered":"\n
\n

\u53c2\u8003\u8d44\u6599\uff1aHidden Number Problems<\/a><\/p>\n<\/blockquote>\n\n\n\n

\u95ee\u9898\u7b80\u8ff0<\/h2>\n\n\n\n

\\(\\text{ECHNP}\\)<\/h3>\n\n\n\n

\u7ed9\u5b9a\u8d28\u6570\\(p\\)\u3001\u4e00\u6b63\u6574\u6570\\(m\\)\u3001\u4e00\\(\\mathbb{F}_{p^m}\\)\u4e0a\u7684\u692d\u5706\u66f2\u7ebf\\(E\\)\uff0c\u70b9\\(Q\\in{E}\\)\uff0c\u4ee5\u53ca\u7531\\(Q\\)\u751f\u6210\u7684\u70b9\\(R\\in{\\langle Q\\rangle}\\)\uff0c\u8bbe\\(f\\)\u4e3a\u4e00\u4e2a\\(E\\)\u4e0a\u7684\u51fd\u6570\uff0c\\(P\\)\u4e3a\\(E\\)\u4e0a\u4e00\u672a\u77e5\u70b9\uff0c\u5e76\u8bbe\u4e00\u9884\u8a00\u673a\\(\\mathcal{O}_{P,R}(t)\\)\uff0c\u5176\u8f93\u5165\u4e3a\\(t\\)\uff0c\u8f93\u51fa\u4e3a\uff1a<\/p>\n\n\n\n

$$
\\mathcal{O}_{P,R}(t)=f(P+tR)
$$ <\/p>\n\n\n\n

\u90a3\u4e48\u692d\u5706\u66f2\u7ebf\u9690\u85cf\u6570\u95ee\u9898\uff08\\(\\text{ECHNP}\\)\uff09\u5219\u662f\u901a\u8fc7\u9884\u8a00\u673a\\(\\mathcal{O}_{P,R}(t)\\)\u7684\u82e5\u5e72\u4e2a\u8f93\u51fa\u6765\u6062\u590d\u70b9\\(P\\).
\u800c\u5bf9\u4e8e\\(m=1\\)\uff0c\u4e14\u51fd\u6570\\(f(X)=\\text{MSB}_k(X_{\\psi})\\)\uff08\u5373\u53d6\u70b9\\(X\\)\u7684\\(\\psi\\)-\u5750\u6807\u7684\u9ad8\\(k\\)\u4f4d\uff0c\u5176\u4e2d\\(\\psi\\in{x,y}\\)\uff09\uff0c\u5219\u6709\\(\\text{ECHNP}_{\\psi}\\)\uff1a<\/p>\n\n\n\n

\\(\\text{ECHNP}_{\\psi}\\)<\/h3>\n\n\n\n

\u7ed9\u5b9a\u8d28\u6570\\(p\\)\u3001\u6b63\u6574\u6570\\(k\\)\u3001\u4e00\\(\\mathbb{F}_{p}\\)\u4e0a\u7684\u692d\u5706\u66f2\u7ebf\\(E\\)\uff0c\u70b9\\(Q\\in{E}\\)\uff0c\u4ee5\u53ca\u7531\\(Q\\)\u751f\u6210\u7684\u70b9\\(R\\in{\\langle Q\\rangle}\\)\uff0c\u8bbe\\(P\\)\u4e3a\\(E\\)\u4e0a\u4e00\u672a\u77e5\u70b9\uff0c\u5e76\u8bbe\u4e00\u9884\u8a00\u673a\\(\\mathcal{O}_{P,R}(t)\\)\uff0c\u5176\u8f93\u5165\u4e3a\\(t\\)\uff0c\u8f93\u51fa\u4e3a\uff1a<\/p>\n\n\n\n

$$
\\mathcal{O}_{P,R}(t)=\\text{MSB}_k((P+tR)_{\\psi})
$$<\/p>\n\n\n\n

\u90a3\u4e48\\(\\text{ECHNP}_{\\psi}\\)\u5219\u662f\u901a\u8fc7\u9884\u8a00\u673a\\(\\mathcal{O}_{P,R}(t)\\)\u7684\u82e5\u5e72\u4e2a\u8f93\u51fa\u6765\u6062\u590d\u70b9\\(P\\).<\/p>\n\n\n\n

\u6c42\u89e3\\(\\text{ECHNP}_{x}\\)<\/h2>\n\n\n\n

\u5b58\u5728\u4e00\u79cd\u591a\u9879\u5f0f\u65f6\u95f4\u7684\u7b97\u6cd5\u6765\u6c42\u89e3\\(k>\\frac{5}{6}\\log{p}\\)\u60c5\u51b5\u4e0b\u7684\\(\\text{ECHNP}_{x}\\).<\/p>\n\n\n\n

\n

\u4ee5\u4e0b\u8ba8\u8bba\u5747\u5efa\u7acb\u5728Weierstrass\u65b9\u7a0b\u5b9a\u4e49\u7684\u692d\u5706\u66f2\u7ebf\u4e0a.<\/p>\n<\/blockquote>\n\n\n\n

\u6839\u636e\u692d\u5706\u66f2\u7ebf\u76f8\u5f02\u70b9\u7684\u52a0\u6cd5\u53ef\u4ee5\u77e5\u9053\uff0c\u5bf9\u4e8e\u66f2\u7ebf\u4e0a\u4e24\u76f8\u5f02\u70b9\\(P(x_P,y_P),Q(x_Q,y_Q)\\)\uff0c\u5176\u548c\\(P+Q\\)\u7684\u6a2a\u5750\u6807\u8ba1\u7b97\u5982\u4e0b\uff1a<\/p>\n\n\n\n

$$
x_{P+Q}=\\left(\\frac{y_Q-y_P}{x_Q-x_P}\\right)^2-x_P-x_Q
$$<\/p>\n\n\n\n

\u6240\u4ee5\u53ef\u4ee5\u77e5\u9053\uff1a<\/p>\n\n\n\n

$$
\\mathcal{O}_{P,R}(t)=\\text{MSB}_k((P+tR)_{x})=\\text{MSB}_k\\left(\\left(\\frac{y_{tR}-y_P}{x_{tR}-x_P}\\right)^2-x_P-x_{tR}\\mod{p}\\right)
$$<\/p>\n\n\n\n

\u800cMSB\u4e5f\u53ef\u4ee5\u7b49\u4ef7\u4e8e\u51cf\u53bb\u4e00\u4e2a\u8f83\u5c0f\u91cf\\(e\\)\uff0c\u90a3\u4e48\u53ef\u4ee5\u5f97\u5230\uff1a<\/p>\n\n\n\n

$$
\\mathcal{O}_{P,R}(t)=\\text{MSB}_k\\left(\\left(\\frac{y_{tR}-y_P}{x_{tR}-x_P}\\right)^2-x_P-x_{tR}\\mod{p}\\right)=\\left(\\frac{y_{tR}-y_P}{x_{tR}-x_P}\\right)^2-x_P-x_{tR}-e\\mod{p}
$$<\/p>\n\n\n\n

\u5176\u4e2d\\(|e|\\le p\/2^{k+1}\\)\uff0c\u6211\u4eec\u4ee4\\(h=\\mathcal{O}_{P,R}(t)\\)\uff0c\u5219\u53ef\u4ee5\u5f97\u5230\uff1a <\/p>\n\n\n\n

$$
h\\equiv\\left(\\frac{y_{tR}-y_P}{x_{tR}-x_P}\\right)^2-x_P-x_{tR}-e\\pmod{p}
$$<\/p>\n\n\n\n

\u53ef\u5c06\\(x\\)\u5750\u6807\u4e0e\\(y\\)\u5750\u6807\u5206\u522b\u79fb\u5230\u7b49\u53f7\u4e24\u8fb9\uff1a<\/p>\n\n\n\n

$$
(h+x_P+x_{tR}+e)(x_{tR}-x_P)^2\\equiv(y_{tR}-y_P)^2\\equiv y_{tR}^2-2y_{tR}y_{P}+y_{P}^2\\pmod{p}
$$<\/p>\n\n\n\n

\u800c\u56e0\u4e3a\\(y_P^2\\equiv x_P^3+ax_P+b\\pmod{p}\\)\uff0c\u5219\u6709\uff1a<\/p>\n\n\n\n

$$
(h+x_P+x_{tR}+e)(x_{tR}-x_P)^2\\equiv(y_{tR}-y_P)^2\\equiv y_{tR}^2-2y_{tR}y_{P}+x_P^3+ax_P+b\\pmod{p}
$$<\/p>\n\n\n\n

\u7136\u800c\u4e0a\u9762\u6709\u6211\u4eec\u5e76\u4e0d\u671f\u671b\u51fa\u73b0\u7684\\(y_P\\)\uff0c\u6545\u6211\u4eec\u9700\u8981\u8fdb\u884c\u6d88\u5143\uff0c\u5bf9\u4e8e\u4efb\u4e00\u6b63\u6574\u6570\\(t\\)\uff0c\u4ee4\\(Q=tR\\)\uff0c\u6211\u4eec\u53ef\u4ee5\u901a\u8fc7\u9884\u8a00\u673a\u5f97\u5230\\((P+Q)_x\\)\u4ee5\u53ca\\((P-Q)_x\\)\u7684MSB\uff0c\u800c\u5728\\(\\mathbb{F}_p\\)\u4e0a\u6709\uff1a <\/p>\n\n\n\n

$$
\\begin{aligned}
(P+Q)_x+(P-Q)_x&=\\left(\\frac{y_P-y_Q}{x_P-x_Q}\\right)^2-x_P-x_Q+\\left(\\frac{y_P+y_Q}{x_P-x_Q}\\right)^2-x_P-x_Q\\\\
&=\\frac{2(y_P^2+y_Q^2)}{(x_P-x_Q)^2}-2x_P-2x_Q\\\\
&=2\\left(\\frac{x_Qx_P^2+(a+x_Q^2)x_P+ax_Q+2b}{(x_P-x_Q)^2}\\right)
\\end{aligned}
$$ <\/p>\n\n\n\n

\u6211\u4eec\u4ee4\\(h=\\mathcal{O}_{P,R}(t)=(P+Q)_x-e,h’=\\mathcal{O}_{P,R}(-t)=(P-Q)_x-e’\\)\uff0c\u5e76\u4ee4\\(\\widetilde{h}=h+h’,\\widetilde{e}=e+e’\\)\uff0c\u7531\u4e0a\u9762\u7684\u63a8\u5bfc\u53ef\u4ee5\u5f97\u5230\uff1a\\(\\widetilde{h}+\\widetilde{e}=(P+Q)_x+(P-Q)_x\\)\uff0c\u53c8\u56e0\u4e3a\u5f53\\(t=0\\)\u7684\u65f6\u5019\uff0c\u6709\\(\\mathcal{O}_{P,R}(0)=x_P-e_0\\)\uff08\u5176\u4e2d\\(e_0\\)\u4e3a\u4e00\u6574\u6570\uff09\uff0c\u90a3\u4e48\u6211\u4eec\u8bb0\\(h_0=\\mathcal{O}_{P,R}(0)\\)\uff0c\u5219\u6709\\(x_P=h_0+e_0\\)\uff0c\u7efc\u5408\u4e0a\u8ff0\u63a8\u5bfc\u5c31\u53ef\u4ee5\u5f97\u5230\uff1a <\/p>\n\n\n\n

$$
\\begin{aligned}
\\widetilde{h}+\\widetilde{e}&=(P+Q)_x+(P-Q)_x\\\\
&=2\\left(\\frac{x_Qx_P^2+(a+x_Q^2)x_P+ax_Q+2b}{(x_P-x_Q)^2}\\right)\\\\
&=2\\left(\\frac{x_Q(h_0+e_0)^2+(a+x_Q^2)(h_0+e_0)+ax_Q+2b}{(h_0+e_0-x_Q)^2}\\right)
\\end{aligned}
$$ <\/p>\n\n\n\n

\u663e\u7136\u7684\uff0c\u4e0a\u5f0f\u4e2d\u53ea\u6709\\(e_0,\\widetilde{e}\\)\u662f\u672a\u77e5\u7684\uff0c\u6211\u4eec\u4ee4\u4e24\u8fb9\u4e58\u4e0a\\((h_0+e_0-x_Q)^2\\)\u53ef\u4ee5\u5f97\u5230\uff1a <\/p>\n\n\n\n

$$
(\\widetilde{h}+\\widetilde{e})(h_0+e_0-x_Q)^2=2(x_Q(h_0+e_0)^2+(a+x_Q^2)(h_0+e_0)+ax_Q+2b)
$$ <\/p>\n\n\n\n

\u4ece\u800c\u53ef\u4ee5\u4ece\u4e2d\u5f97\u5230\u4e00\u4e2a\u591a\u9879\u5f0f\uff1a <\/p>\n\n\n\n

$$
F(X,Y)=(\\widetilde{h}+Y)(h_0-x_Q+X)^2-2(x_Q(h_0+X)^2+(a+x_Q^2)(h_0+X)+ax_Q+2b)
$$ <\/p>\n\n\n\n

\u5c55\u5f00\u6574\u7406\u5219\u6709\uff1a <\/p>\n\n\n\n

$$
\\begin{aligned}
F(X,Y)=&X^2Y+(\\widetilde{h}-2x_Q)X^2+2(h_0-x_Q)XY+2[\\widetilde{h}(h_0-x_Q)-2h_0x_Q-a-x_Q^2]X\\\\
&+(h_0-x_Q)^2Y+[\\widetilde{h}(h_0-x_Q)^2-2h_0^2x_Q-2(a+x_Q)h_0-2ax_Q-4b]
\\end{aligned}
$$ <\/p>\n\n\n\n

\u5f88\u663e\u7136\uff0c\u8be5\u591a\u9879\u5f0f\u6ee1\u8db3\\(F(e_0,\\widetilde{e})\\equiv0\\pmod{p}\\)\uff0c\u6839\u636e\u4e0a\u8ff0\u65b9\u6cd5\uff0c\u6211\u4eec\u53d6\\(n\\)\u7ec4\\((\\mathcal{O}_{P,R}(t_i),\\mathcal{O}_{P,R}(-t_i))=(h_i,h_i’)\\)\u8fdb\u884c\u4e0a\u8ff0\u64cd\u4f5c\u5c31\u53ef\u4ee5\u5f97\u5230\\(n\\)\u4e2a\u591a\u9879\u5f0f\uff1a<\/p>\n\n\n\n

$$
F_i(X,Y)=X^2Y+A_iX^2+A_{0,i}XY+B_iX+B_{0,i}Y+C_i
$$<\/p>\n\n\n\n

\u6ee1\u8db3\\(F_i(e_0,\\widetilde{e}_i)\\equiv0\\pmod{p}\\)\uff0c\u5176\u4e2d\uff1a <\/p>\n\n\n\n

$$
\\begin{aligned}
A_i&=\\widetilde{h}_i-2x_{Q_i}\\\\
A_{0,i}&=2(h_0-x_{Q_i})\\\\
B_i&=2[\\widetilde{h}_i(h_0-x_{Q_i})-2h_0x_{Q_i}-a-x_{Q_i}^2]\\\\
B_{0,i}&=(h_0-x_{Q_i})^2\\\\
C_i&=\\widetilde{h}_i(h_0-x_{Q_i})^2-2h_0^2x_{Q_i}-2(a+x_{Q_i}^2)h_0-2ax_{Q_i}-4b
\\end{aligned}
$$<\/p>\n\n\n\n

\u6b64\u65f6\u53ef\u4ee5\u6784\u9020\u77e9\u9635\uff1a<\/p>\n\n\n\n

$$
M=\\left(\\begin{matrix}
\\Delta_1&0&M_1\\\\
0&\\Delta_2&M_2\\\\
0&0&pI
\\end{matrix}\\right)
$$<\/p>\n\n\n\n

\u5176\u4e2d\\(\\Delta_1,\\Delta_2\\)\u7684\u5b9a\u4e49\u5982\u4e0b\uff1a<\/p>\n\n\n\n

$$
\\Delta_1=diag(
2^{3k},\\underbrace{2^{2k},\\cdots,2^{2k}}_{n+1\u4e2a}), \\Delta_2=2^kI_{n+1}
$$<\/p>\n\n\n\n

\u800c\\(M_1,M_2\\)\u5b9a\u4e49\u5982\u4e0b\uff1a<\/p>\n\n\n\n

$$
M_1=\\left(\\begin{matrix}
-C_1&-C_2&\\cdots&-C_n\\\\
-B_1&-B_2&\\cdots&-B_n\\\\
-B_{0,1}&&\\\\
&-B_{0,2}&\\\\
&&\\ddots&\\\\
&&&-B_{0,n}
\\end{matrix}\\right),
M_2=\\left(\\begin{matrix}
-A_1&-A_2&\\cdots&-A_n\\\\
-A_{0,1}&&\\\\
&-A_{0,2}&\\\\
&&\\ddots&\\\\
&&&-A_{0,n}
\\end{matrix}\\right)
$$<\/p>\n\n\n\n

\u5219\u5b58\u5728\u5411\u91cf\\(v=(1,e_0,\\widetilde{e}_1,\\cdots,\\widetilde{e}_n,e_0^2,e_0\\widetilde{e}_1,\\cdots,e_0\\widetilde{e}_n,k_1,\\cdots,k_n)\\)\u4f7f\u5f97\uff1a<\/p>\n\n\n\n

$$
vM=(2^{3k},2^{2k}e_0,2^{2k}\\widetilde{e}_1,\\cdots,2^{2k}\\widetilde{e}_n,2^ke_0^2,2^ke_0\\widetilde{e}_1,\\cdots,2^ke_0\\widetilde{e}_n,e_0^2\\widetilde{e}_1,\\cdots,e_0^2\\widetilde{e}_n)
$$<\/p>\n\n\n\n

\u5f88\u5bb9\u6613\u53ef\u4ee5\u8bc1\u660e\u4e0a\u8ff0\u5411\u91cf\u53ef\u4ee5\u901a\u8fc7\u89c4\u7ea6\u5f97\u51fa\uff0c\u6c42\u89e3\u4ee3\u7801\u6a21\u677f\u5982\u4e0b\uff1a<\/p>\n\n\n\n

<\/circle><\/circle><\/circle><\/g><\/svg><\/span>