I am trying to generate a "nice" Montgomery elliptic curve on a finite field $\mathbb{F}_q$ such that its birational equivalent twisted Edwards curve has nice properties (for cryptographic application). I am following the approach of the algorithm given in Appendix 1 of Elliptic Curves for Security i.e.:
- $q$ is prime
- $q \equiv 1 \mod(4)$
- The Edwards curve has exact cofactor $8$ (i.e. $ord(Ed_q) = 8.r$ with $r$ prime)
- The twist has exact cofactor $4$ (i.e. $ord(Ed_q) = 8.r$ with $r$ prime)
My experiments so far have reached $A = 220000$ without success. I was hence wondering about the chance of success of finding a curve with suitable properties. Are there any heuristic or conjecture about the proportion of such twisted Edwards curve on a field of prime characteristic? I could not find any related content in the litterature.
If that can be of any help, my prime $q$ is not completely random at a given bit length as it must satisfy some criteria, especially having a large power of two root of unity ( $q - 1 \equiv 0 \mod 2^{\alpha}$) but I'd be happy with some results for random prime $q$.