Curba eliptica si ordinul punctului P(1,7)
Moderator: Mihai Fulger
-
Cezar Lupu
- Site Admin
- Posts: 612
- Joined: Wed Sep 26, 2007 2:04 pm
- Location: Bucuresti sau Constanta
- Contact:
Curba eliptica si ordinul punctului P(1,7)
Fie curba eliptica \( C(\mathbb{Z}_{17}) \) definita prin \( y^2=x^3-3x \) si punctul \( P(\hat{1}, \hat{7})\in C(\mathbb{Z}_{17}) \). Sa se determine ordinul punctului \( P \) de pe curba de mai sus.
An infinite number of mathematicians walk into a bar. The first one orders a beer. The second orders half a beer. The third, a quarter of a beer. The bartender says “You’re all idiots”, and pours two beers.
-
Cristi Popa
- Euclid
- Posts: 24
- Joined: Sat Nov 10, 2007 9:31 pm
- Location: Bucuresti / Ramnicu-Valcea
Problema este simpla si se poate rezolva prin doua metode.
Metoda I
Pentru a aduna doua puncte de pe o curba eliptica \( C(\mathbb{Q})\ :\ y^2=x^3+ax^2+bx+c,\ a,b,c\in\mathbb{Z} \) avem nevoie de urmatoarele formule:
Propozitie. Fie \( P_1(x_1,y_1),\ P_2(x_2,y_2),\ P_1*P_2(x_3,y_3)\in C(\mathbb{Q}) \). Au loc urmatoarele formule:
i) daca \( x_1=x_2 \) si \( P_1\neq P_2 \), atunci \( P_1+P_2=\mathcal{O} \);
ii) daca \( x_1\neq x_2 \), atunci \( P_1+P_2=(x_3,-y_3) \), unde
\( \left\{ \begin{array}{ll}
x_3=\lambda^2-a-x_1-x_2\\
-y_3=-\lambda^3+\lambda a+\lambda x_1+\lambda x_2-\nu
\end{array}, \right. \) \( \displaystyle\lambda=\frac{y_1-y_2}{x_1-x_2},\ \nu=y_1-\lambda x_1=y_2-\lambda x_2 \);
iii) daca \( P_1=P_2=P \), atunci \( P_1+P_2=2P=(x_3,-y_3) \), unde
\( \left\{ \begin{array}{ll}
x_3=\lambda^2-a-2x_1\\
-y_3=-\lambda^3+\lambda a+2\lambda x_1-\nu
\end{array}, \right. \) \( \displaystyle\lambda=\frac{f^,(x_1)}{2y_1} \), \( \nu=y_1-\lambda x_1 \).
Folosind aceste formule (calculele se fac modulo 17) gasim:
\( 2P(\overline{-2},\overline{-7}),\ 4P(\overline{-4},\overline{-4}),\ 8P(\overline{-1},\overline{6}),\ 16P(\overline{2},\overline{-6}),\ 32P(\overline{4},\overline{-1}),\ 64P(\overline{1},\overline{-7})=-P. \)
Deci, \( 64P=-P\Rightarrow 65P=\mathcal{O}\Rightarrow ord(P)\in\{1,5,13,65\}. \)
Clar, \( ord(P)\neq1 \).
Daca \( ord(P)=5\Rightarrow 4P=-P \), ceea ce este o contradictie.
Dar, \( 4P+8P=12P=(\overline{1},\overline{-7})=-P\Rightarrow 13P=\mathcal{O}\Rightarrow ord(P)=13 \).
Metoda a II - a
Avem ca \( ord(P)\ |\ |C(\mathbb{Z}_{17})| \).
\( -1\equiv 4^2\ (mod\ 17)\Rightarrow \left(\displaystyle\frac{n}{17}\right)=1\Leftrightarrow\left(\displaystyle\frac{-n}{17}\right)=1 \)
Daca \( \overline{x}=\overline{0}\Rightarrow\overline{y}=\overline{0}\Rightarrow (\overline{0},\overline{0})\in C(\mathbb{Z}_{17}). \)
Daca \( \overline{x}=\overline{1}\Rightarrow\overline{y}=\overline{\pm7}\Rightarrow (\overline{1},\overline{\pm7})\in C(\mathbb{Z}_{17}). \)
Analog, gasim ca \( (\overline{-1},\overline{\pm6}),\ (\overline{2},\overline{\pm6}),\ (\overline{-2},\overline{\pm7}),\ (\overline{3},\overline{\pm1}),\ (\overline{-3},\overline{\pm4}), \)
\( (\overline{4},\overline{\pm1}),\ (\overline{-4},\overline{\pm4}),\ (\overline{5},\overline{\pm5}),\ (\overline{-5},\overline{\pm3}),\ (\overline{7},\overline{\pm4}),\ (\overline{-7},\overline{\pm1})\in C(\mathbb{Z}_{17}). \)
Adaugand si punctul de la infinit \( \mathcal{O} \), obtinem: \( |C(\mathbb{Z}_{17})|=2\cdot12+2=26\Rightarrow ord(P)\in\{1,2,13,26\} \).
Ca si la metoda I, de aici obtinem ca \( ord(P)=13. \)
Metoda I
Pentru a aduna doua puncte de pe o curba eliptica \( C(\mathbb{Q})\ :\ y^2=x^3+ax^2+bx+c,\ a,b,c\in\mathbb{Z} \) avem nevoie de urmatoarele formule:
Propozitie. Fie \( P_1(x_1,y_1),\ P_2(x_2,y_2),\ P_1*P_2(x_3,y_3)\in C(\mathbb{Q}) \). Au loc urmatoarele formule:
i) daca \( x_1=x_2 \) si \( P_1\neq P_2 \), atunci \( P_1+P_2=\mathcal{O} \);
ii) daca \( x_1\neq x_2 \), atunci \( P_1+P_2=(x_3,-y_3) \), unde
\( \left\{ \begin{array}{ll}
x_3=\lambda^2-a-x_1-x_2\\
-y_3=-\lambda^3+\lambda a+\lambda x_1+\lambda x_2-\nu
\end{array}, \right. \) \( \displaystyle\lambda=\frac{y_1-y_2}{x_1-x_2},\ \nu=y_1-\lambda x_1=y_2-\lambda x_2 \);
iii) daca \( P_1=P_2=P \), atunci \( P_1+P_2=2P=(x_3,-y_3) \), unde
\( \left\{ \begin{array}{ll}
x_3=\lambda^2-a-2x_1\\
-y_3=-\lambda^3+\lambda a+2\lambda x_1-\nu
\end{array}, \right. \) \( \displaystyle\lambda=\frac{f^,(x_1)}{2y_1} \), \( \nu=y_1-\lambda x_1 \).
Folosind aceste formule (calculele se fac modulo 17) gasim:
\( 2P(\overline{-2},\overline{-7}),\ 4P(\overline{-4},\overline{-4}),\ 8P(\overline{-1},\overline{6}),\ 16P(\overline{2},\overline{-6}),\ 32P(\overline{4},\overline{-1}),\ 64P(\overline{1},\overline{-7})=-P. \)
Deci, \( 64P=-P\Rightarrow 65P=\mathcal{O}\Rightarrow ord(P)\in\{1,5,13,65\}. \)
Clar, \( ord(P)\neq1 \).
Daca \( ord(P)=5\Rightarrow 4P=-P \), ceea ce este o contradictie.
Dar, \( 4P+8P=12P=(\overline{1},\overline{-7})=-P\Rightarrow 13P=\mathcal{O}\Rightarrow ord(P)=13 \).
Metoda a II - a
Avem ca \( ord(P)\ |\ |C(\mathbb{Z}_{17})| \).
\( -1\equiv 4^2\ (mod\ 17)\Rightarrow \left(\displaystyle\frac{n}{17}\right)=1\Leftrightarrow\left(\displaystyle\frac{-n}{17}\right)=1 \)
Daca \( \overline{x}=\overline{0}\Rightarrow\overline{y}=\overline{0}\Rightarrow (\overline{0},\overline{0})\in C(\mathbb{Z}_{17}). \)
Daca \( \overline{x}=\overline{1}\Rightarrow\overline{y}=\overline{\pm7}\Rightarrow (\overline{1},\overline{\pm7})\in C(\mathbb{Z}_{17}). \)
Analog, gasim ca \( (\overline{-1},\overline{\pm6}),\ (\overline{2},\overline{\pm6}),\ (\overline{-2},\overline{\pm7}),\ (\overline{3},\overline{\pm1}),\ (\overline{-3},\overline{\pm4}), \)
\( (\overline{4},\overline{\pm1}),\ (\overline{-4},\overline{\pm4}),\ (\overline{5},\overline{\pm5}),\ (\overline{-5},\overline{\pm3}),\ (\overline{7},\overline{\pm4}),\ (\overline{-7},\overline{\pm1})\in C(\mathbb{Z}_{17}). \)
Adaugand si punctul de la infinit \( \mathcal{O} \), obtinem: \( |C(\mathbb{Z}_{17})|=2\cdot12+2=26\Rightarrow ord(P)\in\{1,2,13,26\} \).
Ca si la metoda I, de aici obtinem ca \( ord(P)=13. \)