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$
2
  • $\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, 2019 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, 2019 at 22:42

1 Answer 1

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$
2
  • $\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, 2019 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, 2019 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.