3

i got stuck doing the exercise 4.5 d) in the Book Elliptic Curves: Number Theory and Cryptography by L. Washington and would be grateful for hints.

Let $ p \equiv 1 \text{ (mod 4)}$ be prime and let $E$ be given by $y^2 = x^3 -kx$, where $k \not\equiv 0 \text{ (mod $p$)}$. Let $k$ be a square but not a fourth power mod $p$. Show that exactly one of the curves $y^2 = x^3 -x$ and $y^2 = x^3 -kx$ has a point of order $4$ defined over $\mathbf{F_p}$.

I tried to find a point such that $2P = (\pm\sqrt{k},0)$, but that did not work out and solving the division polynomial $\psi_4$ also didnt work.

reuns
  • 77,999
ASP
  • 129

1 Answers1

2

  • $k=d^2$ then $y^2=x^3-kx$ is isomorphic to $E_d:y^2=d(x^3-x)$.

  • $E_1:y^2=x^3-x$.

  • Since $d$ is not a square, for all $a\in \Bbb{F}_p$, either $(a,\pm \sqrt{a^3-a})\in E_1(\Bbb{F}_p)$ or $(a,\pm \sqrt{d(a^3-a)})\in E_d(\Bbb{F}_p)$

  • $\#E_1(\Bbb{F}_p)+\#E_d(\Bbb{F}_p)= 2(p-3)+8\equiv 4\bmod 8$

  • Both $E_1(\Bbb{F}_p)$ and $E_d(\Bbb{F}_p)$ contain the 2-torsion (the points coming from $a=\infty$ or $a^3-a=0$)

  • Thus, exactly one of $\# E_1(\Bbb{F}_p)$,$\# E_d(\Bbb{F}_p)$ is $\equiv 0\bmod 8$, the other is $\equiv 4\bmod 8$.

  • Exactly one of $ E_1(\Bbb{F}_p)$,$E_d(\Bbb{F}_p)$ contains some point of order $4$.

reuns
  • 77,999
  • Thank you for providing hints, i have a problem getting from the second to last bullet point to the conclusion that exactly one of the elliptic curves contains some point of order 4. Can you explain it in more detail please. – ASP Jan 21 '21 at 19:38
  • Is $2(p-3)+8$ clear to you? – reuns Jan 22 '21 at 00:38
  • yes, since d is not a square mod p and $E_d$ is a twist of $E_1$ we have that $ #E_1(\mathbf{F}_p) + #E_d(\mathbf{F}_p) = p +1 - a + p +1 +a = 2p+2 $ and since $p\equiv 1$(mod 4) we got $2(4r +1) +2 = 8r +4 \equiv 4$ mod 8. – ASP Jan 22 '21 at 01:28
  • $E_1(F_p)$ is a group so the size of the 2-torsion $# E_1(F_p)[2]=4$ divides $# E_1(F_p)$ and it contains some point of order 4 iff $# E_1(F_p)[4]> # E_1(F_p)[2]$ iff $8 \ | \ # E_1(F_p)[4]\ | \ # E_1(F_p)$ – reuns Jan 22 '21 at 01:59
  • $2(p-3)+8$ follows from that $p-3 $ is the number of $ a$ such that $a^3-a\ne 0$, multiplied by 2 for the sign of $\sqrt{a^3-a}$, and $8=2.4$ is the 2-torsion $(a\in 0,-1,1,\infty$) counted two times since it is in both $E_1(F_p)$ and $E_d(F_p)$. – reuns Jan 22 '21 at 02:03
  • I can now follow your argument why exactly one of them has to have a point of order 4. Regarding the number of points in $#E_1(F_p)+#E_d(F_p)$ the argument why every $a$ that fulfills $a³-a \neq 0$ is counted would be: Since $d^{(p-1)/2} \equiv -1$ and for either possible value of $a^{(p-1)/2} \equiv \pm 1$ we have that it is either contained in $E_1$ or $E_d$. Is the argument i made before wrong or did you wanted to show another possible derivation? – ASP Jan 22 '21 at 02:34
  • There is only one derivation, the one I showed: if $a^3-a\ne 0$ then exactly one of $a^3-a,d(a^3-a)$ is a square. What do you not understand for the point of order $4$? – reuns Jan 22 '21 at 02:39