# Why only non-prime order fields have small subgroup attacks?

Why don't prime-order curves have small subgroup attacks?

It seems that I can choose a Generator such that it has a small order, maybe 2 points, and so an attack could generate all of the points in that subgroup and figure out the scalar that exponentiated it.

Why only non-primes this is possible? Do prime fields have subgroups of a certain size, that ensures this?

Also is it correct to say "prime-ordered curves" ? It is the Field that the curve is defined over that has prime order, so I feel like i'm saying it wrong.

In Group theory, it is known that if $$G$$ is a finite group and $$q$$ is a prime number dividing the order of $$G$$ (the number of elements in $$G$$), then $$G$$ contains an element of order $$q$$ (Cauchy's theorem). And the order-$$q$$ element generates an order $$q$$ subgroup.
Thus if a group $$G$$'s order $$N$$ is not a prime number, then $$N$$ can be factored and $$q_1,\cdots,q_n$$ are the prime factors of $$N$$. For each $$q_i$$, there must exist a subgroup of order $$q_i$$. When $$q_i$$ is small, the subgroup is small. Hence small subgroup attack may be possible.
If a group $$G$$'s order is a prime number $$p$$, then by the Lagrange's theorem, the order of every subgroup $$H$$ of $$G$$ divides the order of $$G$$. Now $$p$$ has only two factors $$1$$ and $$p$$, thus $$G$$ can have two only subgroups: the trivial subgroup containing the identity $$\{1\}$$, and $$G$$ itself. There is no other small order sub-groups.
You also need to distinguish the finite field $$F_p$$ and the curve over the finite field $$F_p$$. They are two different things. The order of $$F_p$$ is the $$p$$ (elements are integers from 0 to $$p-1$$, inclusive), and the order of the curve over the finite field $$F_p$$ is the number of points on the curve and is bounded by the Hasse theorem $$|order(E(F_p)) - p-1|\le 2\sqrt{p}$$. A curve can be prime-ordered (or we can use a prime-ordered subgroup of all the points on the curve if the curve order is composite), but it is not simply because it is over a prime field.
• "If $G$ is a cyclic group, then the order-$q$ element generates an order $q$ subgroup." Certainly this is true even if $G$ is not cyclic. ;) – fkraiem Jan 14 '19 at 0:31