Given an integer $N$ to factor which is divisible by some prime $p$, suppose you know (or guess) that $p - 1$ has a few small factors, e.g. $3, 2^2, 5$. Define $B$ as a product of small prime powers so that $q \vert p - 1$ and $q \vert B$ where $q$ is the largest such integer. With these assumptions it's possible to attempt to speed up Pollard's rho algorithm for factorization somewhat by using the function:
$$f(x) = x^{B} + 1 \bmod{n}$$
because $x^B$ will map elements of $(\mathbb{Z}/p\mathbb{Z})^\times$ into the subgroup $G_q$ generated by the $q$th root of unity modulo $p$, which has cardinality at most (and dividing) $\frac{p - 1}{q}$; this function will result in shorter cycles, faster. We expect the number of iterations to be proportional to $\sqrt{\frac{p - 1}{q}}$, though of course we do $\log_2(B)$ work each iteration rather than just a single squaring. If $B / q$ is not too large, this can be a win overall since the log function grows slower than the square root function; its speedup relative to rho can be estimated as
$$\frac{\sqrt{\frac{q}{2}}}{\log_2(B)}$$
This variant is a bit of a continuum between rho and the p - 1 algorithm though it is fairly pointless in practice; you usually don't know the small factors of p - 1, so you need a large $B$ relative to the product of primes that actually divide p - 1, increasing iteration overhead without speeding up the algorithm and it ends up less efficient than either algorithm on average, at least over the field of integers modulo $p$. I suppose that is why it is not mentioned anywhere in the literature.
The difficulty seems to be that while it's easy to get a pseudorandom function over the multiplicative group of integers by just combining multiplication and addition (the two field operations available), there's no fast way to do the same over $G_q$; you can stay within the subgroup using the group operation (multiplication) but this is insufficient to obtain a random function, since it's a permutation. And there is no convenient addition operation to introduce some nonlinearity either; the values of $G_q$ are distributed more or less randomly in $[1, p - 1]$ so naively adding a constant mod $p$ is sure to take you out of the subgroup, and then you need to spend $\log(B)$ work to recover a subgroup element. If there was a way to work completely within this subgroup efficiently, this variant might actually be useful.
My question is, is it possible to construct a proof that there exists no function $f: G_q \mapsto G_q$ which approximates a random function that could be evaluated in time independent of $q$ in the context of Pollard's rho algorithm?
