How to find element g order q, given 2 large primes p and q where q|p-1

i have calculated 2 large primes, $p$ (minimum 2048 bits) and $q$ (minimum 224 bits), where $p-1 \mod q = 0$ by using SageMath.

$p =$32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525193403303896028543209689578721838988682461578457274025662014413066681559q = $26959946667150639794667015087019630673637144422540572481103610249951 Now, i need element$g$order$q$. I try to find it, but it takes so long (still running). Anyone have idea how to find element$g$? • I think this answer will be very beneficial to you. Mar 7 '16 at 15:00 • @mikeazo: thank you so much, that article really help me Mar 7 '16 at 16:28 2 Answers The multiplicative group$\mathbf{Z}_p^*$of non-zero integers modulo$p$is cyclic of order$p-1$, so it has exactly one subgroup of order$k$for each divisor$k$of$p-1$. In particular, it has exactly one subgroup of order$q$, which consists of those integers$a$such that$a^q \bmod p = 1$. Let$G$be this subgroup. To obtain an element$g$of$G$, take any element$a$of$\mathbf{Z}_p^*$and let$g = a^{(p-1)/q} \bmod p$. Then$g$is an element of$G$because $$g^q = \left(a^{(p-1)/q}\right)^q = a^{p-1} = 1 \pmod p.$$ The order of$g$is a divisor of the order of$G$, so it is a divisor of$q$, and since$q$is prime, it equals either$1$or$q$. The only element of order$1$is the identity$1$, so if$g \not\equiv 1 \pmod p$you are done. Otherwise, try another$a$. • thank you so much.. I have one more question for your answer.. the value of g is guaranteed has order q? not multiplicative of q? for example, suppose p = 23, and I choose a = 2, the order of a is 11 (a^11 mod 23 = 1) although a^22 mod 23 also 1.. sorry, I'm new to this thing Mar 7 '16 at 16:36 • If the order of$g$were larger than$q$, we would not have$g^q \bmod p = 1$because the order of$g$is the smallest integer$k$such that$g^k \bmod p = 1$. In your example$q = 11$so there is no problem. Mar 7 '16 at 16:40 Let$G$be the group with order$p-1$. Select random element from$G$and call it$g'\$. Then compute

$$g=\frac{p-1}{q}\cdot g'$$.

• I have no idea why someone downvoted you, unless they didn't understand that you wrote this in additive, not multiplicative notation. Mar 7 '16 at 15:44
• @Meysam Ghahramani : Thank you very much for your answer.. Mar 7 '16 at 16:38