Join Log in
Score:1
avatar Crypto

Finding an element of $\mathbb{Z}_p$ if the order of that element is known

cn flag
mangart

I have two prime numbers $p$ (1024 bits) and $q$ (160 bits) such that $q$ divides $p-1$. Now I want to find an element $b$ in $\mathbb{Z}_p$ with the order of $q$. That means that $b^q \equiv 1 \mod p$.

I tried to choose $b$ at random and than check if the congruence holds, but it seems that this is not a good approach since it doesn't give an answer in a reasonable time. So is there any way to find $b$ efficiently?

32
0 + 0
rsa
dsa
us flag
Mikero
I think this is a different question, because finding a generator by trial and error will be much easier than finding an element with a different order. I think the probability of hitting an element with non-trivial order is $1 - \varphi(n)/n$ which is generally negligibly close to zero (the probability of hitting a generator is $\varphi(n)/n$). This suggests the need for a more efficient approach than trial and error which works for finding a generator.
0
Reply
kelalaka avatar
in flag
kelalaka
**From Poncho's answer:** One easy way of selecting a random generator is to select a random value $h$ between 2 and $p-1$, and compute $h^{(p-1)/q} \bmod p$; if that value is not 1 (and with high probability, it won't be), then $h^{(p-1)/q} \bmod p$ is your random generator.
2
Reply
cn flag
mangart
@kelalaka As far as I know a generator is an element that can generate all the elements of the group and so the order of that element would be $p-1$, but I am trying to find an element $b$ that has the order $q$ which is much smaller than $p-1$ and also $b$ by this definition is not a generator of the group.
0
Reply
kelalaka avatar
in flag
kelalaka
That is what the answer includes. Read carefully.
1
Reply
cn flag
mangart
@kelalaka Oh I see, the answer is actually in the Wikipedia article linked in that answer, about the Schnorr group. So that actually answers my question. Thank you so much and sorry for not reading your suggested question more thoroughly the first time.
0
Reply
poncho avatar
my flag
poncho
If $q$ is prime, my answer is the right one. If it is not, but its factorization is known, then my answer (which some simple post tests works). If the factorization is unknown, then I don't believe there is a way that works all the time (but you can get one that works with probability $> 0.99$
1
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.