1

I've been reading about the elliptic curve used for key generation in bitcoin ie y^2 = x^3 + 7 (mod p) [I'm not sure how to do the congruence symbol]

To help me visualise whats going on I wrote a script to plot the values of y * y - (x * x * x + 7) (mod p) as colours (black = 0).

This is the result where p = 5

mod 5

The plot is NOT symmetrical about y=p/2 but when I mark the integer values of x and y (the red dots) which yield a zero solution the result IS symmetrical (for all values of p)

Is there a neat mathematical reason for this?

Derek
  • 113

1 Answers1

1

First view the curve over $ℝ$. The equation $$E: Y^2 = X^3 + 7$$ has solutions clearly symmetrical about the horizontal axis $Y = 0$ because any real point $(x,y)$ solves the equation if and only if $(x,-y)$ does.

The very same is happening modulo $n$ for any integer $n$. The difference is that modulo $n$, you have $-y \equiv n-y$ for all integers $y$, which gives you another axis of symmetry. For every integer point $(x,y)$ and modulo $n$ $$(x,y) ∈ E ⇔ (x,-y) ∈ E ⇔ (x,n-y) ∈ E.$$

This now looks like a symmetry about the line $Y = \dfrac n 2$.

For example, for $n = 5$, you get the symmetries \begin{align*}(3,2) ∈ E ⇔ (3,-2) ∈ E ⇔ (3,3) ∈ E,\\ (4,1) ∈ E ⇔ (4,-1) ∈ E ⇔ (4,4) ∈ E. \end{align*}

k.stm
  • 18,539
  • Aha! That makes sense. I was confused as to why the same logic wouldn't apply to other values of x,y in R (I expected the whole plot to be symmetrical about y=n/2) but of course the symmetry only applies to integer values (because the modulus is an integer) of x,y that satisfy the elliptic equation (the zeroes of my plot). It's an odd result when you look at the plot but I understand it now. Thanks. – Derek Jan 26 '19 at 10:00