Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
add comment

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
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
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. –  Gerry Myerson Sep 20 '12 at 6:54
add comment

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.

share|improve this answer
    
I suspect Ben has the multiplicative group in mind. –  Gerry Myerson Sep 20 '12 at 5:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.