0
$\begingroup$

Assuming you know the factorization of used prime $P-1$
$P-1 = s \cdot f_2\cdot f_3...f_i$
Now you want to find a member of a subgroup $\mathbb{Z}_s$. This means any $x$ with
$x^s \equiv 1 \mod P $

Naive way whould be selecting a random value $x$, compute $x^s$ and check if it is equal to $1$.

Another way I found online: transform to disc. log
This first first computes a prime root $g$ of $P$. With this you can rewrite the equation:
$x^s \equiv (g^k)^s \equiv (g^s)^k \mod P$
And computes a $k$ with Shanks' baby-step giant-step algorithm.

Is that the best/fastest way to go? Does it help if $s$ is a prime?
Is there a faster way if you are allowed to change $s$ and $P$ as well?
e.g. instead finding $x$ look for a fitting P' instead. For this fix $x$ to any number of choice $x_{const}$ and search for a $P'=s \cdot f +1$
$x_{const}^s \equiv 1 \mod P' $

(Trivial $x$ like $x = 1+n \cdot P$ do not count here)

$\endgroup$
  • $\begingroup$ The absolutely fastest way to find a member of the subgroup is to pick 1; that certainly statisfies $x^s \equiv 1 \pmod P$. Perhaps you have some additional requirements on $x$? $\endgroup$ – poncho May 3 at 22:28
  • $\begingroup$ looking for a prime $x$ but that should be found quite fast after finding any member of this group not equal to 1. $\endgroup$ – J. Doe May 3 at 22:42
1
$\begingroup$

Is that the best/fastest way to go?

Well, unless you give some criteria, whether it's the best is unanswerable. However, it might not be the fastest; you could just note that $k = f_2 \cdot f_3 \cdot … \cdot f_i$ and skip the baby-step-giant-step algorithm entirely.

In addition, if all you want is a random element of the subgroup, you don't need to find a generator. Instead, all you need to do is select a random value $r \in [1, P-1]$, and compute $x = r^k \bmod P$ (using the above definition of $k$); if $x \ne 1$ (true with probability $1 - 1/s$), that's what you're looking for.

BTW: why do you think you need $x$ to be a prime?

$\endgroup$
  • $\begingroup$ Thanks, how could I miss that. That's much faster. I want to use it for my other question crypto.stackexchange.com/questions/70282/… . So far I used primes and it did work. Now I did some test with normal numbers. It worked as well. So nvm about that prime condition. Thanks again for that hint. Are there any common criteria for values x? Can it be good or bad, safe or unsafe? $\endgroup$ – J. Doe May 3 at 23:36
  • 1
    $\begingroup$ @J.Doe: if we're worried about DLog/DH problems, well, assuming $s$ is prime, then there aren't any weak $x$'s (other than 1); they're all equally strong $\endgroup$ – poncho May 4 at 13:50

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.