-1
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – kenAu89 Jan 9 '15 at 18:20
  • $\begingroup$ 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). $\endgroup$ – absinthe_minded Jan 10 '15 at 4:19
  • $\begingroup$ 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. $\endgroup$ – tylo Jan 12 '15 at 10:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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