[curves] Introduction to ECC

[Dominik Pantůček]

Hi Brad and others,

I finally subscribed to the curves list (as Jan has suggested for a long
time) and I think I can give you some insight into GF(p) visualizations
and the behaviour or most (if not all) elliptic curves over finite fields.
>
> Hi Jan and Curve Fans,
>
> After more thought, there is one other nagging issue. Nice quality
> aside, I'm not sure that the torus video [1] leads in the right
> direction.
>
> When dealing with modulus arithmetic, it seems extremely unlikely to
> me that one particular curve will visit all valid points. In a field
> such as GF(23), we could typically expect to see a range of curves
> C(x,y)=23*n for different integer n, as depicted elsewhere [2]. By
> wrapping the curve around the torus, your animation seems to say that
> any particular solution, C(x1,y1)=23*n1, can be lattice-translated to
> C(x1+23*j1,y1+23*k1)=0. The zero-constraint is a Diophantine equation
> in (j1,k1). I'm not sure if or how you can guarantee a translation
> (j,k) exists for every valid triple (x,y,n)?? Isn't this a needlessly
> difficult question to answer when you can just plot a range of curves
> over one square domain?
Short reply: you are wrong here.

Medium-sized reply: Needlessly difficult question is finding the set of
right coefficients j1,k1.

Long reply would probably go along the following lines:

Consider an elliptic curve E over the set of real numbers R. That is a
set of points satisfying the equation f(x,y)=0 where f(x,y) represents
the EC equation with all terms on the left side and remaining zero on
the right side.

For simple Weierstrass form that means: f(x,y)=y^2-x^3-ax-b

Now if we consider the same elliptic curve over a prime finite field
GF(p), we get f(x,y)\equiv 0\mod p

(I assume, you are used to TeX notation here - if not, I can produce a
short PDF with everything).

This can be translated to f(x,y)\mod p=0\mod p

As 0\mod p=0, we can simplify it as f(x,y)\mod p=0 (someone might
consider this inaccurate notation, but treating integer division
remainder as operation is more intuitive)

Now, you are absolutely right that f(x+mp,y+np)\mod p=0; x,y\in N+{0};
m,n\in Z is the set of curves containing the solutions which - if
plotted with x,y\in R\and x,y\in<0,p) -- cross the rational points of GF(p).

This is the crucial part - only for some coefficients m,n\in N+{0} you
cross the rational points of GF(p) projected over R.

The visualization of GF(p) on torus contains all m,n\in Z -  beware, for
some functions you get periodic repetitions: for example in my latest
article (which Jan had already posted here) you can see f(x): y=ax+b;
that is - a straight line. And of course it becomes closed over the
torus representing GF(p) (and in this case it hits exactly p number of
points of given GF(p)).

So yes, any particular curve f(x,y)=0 where x,y\in R plotted over GF(p)
region of the real plane will always cross all the rational points of
the same curve f(x,y)\equiv 0\mod p - that is over GF(p).

Yes, certain repetitions (actually infinitely many of them) cross no
rational point at all! That is fine. The field contains only a finite
number of elements and the curve over R is infinite.
>
> Perhaps the critique is overly technical. Even on a qualitative level,
> the animation is likely to introduce cognitive dissonance. Your torus
> domain goes along two real variables. For doubly-periodic elliptic
> functions, the domain covers a portion of the complex plane. Granted,
> computer science applications do not really depend on integrals or
> differential equations. However, an effort to find the best possible
> depictions of elliptic curves should really be interdisciplinary, with
> ideas and input from all around.
Firstly, the critique is (again) welcome. And secondly... if I read the
rest correctly, you are dealing with ECs over C^2, that is technically
over quaternians... which means your work starts in 4D. As of now I have
no idea how to start thinking about creating decent visualizations of
such. I am really looking forward seeing anything done in that matter.

My interest (for now) lies in ECs over R and GF(p) with emphasis of
creating visualizations and animations of all operations on simple
Weierstrass form, Montgomery form and (yes) Twisted Edwards. The last
one would be really tough on the torus, as you need to project a
hyperbole there.
>
> I will mention again that I have yet to see any convincing pictures or
> animations of elliptic curves, which emphasize realizations as genus
> one surfaces. However, in recent exploration of complex transformation
> between families of elliptic curves, I've invented another decent
> depiction algorithm [3,4]. Quality is not too bad, though yes, rushed.
> At least the drawings have nothing to do with any particular normal form!
It does not look bad for a start. How do you specify the curves and how
do you plot them? For anything smooth I ended up with a naive algorithm
that can plot anything in the form f(x,y)=0 over R and then I just use
coordinate transformations to get the desired pictures.


Cheers,

Dominik

>
> Again, I'm not an expert, so corrections are welcome if I happen to be
> in error.
>
> Cheers,
>
> Brad
>
> after: https://moderncrypto.org/mail-archive/curves/2018/000975.html
> [1] https://www.youtube.com/watch?v=mFVKuFZ29Fc
> [2] https://ptpb.pw/1WvB.png
> [3] https://www.youtube.com/watch?v=X5hkRIk81_Q
> [4] https://www.youtube.com/watch?v=zxQSB8OrlZg
>
>