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


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?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.