0
$\begingroup$

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.

  • 1
    What is your binary operation? Is it modulo addition? In that case the answer is trivial: every non-identity generates the whole group.2012-09-20

2 Answers 2

2

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.

  • 2
    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.2012-09-20
0

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.

  • 0
    I suspect Ben has the *multiplicative* group in mind.2012-09-20