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}$)

Question

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}<m$$

---

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$?

Answer 1

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).