Elliptic curve addition: why does it work in any field?Elliptic curve point additionIntersection of a line with an Elliptic CurveProving that the differential on an elliptic curve $E$ given by $omega=fracdxy$ is translation invariantOrder of a point on an Elliptic CurveGroup law for an elliptic curve using schemesPoints on elliptic curve over finite fieldComputing number of points in elliptic curve through frobenius endomorphismWeierstrass form of elliptic curve with point with order larger than 3Elliptic Curves in CryptographyDerive Group Law on Elliptic Curve with Riemann Roch
Can I make popcorn with any corn?
declaring a variable twice in IIFE
What do you call a Matrix-like slowdown and camera movement effect?
least quadratic residue under GRH: an EXPLICIT bound
New order #4: World
Prevent a directory in /tmp from being deleted
What is the white spray-pattern residue inside these Falcon Heavy nozzles?
Is Social Media Science Fiction?
Can Medicine checks be used, with decent rolls, to completely mitigate the risk of death from ongoing damage?
How to make payment on the internet without leaving a money trail?
Concept of linear mappings are confusing me
Why is this code 6.5x slower with optimizations enabled?
Motorized valve interfering with button?
Could a US political party gain complete control over the government by removing checks & balances?
Why CLRS example on residual networks does not follows its formula?
What typically incentivizes a professor to change jobs to a lower ranking university?
Circuitry of TV splitters
Should I join an office cleaning event for free?
What Brexit solution does the DUP want?
If Manufacturer spice model and Datasheet give different values which should I use?
Download, install and reboot computer at night if needed
How do you conduct xenoanthropology after first contact?
"which" command doesn't work / path of Safari?
N.B. ligature in Latex
Elliptic curve addition: why does it work in any field?
Elliptic curve point additionIntersection of a line with an Elliptic CurveProving that the differential on an elliptic curve $E$ given by $omega=fracdxy$ is translation invariantOrder of a point on an Elliptic CurveGroup law for an elliptic curve using schemesPoints on elliptic curve over finite fieldComputing number of points in elliptic curve through frobenius endomorphismWeierstrass form of elliptic curve with point with order larger than 3Elliptic Curves in CryptographyDerive Group Law on Elliptic Curve with Riemann Roch
$begingroup$
Supposing I have an elliptic curve E(K): y^2 = x^3 + Ax + B with char(K) != 2,3,
why do the formulas for EC addition work in any field.
The formulas make sense in ℝ, for example we calculate the slope between the two points or if we add the same point, we calculate the tangent line with derivation of the EC formula.
But as soon as we move to a finite field, why should these formulas work? Why does e.g. the formula for the slope of the line between two points or a "tangent" (which lives in the "continuous" world) make sense?
Is there any literature that highlights this problem? My background is that of an undergraduate student, but I am willing to read more advanced books if it answers the question.
Thanks in advance!
group-theory arithmetic finite-fields elliptic-curves cryptography
asked Mar 22 at 10:32
NightRain23NightRain23
407
$endgroup$
add a comment |
$begingroup$
Supposing I have an elliptic curve E(K): y^2 = x^3 + Ax + B with char(K) != 2,3,
why do the formulas for EC addition work in any field.
The formulas make sense in ℝ, for example we calculate the slope between the two points or if we add the same point, we calculate the tangent line with derivation of the EC formula.
But as soon as we move to a finite field, why should these formulas work? Why does e.g. the formula for the slope of the line between two points or a "tangent" (which lives in the "continuous" world) make sense?
Is there any literature that highlights this problem? My background is that of an undergraduate student, but I am willing to read more advanced books if it answers the question.
Thanks in advance!
group-theory arithmetic finite-fields elliptic-curves cryptography
asked Mar 22 at 10:32
NightRain23NightRain23
407
$endgroup$
1
$begingroup$
Basically it is because if you plug in the equation of a line, $y=mx+b$, to the equation of the elliptic curve, you get a cubic equation in the unknown $x$. Furthermore, the coefficients will be in the field $K$ that contains $A,B,m,b$. If you picked the line through a pair of points on the curve (with coordinates in $K$), then you know two solutions for the $x$, and Vieta relations imply that the third is also in that same field. If your line is the tangent line, this implies that the $x$-coordinate of the point of tangency is a double root of that cubic, and the same argument goes thru.
$endgroup$
– Jyrki Lahtonen
Mar 22 at 10:46
1
$begingroup$
Basically tangent line to the curve at the point $(x_0,y_0)$ can be replaced with the purely algebraic the unique line $y=mx+b$ such that the equation $(mx+b)^2=x^3+Ax+b$ has a double root at $x=x_0$.
$endgroup$
– Jyrki Lahtonen
Mar 22 at 10:47
1
$begingroup$
@JyrkiLahtonen That looks like it really should've been an answer post.
$endgroup$
– Arthur
Mar 22 at 10:58
add a comment |
$begingroup$
Supposing I have an elliptic curve E(K): y^2 = x^3 + Ax + B with char(K) != 2,3,
why do the formulas for EC addition work in any field.
The formulas make sense in ℝ, for example we calculate the slope between the two points or if we add the same point, we calculate the tangent line with derivation of the EC formula.
But as soon as we move to a finite field, why should these formulas work? Why does e.g. the formula for the slope of the line between two points or a "tangent" (which lives in the "continuous" world) make sense?
Is there any literature that highlights this problem? My background is that of an undergraduate student, but I am willing to read more advanced books if it answers the question.
Thanks in advance!
group-theory arithmetic finite-fields elliptic-curves cryptography
asked Mar 22 at 10:32
NightRain23NightRain23
407
$endgroup$
Supposing I have an elliptic curve E(K): y^2 = x^3 + Ax + B with char(K) != 2,3,
why do the formulas for EC addition work in any field.
The formulas make sense in ℝ, for example we calculate the slope between the two points or if we add the same point, we calculate the tangent line with derivation of the EC formula.
But as soon as we move to a finite field, why should these formulas work? Why does e.g. the formula for the slope of the line between two points or a "tangent" (which lives in the "continuous" world) make sense?
Is there any literature that highlights this problem? My background is that of an undergraduate student, but I am willing to read more advanced books if it answers the question.
Thanks in advance!
group-theory arithmetic finite-fields elliptic-curves cryptography
group-theory arithmetic finite-fields elliptic-curves cryptography
asked Mar 22 at 10:32
NightRain23NightRain23
407
asked Mar 22 at 10:32
NightRain23NightRain23
407
asked Mar 22 at 10:32
NightRain23NightRain23
407
asked Mar 22 at 10:32
NightRain23NightRain23
407
asked Mar 22 at 10:32
NightRain23NightRain23
407
407
1
$begingroup$
Basically it is because if you plug in the equation of a line, $y=mx+b$, to the equation of the elliptic curve, you get a cubic equation in the unknown $x$. Furthermore, the coefficients will be in the field $K$ that contains $A,B,m,b$. If you picked the line through a pair of points on the curve (with coordinates in $K$), then you know two solutions for the $x$, and Vieta relations imply that the third is also in that same field. If your line is the tangent line, this implies that the $x$-coordinate of the point of tangency is a double root of that cubic, and the same argument goes thru.
$endgroup$
– Jyrki Lahtonen
Mar 22 at 10:46
1
$begingroup$
Basically tangent line to the curve at the point $(x_0,y_0)$ can be replaced with the purely algebraic the unique line $y=mx+b$ such that the equation $(mx+b)^2=x^3+Ax+b$ has a double root at $x=x_0$.
$endgroup$
– Jyrki Lahtonen
Mar 22 at 10:47
1
$begingroup$
@JyrkiLahtonen That looks like it really should've been an answer post.
$endgroup$
– Arthur
Mar 22 at 10:58
add a comment |
1
$begingroup$
Basically it is because if you plug in the equation of a line, $y=mx+b$, to the equation of the elliptic curve, you get a cubic equation in the unknown $x$. Furthermore, the coefficients will be in the field $K$ that contains $A,B,m,b$. If you picked the line through a pair of points on the curve (with coordinates in $K$), then you know two solutions for the $x$, and Vieta relations imply that the third is also in that same field. If your line is the tangent line, this implies that the $x$-coordinate of the point of tangency is a double root of that cubic, and the same argument goes thru.
$endgroup$
– Jyrki Lahtonen
Mar 22 at 10:46
1
$begingroup$
Basically tangent line to the curve at the point $(x_0,y_0)$ can be replaced with the purely algebraic the unique line $y=mx+b$ such that the equation $(mx+b)^2=x^3+Ax+b$ has a double root at $x=x_0$.
$endgroup$
– Jyrki Lahtonen
Mar 22 at 10:47
1
$begingroup$
@JyrkiLahtonen That looks like it really should've been an answer post.
$endgroup$
– Arthur
Mar 22 at 10:58
1
1
$begingroup$
Basically it is because if you plug in the equation of a line, $y=mx+b$, to the equation of the elliptic curve, you get a cubic equation in the unknown $x$. Furthermore, the coefficients will be in the field $K$ that contains $A,B,m,b$. If you picked the line through a pair of points on the curve (with coordinates in $K$), then you know two solutions for the $x$, and Vieta relations imply that the third is also in that same field. If your line is the tangent line, this implies that the $x$-coordinate of the point of tangency is a double root of that cubic, and the same argument goes thru.
$endgroup$
– Jyrki Lahtonen
Mar 22 at 10:46
$begingroup$
Basically it is because if you plug in the equation of a line, $y=mx+b$, to the equation of the elliptic curve, you get a cubic equation in the unknown $x$. Furthermore, the coefficients will be in the field $K$ that contains $A,B,m,b$. If you picked the line through a pair of points on the curve (with coordinates in $K$), then you know two solutions for the $x$, and Vieta relations imply that the third is also in that same field. If your line is the tangent line, this implies that the $x$-coordinate of the point of tangency is a double root of that cubic, and the same argument goes thru.
$endgroup$
– Jyrki Lahtonen
Mar 22 at 10:46
1
1
$begingroup$
Basically tangent line to the curve at the point $(x_0,y_0)$ can be replaced with the purely algebraic the unique line $y=mx+b$ such that the equation $(mx+b)^2=x^3+Ax+b$ has a double root at $x=x_0$.
$endgroup$
– Jyrki Lahtonen
Mar 22 at 10:47
$begingroup$
Basically tangent line to the curve at the point $(x_0,y_0)$ can be replaced with the purely algebraic the unique line $y=mx+b$ such that the equation $(mx+b)^2=x^3+Ax+b$ has a double root at $x=x_0$.
$endgroup$
– Jyrki Lahtonen
Mar 22 at 10:47
1
1
$begingroup$
@JyrkiLahtonen That looks like it really should've been an answer post.
$endgroup$
– Arthur
Mar 22 at 10:58
$begingroup$
@JyrkiLahtonen That looks like it really should've been an answer post.
$endgroup$
– Arthur
Mar 22 at 10:58
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
When going from continuous fields ($Bbb R$ and $Bbb C$, and to a lesser extent $Bbb Q$) to something like a finite field, you are right that the geometric intuition fails. However, nothing is stopping the algebra from working exactly as before (or, at least, almost exactly like before; as you pointed out, characteristic 2 and 3 mess with things when working with quadratic and cubic polynomials).
Say we have a finite field $K$. Then the line between $(a, b)$ and $(c, d)$ in $K^2$ is simply the set of $(x, y)in K^2$ which satisfy a linear equation
$$
mx + ny + k = 0
$$
where $m, n, k$ are chosen so that the equation is satisfied for $(a, b)$ and $(c, d)$ (if the two points are distinct, then there is exactly one viable choice of $m, n, k$ up to scaling).
A tangent is a bit more tricky, but as we know from the continuous case, a line $mx + ny + k = 0$ which has a point $(a, b)$ in common with $E$ is tangent with $E$ at that point if the intersection at $(a, b)$ has degree greater than $0$. And the degree of the intersection can be found purely algebraically, for instance by looking at $K[x, y]/(mx+ny + k)cong K[z]$ and considering whether $x^3 + Ax + B - y^2$ has a multiple root at $(a, b)$.
So the moral of the story is that even though the geometric interpretation doesn't make as much sense, we keep the geometric terms and define them algebraically instead, and much of the intuitive results from the continuous case carry right over to the discrete case.
answered Mar 22 at 10:40
ArthurArthur
122k7122211
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3157986%2felliptic-curve-addition-why-does-it-work-in-any-field%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
When going from continuous fields ($Bbb R$ and $Bbb C$, and to a lesser extent $Bbb Q$) to something like a finite field, you are right that the geometric intuition fails. However, nothing is stopping the algebra from working exactly as before (or, at least, almost exactly like before; as you pointed out, characteristic 2 and 3 mess with things when working with quadratic and cubic polynomials).
Say we have a finite field $K$. Then the line between $(a, b)$ and $(c, d)$ in $K^2$ is simply the set of $(x, y)in K^2$ which satisfy a linear equation
$$
mx + ny + k = 0
$$
where $m, n, k$ are chosen so that the equation is satisfied for $(a, b)$ and $(c, d)$ (if the two points are distinct, then there is exactly one viable choice of $m, n, k$ up to scaling).
A tangent is a bit more tricky, but as we know from the continuous case, a line $mx + ny + k = 0$ which has a point $(a, b)$ in common with $E$ is tangent with $E$ at that point if the intersection at $(a, b)$ has degree greater than $0$. And the degree of the intersection can be found purely algebraically, for instance by looking at $K[x, y]/(mx+ny + k)cong K[z]$ and considering whether $x^3 + Ax + B - y^2$ has a multiple root at $(a, b)$.
So the moral of the story is that even though the geometric interpretation doesn't make as much sense, we keep the geometric terms and define them algebraically instead, and much of the intuitive results from the continuous case carry right over to the discrete case.
answered Mar 22 at 10:40
ArthurArthur
122k7122211
$endgroup$
add a comment |
$begingroup$
When going from continuous fields ($Bbb R$ and $Bbb C$, and to a lesser extent $Bbb Q$) to something like a finite field, you are right that the geometric intuition fails. However, nothing is stopping the algebra from working exactly as before (or, at least, almost exactly like before; as you pointed out, characteristic 2 and 3 mess with things when working with quadratic and cubic polynomials).
Say we have a finite field $K$. Then the line between $(a, b)$ and $(c, d)$ in $K^2$ is simply the set of $(x, y)in K^2$ which satisfy a linear equation
$$
mx + ny + k = 0
$$
where $m, n, k$ are chosen so that the equation is satisfied for $(a, b)$ and $(c, d)$ (if the two points are distinct, then there is exactly one viable choice of $m, n, k$ up to scaling).
A tangent is a bit more tricky, but as we know from the continuous case, a line $mx + ny + k = 0$ which has a point $(a, b)$ in common with $E$ is tangent with $E$ at that point if the intersection at $(a, b)$ has degree greater than $0$. And the degree of the intersection can be found purely algebraically, for instance by looking at $K[x, y]/(mx+ny + k)cong K[z]$ and considering whether $x^3 + Ax + B - y^2$ has a multiple root at $(a, b)$.
So the moral of the story is that even though the geometric interpretation doesn't make as much sense, we keep the geometric terms and define them algebraically instead, and much of the intuitive results from the continuous case carry right over to the discrete case.
answered Mar 22 at 10:40
ArthurArthur
122k7122211
$endgroup$
add a comment |
$begingroup$
When going from continuous fields ($Bbb R$ and $Bbb C$, and to a lesser extent $Bbb Q$) to something like a finite field, you are right that the geometric intuition fails. However, nothing is stopping the algebra from working exactly as before (or, at least, almost exactly like before; as you pointed out, characteristic 2 and 3 mess with things when working with quadratic and cubic polynomials).
Say we have a finite field $K$. Then the line between $(a, b)$ and $(c, d)$ in $K^2$ is simply the set of $(x, y)in K^2$ which satisfy a linear equation
$$
mx + ny + k = 0
$$
where $m, n, k$ are chosen so that the equation is satisfied for $(a, b)$ and $(c, d)$ (if the two points are distinct, then there is exactly one viable choice of $m, n, k$ up to scaling).
A tangent is a bit more tricky, but as we know from the continuous case, a line $mx + ny + k = 0$ which has a point $(a, b)$ in common with $E$ is tangent with $E$ at that point if the intersection at $(a, b)$ has degree greater than $0$. And the degree of the intersection can be found purely algebraically, for instance by looking at $K[x, y]/(mx+ny + k)cong K[z]$ and considering whether $x^3 + Ax + B - y^2$ has a multiple root at $(a, b)$.
So the moral of the story is that even though the geometric interpretation doesn't make as much sense, we keep the geometric terms and define them algebraically instead, and much of the intuitive results from the continuous case carry right over to the discrete case.
answered Mar 22 at 10:40
ArthurArthur
122k7122211
$endgroup$
When going from continuous fields ($Bbb R$ and $Bbb C$, and to a lesser extent $Bbb Q$) to something like a finite field, you are right that the geometric intuition fails. However, nothing is stopping the algebra from working exactly as before (or, at least, almost exactly like before; as you pointed out, characteristic 2 and 3 mess with things when working with quadratic and cubic polynomials).
Say we have a finite field $K$. Then the line between $(a, b)$ and $(c, d)$ in $K^2$ is simply the set of $(x, y)in K^2$ which satisfy a linear equation
$$
mx + ny + k = 0
$$
where $m, n, k$ are chosen so that the equation is satisfied for $(a, b)$ and $(c, d)$ (if the two points are distinct, then there is exactly one viable choice of $m, n, k$ up to scaling).
A tangent is a bit more tricky, but as we know from the continuous case, a line $mx + ny + k = 0$ which has a point $(a, b)$ in common with $E$ is tangent with $E$ at that point if the intersection at $(a, b)$ has degree greater than $0$. And the degree of the intersection can be found purely algebraically, for instance by looking at $K[x, y]/(mx+ny + k)cong K[z]$ and considering whether $x^3 + Ax + B - y^2$ has a multiple root at $(a, b)$.
So the moral of the story is that even though the geometric interpretation doesn't make as much sense, we keep the geometric terms and define them algebraically instead, and much of the intuitive results from the continuous case carry right over to the discrete case.
answered Mar 22 at 10:40
ArthurArthur
122k7122211
edited Mar 22 at 11:41
answered Mar 22 at 10:40
ArthurArthur
122k7122211
answered Mar 22 at 10:40
ArthurArthur
122k7122211
answered Mar 22 at 10:40
ArthurArthur
122k7122211
122k7122211
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3157986%2felliptic-curve-addition-why-does-it-work-in-any-field%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
Basically it is because if you plug in the equation of a line, $y=mx+b$, to the equation of the elliptic curve, you get a cubic equation in the unknown $x$. Furthermore, the coefficients will be in the field $K$ that contains $A,B,m,b$. If you picked the line through a pair of points on the curve (with coordinates in $K$), then you know two solutions for the $x$, and Vieta relations imply that the third is also in that same field. If your line is the tangent line, this implies that the $x$-coordinate of the point of tangency is a double root of that cubic, and the same argument goes thru.
$endgroup$
– Jyrki Lahtonen
Mar 22 at 10:46
1
$begingroup$
Basically tangent line to the curve at the point $(x_0,y_0)$ can be replaced with the purely algebraic the unique line $y=mx+b$ such that the equation $(mx+b)^2=x^3+Ax+b$ has a double root at $x=x_0$.
$endgroup$
– Jyrki Lahtonen
Mar 22 at 10:47
1
$begingroup$
@JyrkiLahtonen That looks like it really should've been an answer post.
$endgroup$
– Arthur
Mar 22 at 10:58