Mixing
Proof of Velu's formulas in Washington's Elliptic Curves
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
The proof of Velu's formulae in Washington's "Elliptic Curves" uses two exercises (Ex. 12.6 and Ex.12.8). One part in Ex.12.6 is the following:
Let $E:y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6$ be an elliptic curve over a field $K$. Let $P,Q$ be two points on $E$. Let $x_P, x_Q, x_P+Q,y_P,y_Q$ denote the $x$- or $y$-coordinates of the points. Let $Q$ be a $2$-torsion point, so $2Q=infty$ and $Q=-Q$. The exercise claims the following equality holds:
$x_P+Q-x_Q=frac3x_Q^2+2a_2x_Q+a_4-a_1y_Qx_P-x_Q$
Since the cases $P=Q=-Q$ don't need examination, we assume $x_Pneq x_Q$ and we can use the addition formula as follows:
$x_P+Q=frac(y_P-y_Q)^2(x_P-x_Q)^2+a_1fracy_P-y_Qx_P-x_Q-a_2-x_P-x_Q$
So we need to show that:
$frac(y_P-y_Q)^2(x_P-x_Q)^2+a_1fracy_P-y_Qx_P-x_Q-a_2-x_P-x_Q-x_Q=frac3x_Q^2+2a_2x_Q+a_4-a_1y_Qx_P-x_Q$
After working on it for a while I noticed that I can't solve it due to the following dead end:
The LHS has a $y_P^2$ term while the RHS has not. After replacing $y_P^2$ using the equation of the curve the LHS has a $a_6$ term while the RHS has not. For all i know dividing those terms by $(x_P-x_Q)$ doesn't change anything. I'm thankful for any kind of information, especially any $equalities$ I might have missed.
Note: Since $Q$ is a $2$-torsion point, we can use the negation formulae for $y$-coordinates $y_Q=-a_1x_Q-a_3-y_Q$ to replace $y_Q^2$ as an expression in $x_Q$. That's why that part isn't an issue for now.
algebraic-geometry elliptic-curves
asked Aug 1 at 13:28
Benedikt Höpers
161
add a comment |Â
up vote
3
down vote
favorite
The proof of Velu's formulae in Washington's "Elliptic Curves" uses two exercises (Ex. 12.6 and Ex.12.8). One part in Ex.12.6 is the following:
Let $E:y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6$ be an elliptic curve over a field $K$. Let $P,Q$ be two points on $E$. Let $x_P, x_Q, x_P+Q,y_P,y_Q$ denote the $x$- or $y$-coordinates of the points. Let $Q$ be a $2$-torsion point, so $2Q=infty$ and $Q=-Q$. The exercise claims the following equality holds:
$x_P+Q-x_Q=frac3x_Q^2+2a_2x_Q+a_4-a_1y_Qx_P-x_Q$
Since the cases $P=Q=-Q$ don't need examination, we assume $x_Pneq x_Q$ and we can use the addition formula as follows:
$x_P+Q=frac(y_P-y_Q)^2(x_P-x_Q)^2+a_1fracy_P-y_Qx_P-x_Q-a_2-x_P-x_Q$
So we need to show that:
$frac(y_P-y_Q)^2(x_P-x_Q)^2+a_1fracy_P-y_Qx_P-x_Q-a_2-x_P-x_Q-x_Q=frac3x_Q^2+2a_2x_Q+a_4-a_1y_Qx_P-x_Q$
After working on it for a while I noticed that I can't solve it due to the following dead end:
The LHS has a $y_P^2$ term while the RHS has not. After replacing $y_P^2$ using the equation of the curve the LHS has a $a_6$ term while the RHS has not. For all i know dividing those terms by $(x_P-x_Q)$ doesn't change anything. I'm thankful for any kind of information, especially any $equalities$ I might have missed.
Note: Since $Q$ is a $2$-torsion point, we can use the negation formulae for $y$-coordinates $y_Q=-a_1x_Q-a_3-y_Q$ to replace $y_Q^2$ as an expression in $x_Q$. That's why that part isn't an issue for now.
algebraic-geometry elliptic-curves
asked Aug 1 at 13:28
Benedikt Höpers
161
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
The proof of Velu's formulae in Washington's "Elliptic Curves" uses two exercises (Ex. 12.6 and Ex.12.8). One part in Ex.12.6 is the following:
Let $E:y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6$ be an elliptic curve over a field $K$. Let $P,Q$ be two points on $E$. Let $x_P, x_Q, x_P+Q,y_P,y_Q$ denote the $x$- or $y$-coordinates of the points. Let $Q$ be a $2$-torsion point, so $2Q=infty$ and $Q=-Q$. The exercise claims the following equality holds:
$x_P+Q-x_Q=frac3x_Q^2+2a_2x_Q+a_4-a_1y_Qx_P-x_Q$
Since the cases $P=Q=-Q$ don't need examination, we assume $x_Pneq x_Q$ and we can use the addition formula as follows:
$x_P+Q=frac(y_P-y_Q)^2(x_P-x_Q)^2+a_1fracy_P-y_Qx_P-x_Q-a_2-x_P-x_Q$
So we need to show that:
$frac(y_P-y_Q)^2(x_P-x_Q)^2+a_1fracy_P-y_Qx_P-x_Q-a_2-x_P-x_Q-x_Q=frac3x_Q^2+2a_2x_Q+a_4-a_1y_Qx_P-x_Q$
After working on it for a while I noticed that I can't solve it due to the following dead end:
The LHS has a $y_P^2$ term while the RHS has not. After replacing $y_P^2$ using the equation of the curve the LHS has a $a_6$ term while the RHS has not. For all i know dividing those terms by $(x_P-x_Q)$ doesn't change anything. I'm thankful for any kind of information, especially any $equalities$ I might have missed.
Note: Since $Q$ is a $2$-torsion point, we can use the negation formulae for $y$-coordinates $y_Q=-a_1x_Q-a_3-y_Q$ to replace $y_Q^2$ as an expression in $x_Q$. That's why that part isn't an issue for now.
algebraic-geometry elliptic-curves
asked Aug 1 at 13:28
Benedikt Höpers
161
The proof of Velu's formulae in Washington's "Elliptic Curves" uses two exercises (Ex. 12.6 and Ex.12.8). One part in Ex.12.6 is the following:
Let $E:y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6$ be an elliptic curve over a field $K$. Let $P,Q$ be two points on $E$. Let $x_P, x_Q, x_P+Q,y_P,y_Q$ denote the $x$- or $y$-coordinates of the points. Let $Q$ be a $2$-torsion point, so $2Q=infty$ and $Q=-Q$. The exercise claims the following equality holds:
$x_P+Q-x_Q=frac3x_Q^2+2a_2x_Q+a_4-a_1y_Qx_P-x_Q$
Since the cases $P=Q=-Q$ don't need examination, we assume $x_Pneq x_Q$ and we can use the addition formula as follows:
$x_P+Q=frac(y_P-y_Q)^2(x_P-x_Q)^2+a_1fracy_P-y_Qx_P-x_Q-a_2-x_P-x_Q$
So we need to show that:
$frac(y_P-y_Q)^2(x_P-x_Q)^2+a_1fracy_P-y_Qx_P-x_Q-a_2-x_P-x_Q-x_Q=frac3x_Q^2+2a_2x_Q+a_4-a_1y_Qx_P-x_Q$
After working on it for a while I noticed that I can't solve it due to the following dead end:
The LHS has a $y_P^2$ term while the RHS has not. After replacing $y_P^2$ using the equation of the curve the LHS has a $a_6$ term while the RHS has not. For all i know dividing those terms by $(x_P-x_Q)$ doesn't change anything. I'm thankful for any kind of information, especially any $equalities$ I might have missed.
Note: Since $Q$ is a $2$-torsion point, we can use the negation formulae for $y$-coordinates $y_Q=-a_1x_Q-a_3-y_Q$ to replace $y_Q^2$ as an expression in $x_Q$. That's why that part isn't an issue for now.
algebraic-geometry elliptic-curves
asked Aug 1 at 13:28
Benedikt Höpers
161
asked Aug 1 at 13:28
Benedikt Höpers
161
asked Aug 1 at 13:28
Benedikt Höpers
161
asked Aug 1 at 13:28
Benedikt Höpers
161
161
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
The equation of the elliptic curve is
$$y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6.tag1$$
I'll first prove the result, under the additional hypothesis that
$Q=(0,0)$. For $Q$ to lie on $E$, $a_6=0$. Then the tangent to
$E$ at $Q$ has the equation $a_3y+a_4x=0$. For $Q$ to be $2$-torsion,
this has to be vertical, so $a_3=0$ and $a_4ne0$. If $a_4$ were
zero $E$ must have a singularity at $Q$. Then $(1)$ becomes
$$y^2+a_1xy=x^3+a_2x^2+a_4xtag2$$
with $a_4ne0$.
Let $P$ be a point with $Pne O,Q$. The points $P$, $Q$ and $-P-Q$
are collinear. They are the three points of intersection of $E$
with a non-vertical
line through the origin. This line has the equation $y=tx$ for some $t$.
Inserting this in $(2)$ gives
$$x^3+(a_2-t^2-a_1t)x^2+a_4x=0.tag3$$
The three roots of $(3)$ are $x_P$, $x_Q=0$ and $x_-P-Q=x_P+Q$.
The product of the nonzero roots is $a_4$, that is $a_4=x_Px_P+Q$. Thus
$$x_P+Q=fraca_4x_P$$
which is the desired result in this case.
Returning to the general case, let $x'=x-x_Q$ and $y'=y-y_Q$. Then $(1)$ is equivalent to
$$y'^2+a'_1x'y'=x'^3+a'_2x'^2+a'_4x'tag4$$
for some $a_1'$, $a_2'$, $a_4'$. Then by the special case above
$$x_P+Q-x_Q=x'_P+Q=fraca_4'x'_P=fraca'_4x_P-x_Q.$$
But $a_4'$ is the coefficient of $x'$ after substituting $x'+x_Q$
and $y'=x'+y_Q$ in $(1)$. This is clearly
$$a_4'=3x_Q^2+2a_2x_Q+a_4-a_1y_Q.$$
That completes the proof in the general case.
answered Aug 2 at 10:23
Lord Shark the Unknown
84.2k950111
I was wondering whether this was the answer the author had in mind when writing down this exercise. Do you think that there is a 'more direct' approach than this one? I am curious!
– windsheaf
Aug 2 at 10:57
After writing this, I realised that most of it could be avoided by saying "without loss of generality assume that $Q=(0,0)$". Can you complete your argument under this assumption?
– Lord Shark the Unknown
Aug 2 at 10:59
@windsheaf I have now rewritten and simplified the argument. This now could be what Washington had in mind....
– Lord Shark the Unknown
Aug 3 at 7:45
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
The equation of the elliptic curve is
$$y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6.tag1$$
I'll first prove the result, under the additional hypothesis that
$Q=(0,0)$. For $Q$ to lie on $E$, $a_6=0$. Then the tangent to
$E$ at $Q$ has the equation $a_3y+a_4x=0$. For $Q$ to be $2$-torsion,
this has to be vertical, so $a_3=0$ and $a_4ne0$. If $a_4$ were
zero $E$ must have a singularity at $Q$. Then $(1)$ becomes
$$y^2+a_1xy=x^3+a_2x^2+a_4xtag2$$
with $a_4ne0$.
Let $P$ be a point with $Pne O,Q$. The points $P$, $Q$ and $-P-Q$
are collinear. They are the three points of intersection of $E$
with a non-vertical
line through the origin. This line has the equation $y=tx$ for some $t$.
Inserting this in $(2)$ gives
$$x^3+(a_2-t^2-a_1t)x^2+a_4x=0.tag3$$
The three roots of $(3)$ are $x_P$, $x_Q=0$ and $x_-P-Q=x_P+Q$.
The product of the nonzero roots is $a_4$, that is $a_4=x_Px_P+Q$. Thus
$$x_P+Q=fraca_4x_P$$
which is the desired result in this case.
Returning to the general case, let $x'=x-x_Q$ and $y'=y-y_Q$. Then $(1)$ is equivalent to
$$y'^2+a'_1x'y'=x'^3+a'_2x'^2+a'_4x'tag4$$
for some $a_1'$, $a_2'$, $a_4'$. Then by the special case above
$$x_P+Q-x_Q=x'_P+Q=fraca_4'x'_P=fraca'_4x_P-x_Q.$$
But $a_4'$ is the coefficient of $x'$ after substituting $x'+x_Q$
and $y'=x'+y_Q$ in $(1)$. This is clearly
$$a_4'=3x_Q^2+2a_2x_Q+a_4-a_1y_Q.$$
That completes the proof in the general case.
answered Aug 2 at 10:23
Lord Shark the Unknown
84.2k950111
I was wondering whether this was the answer the author had in mind when writing down this exercise. Do you think that there is a 'more direct' approach than this one? I am curious!
– windsheaf
Aug 2 at 10:57
After writing this, I realised that most of it could be avoided by saying "without loss of generality assume that $Q=(0,0)$". Can you complete your argument under this assumption?
– Lord Shark the Unknown
Aug 2 at 10:59
@windsheaf I have now rewritten and simplified the argument. This now could be what Washington had in mind....
– Lord Shark the Unknown
Aug 3 at 7:45
add a comment |Â
up vote
0
down vote
The equation of the elliptic curve is
$$y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6.tag1$$
I'll first prove the result, under the additional hypothesis that
$Q=(0,0)$. For $Q$ to lie on $E$, $a_6=0$. Then the tangent to
$E$ at $Q$ has the equation $a_3y+a_4x=0$. For $Q$ to be $2$-torsion,
this has to be vertical, so $a_3=0$ and $a_4ne0$. If $a_4$ were
zero $E$ must have a singularity at $Q$. Then $(1)$ becomes
$$y^2+a_1xy=x^3+a_2x^2+a_4xtag2$$
with $a_4ne0$.
Let $P$ be a point with $Pne O,Q$. The points $P$, $Q$ and $-P-Q$
are collinear. They are the three points of intersection of $E$
with a non-vertical
line through the origin. This line has the equation $y=tx$ for some $t$.
Inserting this in $(2)$ gives
$$x^3+(a_2-t^2-a_1t)x^2+a_4x=0.tag3$$
The three roots of $(3)$ are $x_P$, $x_Q=0$ and $x_-P-Q=x_P+Q$.
The product of the nonzero roots is $a_4$, that is $a_4=x_Px_P+Q$. Thus
$$x_P+Q=fraca_4x_P$$
which is the desired result in this case.
Returning to the general case, let $x'=x-x_Q$ and $y'=y-y_Q$. Then $(1)$ is equivalent to
$$y'^2+a'_1x'y'=x'^3+a'_2x'^2+a'_4x'tag4$$
for some $a_1'$, $a_2'$, $a_4'$. Then by the special case above
$$x_P+Q-x_Q=x'_P+Q=fraca_4'x'_P=fraca'_4x_P-x_Q.$$
But $a_4'$ is the coefficient of $x'$ after substituting $x'+x_Q$
and $y'=x'+y_Q$ in $(1)$. This is clearly
$$a_4'=3x_Q^2+2a_2x_Q+a_4-a_1y_Q.$$
That completes the proof in the general case.
answered Aug 2 at 10:23
Lord Shark the Unknown
84.2k950111
I was wondering whether this was the answer the author had in mind when writing down this exercise. Do you think that there is a 'more direct' approach than this one? I am curious!
– windsheaf
Aug 2 at 10:57
After writing this, I realised that most of it could be avoided by saying "without loss of generality assume that $Q=(0,0)$". Can you complete your argument under this assumption?
– Lord Shark the Unknown
Aug 2 at 10:59
@windsheaf I have now rewritten and simplified the argument. This now could be what Washington had in mind....
– Lord Shark the Unknown
Aug 3 at 7:45
add a comment |Â
up vote
0
down vote
up vote
0
down vote
The equation of the elliptic curve is
$$y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6.tag1$$
I'll first prove the result, under the additional hypothesis that
$Q=(0,0)$. For $Q$ to lie on $E$, $a_6=0$. Then the tangent to
$E$ at $Q$ has the equation $a_3y+a_4x=0$. For $Q$ to be $2$-torsion,
this has to be vertical, so $a_3=0$ and $a_4ne0$. If $a_4$ were
zero $E$ must have a singularity at $Q$. Then $(1)$ becomes
$$y^2+a_1xy=x^3+a_2x^2+a_4xtag2$$
with $a_4ne0$.
Let $P$ be a point with $Pne O,Q$. The points $P$, $Q$ and $-P-Q$
are collinear. They are the three points of intersection of $E$
with a non-vertical
line through the origin. This line has the equation $y=tx$ for some $t$.
Inserting this in $(2)$ gives
$$x^3+(a_2-t^2-a_1t)x^2+a_4x=0.tag3$$
The three roots of $(3)$ are $x_P$, $x_Q=0$ and $x_-P-Q=x_P+Q$.
The product of the nonzero roots is $a_4$, that is $a_4=x_Px_P+Q$. Thus
$$x_P+Q=fraca_4x_P$$
which is the desired result in this case.
Returning to the general case, let $x'=x-x_Q$ and $y'=y-y_Q$. Then $(1)$ is equivalent to
$$y'^2+a'_1x'y'=x'^3+a'_2x'^2+a'_4x'tag4$$
for some $a_1'$, $a_2'$, $a_4'$. Then by the special case above
$$x_P+Q-x_Q=x'_P+Q=fraca_4'x'_P=fraca'_4x_P-x_Q.$$
But $a_4'$ is the coefficient of $x'$ after substituting $x'+x_Q$
and $y'=x'+y_Q$ in $(1)$. This is clearly
$$a_4'=3x_Q^2+2a_2x_Q+a_4-a_1y_Q.$$
That completes the proof in the general case.
answered Aug 2 at 10:23
Lord Shark the Unknown
84.2k950111
The equation of the elliptic curve is
$$y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6.tag1$$
I'll first prove the result, under the additional hypothesis that
$Q=(0,0)$. For $Q$ to lie on $E$, $a_6=0$. Then the tangent to
$E$ at $Q$ has the equation $a_3y+a_4x=0$. For $Q$ to be $2$-torsion,
this has to be vertical, so $a_3=0$ and $a_4ne0$. If $a_4$ were
zero $E$ must have a singularity at $Q$. Then $(1)$ becomes
$$y^2+a_1xy=x^3+a_2x^2+a_4xtag2$$
with $a_4ne0$.
Let $P$ be a point with $Pne O,Q$. The points $P$, $Q$ and $-P-Q$
are collinear. They are the three points of intersection of $E$
with a non-vertical
line through the origin. This line has the equation $y=tx$ for some $t$.
Inserting this in $(2)$ gives
$$x^3+(a_2-t^2-a_1t)x^2+a_4x=0.tag3$$
The three roots of $(3)$ are $x_P$, $x_Q=0$ and $x_-P-Q=x_P+Q$.
The product of the nonzero roots is $a_4$, that is $a_4=x_Px_P+Q$. Thus
$$x_P+Q=fraca_4x_P$$
which is the desired result in this case.
Returning to the general case, let $x'=x-x_Q$ and $y'=y-y_Q$. Then $(1)$ is equivalent to
$$y'^2+a'_1x'y'=x'^3+a'_2x'^2+a'_4x'tag4$$
for some $a_1'$, $a_2'$, $a_4'$. Then by the special case above
$$x_P+Q-x_Q=x'_P+Q=fraca_4'x'_P=fraca'_4x_P-x_Q.$$
But $a_4'$ is the coefficient of $x'$ after substituting $x'+x_Q$
and $y'=x'+y_Q$ in $(1)$. This is clearly
$$a_4'=3x_Q^2+2a_2x_Q+a_4-a_1y_Q.$$
That completes the proof in the general case.
answered Aug 2 at 10:23
Lord Shark the Unknown
84.2k950111
edited Aug 3 at 10:18
answered Aug 2 at 10:23
Lord Shark the Unknown
84.2k950111
answered Aug 2 at 10:23
Lord Shark the Unknown
84.2k950111
answered Aug 2 at 10:23
Lord Shark the Unknown
84.2k950111
84.2k950111
I was wondering whether this was the answer the author had in mind when writing down this exercise. Do you think that there is a 'more direct' approach than this one? I am curious!
– windsheaf
Aug 2 at 10:57
After writing this, I realised that most of it could be avoided by saying "without loss of generality assume that $Q=(0,0)$". Can you complete your argument under this assumption?
– Lord Shark the Unknown
Aug 2 at 10:59
@windsheaf I have now rewritten and simplified the argument. This now could be what Washington had in mind....
– Lord Shark the Unknown
Aug 3 at 7:45
add a comment |Â
I was wondering whether this was the answer the author had in mind when writing down this exercise. Do you think that there is a 'more direct' approach than this one? I am curious!
– windsheaf
Aug 2 at 10:57
After writing this, I realised that most of it could be avoided by saying "without loss of generality assume that $Q=(0,0)$". Can you complete your argument under this assumption?
– Lord Shark the Unknown
Aug 2 at 10:59
@windsheaf I have now rewritten and simplified the argument. This now could be what Washington had in mind....
– Lord Shark the Unknown
Aug 3 at 7:45
I was wondering whether this was the answer the author had in mind when writing down this exercise. Do you think that there is a 'more direct' approach than this one? I am curious!
– windsheaf
Aug 2 at 10:57
I was wondering whether this was the answer the author had in mind when writing down this exercise. Do you think that there is a 'more direct' approach than this one? I am curious!
– windsheaf
Aug 2 at 10:57
After writing this, I realised that most of it could be avoided by saying "without loss of generality assume that $Q=(0,0)$". Can you complete your argument under this assumption?
– Lord Shark the Unknown
Aug 2 at 10:59
After writing this, I realised that most of it could be avoided by saying "without loss of generality assume that $Q=(0,0)$". Can you complete your argument under this assumption?
– Lord Shark the Unknown
Aug 2 at 10:59
@windsheaf I have now rewritten and simplified the argument. This now could be what Washington had in mind....
– Lord Shark the Unknown
Aug 3 at 7:45
@windsheaf I have now rewritten and simplified the argument. This now could be what Washington had in mind....
– Lord Shark the Unknown
Aug 3 at 7:45
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2869072%2fproof-of-velus-formulas-in-washingtons-elliptic-curves%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password