Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Suppose I have an elliptic curve defined over a prime field $\operatorname{GF}(p)$ where $p$ is a large prime (e.g. 256-bit). Suppose also that $p = kn +1$, where $n$ is a relatively large power of $2$ (e.g. $2^{32}$). This structure implies that $\operatorname{GF}(p)$ has $n^{\mathit{th}}$ roots of unity.
My question is: does the fact that $\operatorname{GF}(p)$ has "high order" roots of unity make curves defined over this field inherently less secure?
My question is: does the fact that $\operatorname{GF}(p)$ has "high order" roots of unity make curves defined over this field inherently less secure?
Not particularly; the factorization of $p-1$ is not specifically relevant to the strength of a curve over $\operatorname{GF}(p)$.
Now, it is quite relevant to the strength of the group $\mathbb{Z}_p^*$; however that's because the order of the group is always $p-1$ (assuming $p$ is prime), and the factorization of the group order is quite relevant. However, the elliptic curve (in general) doesn't have order $p-1$; instead, it is $p + \delta$ for some $|\delta| < 2\sqrt{p}$ (the exact value of $\delta$ depends on the precise curve you pick), and it is the factorization of $p + \delta$ which is important.
