1

Can someone help me:

1) to list the points on the elliptic curve $E: y^2\equiv x^3 – 2\pmod 7$.

2) to find the sum $(3, 2) + (5, 5) $ on $E$.

Alex M.
  • 35,207
Niyaz Iralin
  • 19

1 Answers1

1

For the first part, you compute the quadratic residues $\pmod 7$ : $$0,1,4,3^2 \equiv 2,4^2 \equiv 2,5^2 \equiv 4, 6^2 \equiv 1.\tag{A}$$

By simple calculations (by hand), you know that $x^3-2$ is not a quadratic residue for $x=0,1,2,4$. Then you have 7 points on $E$ :

$$(3,2) \quad;\quad (3,5) \quad;\quad (5,2) \quad;\quad (5,5) \quad;\quad (6,2) \quad;\quad (6,5) \quad;\quad \infty\tag{B}$$

For the second part, first compute the slope $$m = \dfrac{5 - 2}{5-3} = 3 \cdot 2^{-1} \equiv 3\cdot4 \equiv \color{purple}5 \pmod 7 \tag{C}$$ Then the sum of the 2 points (that lie on $E$) is

$$(\color{orange}3,\color{blue}2)+(\color{green}5,5) = (x = \color{purple}5^2 - \color{orange}3 - \color{green}5, y = \color{purple}5 \cdot (\color{orange}3-x) - \color{blue}2) \equiv (3,5\cdot0 -2) \equiv (3,5)\tag{D}$$

Watson
  • 23,793
  • Could you explain the first part in details? I didn't get it. – Niyaz Iralin Jan 18 '16 at 00:44
  • 1
    If $(x,y)$ lies on $E$, then $x^3-2=y^2$ is a square in $\mathbb F_7$. The squares are $0,1,2,4$ as I showed in the first part. Then you just have to compute $f(x):=x^3-2$ for $x \in {0, \dots 6}$ and see when $f(x)$ is a square (that is $f(x)=y^2 \in {0,1,2,4}$). You will see that this happens only if $x \in {3,5,6}$. – Watson Jan 18 '16 at 10:42