# Variant of Pollard rho using small factors of p - 1

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?