ECC introduction: point addition on simple Weierstrass form

[Dominik Pantůček]

Hello curves fans,

another article in my introductory series about elliptic curves used in
cryptography is out[1]. This time it is about point addition on elliptic
curve in simple Weierstrass form over R and GF(p). For those following
my discussion with Brad earlier, you can see the graphical
representation of infinite straight line over GF(p) torus in the
video[2] - around 0:45 it becomes closed. I would appreciate any
feedback regarding the article format, visualizations or anything else -
just, please, bear in mind that the intended audience are real beginners
and therefore I have omitted some things and want to explain them in the
future separately.


Cheers,

Dominik

[1] https://trustica.cz/en/2018/03/15/elliptic-curves-point-addition/

[2]

[Dominik Pantůček]

Hello everyone again,

I hope this does not bother anyone, but I'd like to present you next
article[1] in my introductory series about ECC. This time about point
doubling. For those following my earlier discussion with Brad, you
should find the explanation how the rational points over given finite
field form - more specifically, from which complete set of curves are
they actually produced. The general idea is for any EC in simple
Weierstrass form satisfying y^2=x^3+ax+b we define a function
f(x,y)=y^2-x^3-ax-b and the original curve is then specified as
f(x,y)=0. The infinite set of all curves from which some cross the
rational points of given finite field GF(p) is then given by the
equation f(x+mp,y+np)+kp=0 \forall m,n,k\in Z

The visualization[2] may look messy or you may see it immediately - the
torus rotation timing was set in sync with showing the basic f(x,y)=0
variant when the origin [0,0] is facing the viewer.

As always, I'd love to hear any feedback regarding the visualizations or
the writing style. My longer-term goal is to finish simple Weierstrass
form and continue with isogeny to Montgomery form and showing the same
operations on Montgomery form - ideally both over R and GF(p) and also
in X:Z coordinates. But that is still some way to go...


Cheers,
Dominik

[1] https://trustica.cz/en/2018/03/22/elliptic-curves-point-doubling/
[2]

[Dominik Pantůček]

(This is actually a re-post, I accidentally addressed Brad only, sorry
for that).

Hi Brad and others,

Hi Dominik,
Some of these graphs are looking cool, but I'm not sure why your
worried about integers (m,n). If you include (m,n) then every point
will actually intersect infinitely many curves. The slopes of these
curves at the point of intersection are different per curve, but
reduce to one particular line over a finite field. So (m,n) could
really be considered extraneous, and parameter k quite sufficient.

you have to include at least m\in{-1,0}, n\in{-1,0} - you can see this
in[1] (I didn't want to draw my own, so I am reusing yours here).

Another thing to think about is intersection geometries combining
elliptic curves with a non-linear addition curve. For example, Edwards
curves have a hyperbolic addition rule. In this case the quadratic
hyperbolas are more similar to cubic elliptic curves than to lines.
They don't wrap the torus nicely, again require a big set to account
for all intersections.
Drawings of linear intersections over finite fields are now becoming
standard fare. We have seen continuous interpretation of hyperbolic
intersection in a number of references. I have yet to see hyperbolic
intersection over finite field, so perhaps this would be an
interesting direction to go in terms of depiction?

Now you have unveiled my secret long-term plan. Yes, I want to slowly go
through all the basics using simple Weierstrass form, then continue with
Montgomery form and finally show the hyperbolic intersections of twisted
Edwards over finite field (there are few things to be solved in that
case, but I am looking forward those challenges :) ).

Speaking of slowly going through all the basics, I produced another
article[2] and accompanying video[3] - this time about point at
infinity. Truth is, I am not satisfied with this one and I am thinking
about creating another one showing the actual intersections at point at
infinity on the projective plane.


Cheers,
Dominik

[1] Loading Image...
[2] https://trustica.cz/en/2018/03/29/elliptic-curves-point-at-infinity/
[3]

[Dominik Pantůček]

Hi curves fans,

Post by Dominik Pantůček
Speaking of slowly going through all the basics, I produced another
article[2] and accompanying video[3] - this time about point at
infinity. Truth is, I am not satisfied with this one and I am thinking
about creating another one showing the actual intersections at point at
infinity on the projective plane.

I have put some more thought in explaining the point at infinity in the
projective plane and created a visualization using stereographic
projection onto a sphere[1]. The accompanying article[2] wouldn't
probably be of much interest here, but I am referencing it for the sake
of completeness. I would really appreciate any feedback as I am trying
to finalize the visualization framework (not there yet, but it is way
more polished than two months ago when I dug it out of git repository
after not touching it for about a year).

Cheers,
Dominik

[1]

[2]
https://trustica.cz/en/2018/04/05/elliptic-curves-point-at-infinity-revisited/