# How to efficiently find Schnorr groups that have a generator $g=2$?

A Schnorr group is a multiplicative group of integers modulo an odd prime $$p$$ of prime order $$q$$, normally such that $$p$$ is much greater than $$q$$.

As far as I know, the normal way to find a Schnorr group is to:

1. determine $$q$$ as a random prime in the desired range of the group size (e. g. $$2^{255} \le q < 2^{256}$$), which ultimately also determines the signature size of Schnorr signatures;
2. pick a random number $$r$$ that brings $$p$$ into the desired $$b$$-bit range such that $$\lfloor log_2r \rfloor=b-\lfloor log_2q\rfloor$$ (e. g. $$2^{1792} \le r < 2^{1793}$$ for bit size $$b=2048$$ of $$p$$, with the value of $$q$$ being in the range of the example noted above), where $$p$$ should be fairly large to resist attacks, namely it should be at least a 2048-bit number;
3. compute $$p=qr+1$$ and check whether the resulting $$p$$ is prime;
4. for $$g=h^r\pmod{p}$$, check whether $$g \equiv 1\pmod{p}$$ and return to step 2 if so, else $$g$$ is the generator of the group.

However, for efficiency reasons, I'm interested in groups with the generator $$g=2$$ because exponentiation of $$2$$ is a trivial bit shift. When generating groups with the method outlined above, there is an approximate chance of $$\frac{\lfloor\log_2{q}\rfloor}{\lfloor\log_2{p}\rfloor}$$ that $$2$$ is a member of the group – and all members of the group are generators of the group because $$q$$ is prime. However, that is still an effectively impossible chance.

Is there a way to generate a Schnorr group with $$g=2$$ that doesn't rely on random chance and is reasonably efficient to compute (possible to do within at most weeks on commodity hardware)?

• Is there a specific reason you want a Schnorr group, rather than a safe prime (which would make this problem comparatively easy)? Aug 22, 2020 at 14:25
• @poncho That's because I want to do Schnorr signatures over the resulting group. It doesn't have to be a Schnorr group specifically as long as it's a group suitable for DL-based Schnorr signatures (implying $q$ being small and $p$ being large). Aug 22, 2020 at 14:57