Wikipedia:Reference desk/Archives/Mathematics/2015 January 10

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 10

Explain this plot used in ECC

On the Ars Technica page explaining elliptic curve cryptography, they presented this image of the curve $y^{2}=x^{3}-x+1$. What exactly is it? They failed to satisfactorily explain it. — Melab±1 ☎ 17:27, 10 January 2015 (UTC)

It would help if you gave a link to the page to which you refer, not only the image. The diagram appears to depict the solutions to equation where the variables are from a finite field, which is generally the case for ECC. —Quondum 18:39, 10 January 2015 (UTC)

That is what it is. Here is the page in question. They said it involved wrapping the curve around the edges or something, but I don't understand what that means. Are each of those points resting on <math>&xi;</math> that have been remainder divided? — Melab±1 ☎ 06:40, 11 January 2015 (UTC)

That <math> expression was a syntax error. I've edited it to display as Melab's source form, not being sure what Melab intended to be saying. --65.94.50.4 (talk) 06:58, 11 January 2015 (UTC)

Expanding on Quondum's answer, the plot represents the solutions to $y^{2}=x^{3}-x+1$ in the field of integers module 97. At the far left of the diagram are the points with coordinates (0,1) and (0,96) because 0^3-0+1 = 1 and the square roots of 1 module 97 are 1 and 96 (you can also think of these as 1 and -1 modulo 97). Then we have (1,1) and (1,96) because 1^3-1+1 = 1. Then there is a gap because 2^3-2+1 = 7 and there is no solution to y^2 = 7 modulo 97. Then we have (3,5) and (3,92) because 3^3-3+1 = 25 and 5^2 = 25 modulo 97, and also 92^2 = 25 modulo 97 because 92 = -5 modulo 97. Then we have (4,35) and (4,62) because 4^3-4+1 = 61 and 35^2 = 61 modulo 97, and also 62^2 = 61 modulo 97. Then we have (5,11) and (5,86), then a long gap, followed by (17,12) and (17,85) etc. Gandalf61 (talk) 11:48, 11 January 2015 (UTC)

I can see the article being confusing: "we restrict ourselves to whole numbers in a fixed range" and "It's like, in our bizarro billiards game, when a ball hits the edge of the board (the max) and then is magically transported to the opposite side of the table and continues on its path until reaching a point, kind of like the game Snake." They do not seem to explicitly mention modular arithmetic or its rules, recognizable to anyone familiar with it, but others may still be confused. A simpler way of describing it might have been: take only the points on the curve for which x and y are integers, so that we have dots. Then slice of up plane into squares (of width 97) and stack these. We end of with all the dots from all the strips as in the picture, rather random-looking, bit still preserving certain properties, in particular being the solutions the same equation under modular arithmetic, and at most three dots on any line. Each of the dots is made up of an infinite number of the original dots stacked together. —Quondum 17:56, 11 January 2015 (UTC)

So if I wanted to find the points for $y^{2}=x^{3}+5x+1$ over the field for 31, then I would have to take every integer from 0 to 30, substitute them in for $x$, and then the corresponding y coordinates would be whatever number makes $y^{2}\%31$ equal to $(x^{3}+5x+1)\%31$, correct? — Melab±1 ☎ 21:58, 11 January 2015 (UTC)

Correct. Keep in mind that for some x there may be no solution, and aside from y = 0, there is always a second solution y = −y (mod 31) if there is one solution (except for a field of characteristic 2). —Quondum 22:33, 11 January 2015 (UTC)