Exact number of elliptic curves in the canonical form, which are isomorphic to Edwards curves over prime field (Q2515329)

Let \(E_p\) be an elliptic curve over the prime field \(\mathbb{F}_p\) with \(p > 3\) defined by the equation \(y^2 = x^3+ax+b\). Suppose that \(E_p\) has order divisible by 2. Then its equation can be rewritten as \[ y^2 = (x-c)(x^2+cx+a+c^2), \;\;b=-c^3-ac,\;\;c\in \mathbb{F}_p. \] In this paper, it is proved that \(E_p\) has exactly two points of order 4 if and only if \((-(3c^2+4a)/p)=-1\) and \((\delta/p) = 1\), where \(\delta = 3c^2+a\). Next, the number \(N\) of elliptic curves \(E_p\) with \(a\neq 0\) and \(b\neq 0\) with two points of order 4 is given. More precisely, it is proved that in case where \(p\equiv 1\;(\bmod\, 4)\) we have \(N = (p-1)^2/4\) and in case where \(p\equiv 3\;(\bmod\, 4)\) we have \(N=(p-1)(p-7)/4\) if \((3/p)=1\) and \(N=(p-1)(p-3)/4\) if \((3/p)=-1\). Finally, an algorithm is proposed for random generation of a canonical curve isomorphic to Edwards curve.