# Given a prime group, is there an easy way to find an element that only generates a small subgroup

I have a group of $(Z_P,*)$ and I'd like to find some elements that will generate only a small subgroup of elements.

Such that if P were something like the first prime above $2^{2048}$, the element would only generate 1000 or so elements.

If so I'd love to hear it, if not I'd love to know why not, thanks in advance.

-
What is your binary operation? Is it modulo addition? In that case the answer is trivial: every non-identity generates the whole group. – Shahab Sep 20 '12 at 5:30

## 2 Answers

The multiplicative group is cyclic of order $P-1$. If $P-1=2Q$ for some prime $Q$ (and it is believed that this happens infinitely often), then the only subgroups are of order $1,2,Q$, and $2Q$, so you're out of luck.

-
Thanks, pretty much what i wanted to know, just one quick follow up if it's not a sophie germain prime is it possible? – Ben Sep 20 '12 at 6:40
It's only possible to find a subgroup with 1000 or so elements if $P-1$ is divisible by some number of size 1000 or so. There is a subgroup of order $d$ if and only if $d$ is a divisor of $P-1$. Mind you, even if you have such a divisor $d$, actually finding the element that generates a subgroup of order $d$ can be extremely difficult. Well, it's easy if you know a primitive root, but that is hard to do. – Gerry Myerson Sep 20 '12 at 6:54

We have that $\mathbb{Z}_p$ is cyclic of order $p$. That is, it is generated by any non-identity element. Thus, the only subgroups are the trivial group and $\mathbb{Z}_p$ itself.

-
I suspect Ben has the multiplicative group in mind. – Gerry Myerson Sep 20 '12 at 5:43