I'm trying to learn about ECC. I understand that the points of the finite field are determined by taking the continuous elliptic curve and finding its points that have integer coordinates. Since ECC uses modular arithmetic, the points of the finite field are on an integer grid that extends from 0 to the modulus-1 in both x and y. The points of the field are determined by "wrapping" the continuous curve when it reaches the edge of this grid. Here's where I'm confused. Since the continuous curve is over all real numbers, it extends infinitely in both dimensions. When it's wrapped onto the finite integer grid, it seems that it would cover the entire grid and intersect every point on the grid, so every possible point would be in the finite field. Why isn't this true?
-
1$\begingroup$ An elliptic curve over a finite field is not really a curve - this is what it looks like - eng.paxos.com/hubfs/_02_Paxos_Engineering/… - May be this will help you understand it better. All the dots are points of the EC. $\endgroup$– user93353Sep 16, 2021 at 7:42
-
$\begingroup$ en.wikipedia.org/wiki/Nagell%E2%80%93Lutz_theorem $\endgroup$– kelalakaSep 16, 2021 at 14:06
-
$\begingroup$ And ECC on Rationals vs Finite field with illustrations. $\endgroup$– kelalakaSep 16, 2021 at 14:12
1 Answer
First of all your description is not quite right. There are usually very few points on an elliptic curve which have integer coordinates. The points where the curve equation is satisfied modulo some number typically do not correspond to a point on the continuous curve with integer coordinates.
On the wider point of curve wrapping, think of wrapping a piece of string around a parcel of some shape. At some point the string will start following its original path and if that occurs before all of the surface is covered, then some of the surface will always be uncovered.
For example, consider the simpler curve $y=x^3$ which as a continuous curve covers all of the real numbers for both $x$ and $y$. Now look at the pattern of cube number modulo 19; it goes 0, 1, 8, 8, 7, 11, 7, 1, 18, 7, 12, 1, 18, 12, 8, 12, 11, 11, 18, 0, 1, 8, 8, 7, 11, 7, 1... and so on repeating. The numbers wrap around and start again after 19 steps and so the $y$ values 2, 3, 4, 5, 6, 9, 10, 13, 14, 15, 16, 17 are never hit.
-
1$\begingroup$ There is a way to map the points of an Elliptic Curve group to points on the continuous curve of same equation, with the continuous geometrical construction matching the group law. I've explored that there, with illustration for a group of order $10$. But it turns out to be worse than useless in explaining ECC crypto, and I could not find any use for cryptanalysis or implementation. So I mention this just to make the web yet more inscrutably linked. $\endgroup$– fgrieu ♦Sep 16, 2021 at 10:12
-
$\begingroup$ Thank you, Daniel S! Your third paragraph demonstrates the flaw in my thinking. $\endgroup$ Sep 17, 2021 at 1:13