if a number is said to be a subgroup of a quadratic residue of Z∗p, can I affirm that it is a generator of a cyclic group ?

ie, say i am looking for a number which is an element of order q in Z*p, and P is a prime and equal to 7, can I say that 3 is a generator of the P?

I am referring to this: http://crypto.stanford.edu/pbc/notes/numbertheory/gen.html

Thanks!

regards, Ken

• please edit your question. Its a bit weird what you are writing. – DrLecter Jan 9 '15 at 20:58

There are some errors in the basic assumptions or in their descriptions.

So, we start with the group $\mathbb{Z}_p^*$, with $p$ prime. This is a cyclic group with order $p-1$.

if a number is said to be a subgroup of a quadratic residue of Z∗p, can I affirm that it is a generator of a cyclic group ?

First, a number (or more formally an element of the group) is not a (sub)group itself.

Concerning the other part: You started with a cyclic group. So any subgroup of this group will also be cyclic. And every element in this group generates a subgroup, and the cardinality of this subgroup is equal to the order of the element in $\mathbb{Z}_p^*$, ranging from $1$ to $p-1$, including any divisor of $p-1$.

Concerning QR: Quadratic residues form a subgroup. Therefore it is also cyclic. And as any cyclic group, it has a number of generators. But not all quadratic residues are generators for the while subgroup of quadratic residues.

ie, if an element g of order q in Z*p, and P is a prime say 7, can i safely assume that g can be 3?

With $p=7, g=3$, $g$ is not a quadratic residue. Therefore, it can not be a generator of the subgroup of quadratic residues. Due to the fact that the order of $g$ is $6$, it generates the entire multiplicative group. The quadratic residues in $\mathbb{Z}_7^*$ are: ${1,2,4}$. Both $2$ and $4$ generate this subgroup.

• hello @tylo, Thanks for the in-depth explanation. So let me try it again with more information and see if its work well: List an element g of order q in Z*p where p = kq + 1, P = 23, Q = 11. So order of g = 11-1 which is 10. As such, the qr is 1, 2 and 5? – kenAu89 Jan 9 '15 at 18:20
• So the order of g has to be 10. Why don't you start checking random elements of Zp to see whether their order is 10? All you have to do check is whether a^10=1 and a^2!=1 and a^5!=1. In principle, this is how we create group generators, but we pick p=2kq+1 (q prime). – absinthe_minded Jan 10 '15 at 4:19
• It would help if you tried to use the built-in math formating of the forum. So you got $\mathbb{Z}_{23}^*$. This has cardinality 22. And therefore, there can only be elements of order 1,2,11 and 22. I have no idea how you get to 10 there, and it is unclear to me, what you are aiming at... Besides, this is actually a purely mathematical question, and probably should be over at math.SE instead of here. – tylo Jan 12 '15 at 10:48