# Which is the fastest way to find a member of a subgroup with known size modulo prime $P$, with know factorization of $P-1$?->$x$ with $x^s \mod P = 1$

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)

• 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$? – poncho May 3 '19 at 22:28
• looking for a prime $x$ but that should be found quite fast after finding any member of this group not equal to 1. – J. Doe May 3 '19 at 22:42

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?
• @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 – poncho May 4 '19 at 13:50