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 = $32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525193403303896028543209689578721838988682461578457274025662014413066681559$

$q = $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$?

  • $\begingroup$ I think this answer will be very beneficial to you. $\endgroup$ – mikeazo Mar 7 '16 at 15:00
  • $\begingroup$ @mikeazo: thank you so much, that article really help me $\endgroup$ – stranger Mar 7 '16 at 16:28

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$.

  • $\begingroup$ 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 $\endgroup$ – stranger Mar 7 '16 at 16:36
  • $\begingroup$ 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. $\endgroup$ – fkraiem 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'$$.

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

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.