# How to find a small generator with small inverse? Does it have negative impact to security? (for Schnorr subgroup of $\mathbb{Z}/P\mathbb{Z}$)

Given a prime $$P$$ with $$P= r \cdot q+1$$ with $$q$$ prime as well.
I'm looking for a generator $$g$$ of the Schnorr subgroup with order $$q$$ which is small by value and has a inverse (to $$\bmod P$$) which is small as well: $$|\{g^i, \forall i \in [0,P-1]\}| = q$$ $$g^q = 1 \bmod P$$ $$g < m \text{ } \land \text{ } g^{-1}

To find a Schnorr group generator $$g$$ in general we can pick a random value $$h$$ until $$h^r \not= 1 \bmod P$$ $$\rightarrow \text{ } g = h^r \bmod P$$ To find $$g^{-1}$$ we can use the Extended Euclidean algorithm or just compute: $$g^{-1} = g^{q-1} \bmod P$$

Questions:

Q1.) What is the best way to find $$g,g^{-1}$$ which are each less than value $$m$$? (edit: found some with step-by-step computation. Main interest now is Q3 (edit-end))
Q2.) How small can $$m$$ be?
Q3.) Would a small $$g,g^{-1}$$ have any impact to security?

Trial for Q1: Ways to find small $$g, g^{-1}$$
a.) pick random $$v$$ number and project to Schnorr group $$v_s = v^r \bmod P$$
(all values but $$1$$ of a Schnorr group are generators)
b.) compute inverse with EEA or with $$v_s^{q-1} \bmod P$$ (any way faster?)
c.) check if $$g, g^{-1} < m$$ . If not repeat a.)b.)c.)

Another way than random picks all the time would be an initial random pick for $$g$$, and a 2nd random value $$w$$ in this group to start from. Compute the inverse of both as well and traverse through the group with new generator $$g^*_j$$: $$g_j^* = w \cdot (g)^j \bmod P$$ $${g_j^*}^{-1} = w^{-1} \cdot (g^{-1})^j \bmod P$$ $$w \cdot (g)^j \cdot w^{-1} \cdot (g^{-1})^j = 1 \bmod P$$ and test if $$g^*_j$$ and its inverse are smaller than $$m$$.
This computes the values faster but will it be faster in finding suitable generator? Can it be for certain values the results lay in a valley of bad values?

Trial for Q2: How small can $$m$$ be?
The product of $$g, g^{-1}$$ need to be at least $$p+1$$
That means $$m \ge \sqrt{p-1}$$
Is there another higher border for smallest $$m$$?

In general the equation need to hold: $$g \cdot g^{-1} = a\cdot P +1 \equiv 1 \bmod P$$ $$a \in [1,P-2]$$

Can the factorization of $$(aP+1)$$ be used to solve Q1 ($$g,g^{-1}$$ products of factor(combinations))?
Any way to guarantee its inside the Schnorr group?
Or just check again with $$g^q = 1 \bmod P$$?

• As for Q2: it's unlikely that you could give significantly larger bounds on $m$; one small example I found was $p=229\cdot 698512 + 1, g = 12645, g^{-1} = 12650, ord(g) = 229$; this example has an $m=12650$ which is not much larger than $\sqrt{p-1} = 12647.4997...$. Obviously, that's much smaller than a cryptographically relevant example, however the existence of such suggests that there are likely to be much larger ones. – poncho Feb 3 at 16:37
• @poncho also did some experiments. It tried with a prime ~69 bit. In first trial I didn't found any factor below $2^{59}$. After changing prime and factors a little (about same size) I could find some small generators (54 and 57 bit). Those are not that small as yours but they are sufficient for me. I wrote some program in C which found them quite fast (like my trial Q2 above (part II)). Now my main interest is Q3, If such small generators with small inverse have an impact to security. – J. Doe Feb 3 at 17:42

Q3.) Would a small $$g, g^{-1}$$ have any impact to security?

It would not appear so. It is easy to show that, if we had a generator $$g$$ that makes the Discrete Log (or the Computational Diffie-Hellman) problem easy, then the Discrete Log/CDH problem is easy with respect to any base $$h$$ that's within the same subgroup.

Suppose we had a way that, given $$g, g^x$$, gave us the value $$x$$. Then, what we could do, given $$h, h^y$$ is first find the value $$z$$ such that $$g^z = h$$ (by solving the discrete log to the base $$g$$), and then the value $$w$$ such that $$g^w = h^y$$ (again, solving another discrete log to the base $$g$$); then, we have $$h^{wz^{-1}} = h^y$$; since we know $$w$$ and $$z$$, that tells us the discrete log. Similar (but more complicated) logic allows us to solve the Computational Diffie-Hellman problem, given a CDH oracle with respect to base $$g$$.

However, this is not a complete answer to the question; it might be that the existence of a small $$g, g^{-1}$$ makes all discrete log/CDH problems easy.

I don't know of a way this can be disproven. However:

• None of the known discrete log methods have significant speed-ups when given a small $$g, g^{-1}$$ (by significant, I mean more than speeding the operation of multiplying by $$g$$)

• For just about any prime, there will be tiny $$g$$ values that generate groups that contain the Schnorr group as a subgroup. If there were a fast way to complete discrete logs with a tiny $$g$$ in this group, then you could use that to compute discrete logs in the Schnorr group (and although this argument doesn't take into account the tiny $$g^{-1}$$, there's no obvious way to use that).