Efficiency of finding sub group order vs factorization Suppose you got a prime $p = 2\mathbb\Pi_{i=0}^{n-1}q_i+1$, where $2^{k-1} \lt q_i \lt 2^k$ for some $k$ and all $0 \le i \lt n$, and that you also got a generator $g$ of one of the prime order sub groups of $\mathbb Z_p^*$. Also assume that the factorization of $\frac{p-1}{2}$ is unknown.

Question #1:

Are there ways to find the order of $g$ faster than using the elliptic curve and number field sieve methods for factoring $\frac{p-1}{2}$? The expected running time of the generic meet-in-the-middle algorithm for finding the order of $g$ is $O(\sqrt{2^k})$, which might be assumed to be greater than the running time of ECM.

Question #2:

Suppose Alice picks an element $x$ uniformly from $\mathbb Z_{q_0}$ and that $g$ is a generator of the $q_0$ order subgroup of $\mathbb Z_p^*$. Alice calculates $y = g^x \mod p$ and gives $(p,g,y)$ to Bob. Bob's goal is to find $q_0$ and he gets to do that either by factoring $\frac{p-1}{2}$, by finding the order of $g$ and $y$, or by collecting solutions $(a_j,b_j)$ to the equation $BS2I(a_j) \equiv xBS2I(b_j) \pmod {q_0}$ using the following protocol:


Bob: Pick an element $a_j \in \{0,1\}^k$ and send it to Alice
Alice: Calculate $c = x^{-1}BS2I(a_j) \mod {q_0}$. For some deterministic function $f:\mathbb Z_{q_0} \rightarrow \{0,1\}^k$ such that $BS2I(f(z))\equiv z \pmod {q_0}$ for all $z\in \mathbb Z_{q_0}$, calculate $b_j=f(c)$ and send $b_j$ to Bob.
Bob: Verify that $g^{BS2I(a_j)} = y^{BS2I(b_j)} \mod p$.


Question #3:

If we regard the protocol in question #2 as a simple instance of polynomial evaluation, where Alice picks two polynomials $r(), s()$ with coefficients in $\mathbb Z_{q_0}$ and provides Bob with the means to verify if $r(BS2I(a_j)) \equiv s(BS2I(b_j)) \pmod {q_0}$, where Bob picks $a_j$ and Alice provides the solution $b_j$ - would choosing polynomials with higher degree than 1 make it significantly harder for Bob to solve $q_0$?
Concerning question 3, here is an answer assuming that the coefficients of $r$ are known to Bob and the coefficients of $s$ hidden in an exponential representation. [This is unessential, it can be easily generalized to hidden $r$, but it simplifies the presentation].

To further simplify, let's also assume that $s$ contains no constant term. In this setting, each pair $(a_i,b_i)$ as in the question is equivalent to a pair $(A_i,b_i)$ together with the information that $s(b_i)\equiv A_i\pmod{q_0}$. This can be easily rewritten as a linear equation $$\sum_{k=1}^{\ell}s_kb_i^k\equiv A_i\pmod{q_0},$$where $\ell$ is the degree of $s$. Collect $\ell+1$ such equations and form the matrix:
$$
M=\left(\begin{array}{ccccc}-A_1 &amp;b_1 &amp; b_1^2 &amp; \cdots &amp;b_1^\ell\\
-A_2 &amp; b_2 &amp; b_2^2 &amp; \cdots &amp;b_2^\ell\\
\vdots &amp;\vdots &amp; \vdots &amp; \ddots &amp; \vdots\\
-A_{\ell+1}&amp; b_{\ell+1} &amp; b_{\ell+1}^2 &amp; \cdots &amp;b_{\ell+1}^\ell\\
\end{array}\right).
$$ 
By construction the system $Mx=0$ has a non zero solution vector (formed by a '1' followed by the coefficients of $s$) modulo $q_0$. As a consequence, $\det(M)$ is a multiple of $q_0$. Form two such matrices, take gcd and you can recover $q_0$ directly.

Note that this can be made more efficient by taking a rectangular matrix $M$ (with extra equations) and computing a Hermite normal form.