The claim is that there are quick procedures to factor N if it has a prime factor so that G(p) is B-powersmooth or more generally has a ``large'' B-smooth number as factor. We now restrict ourselves to the case when G is the group of units to understand this procedure.
Let us now assume that N has a prime factor p so that p - 1 (which is the order of the group of units in /p) is B-powersmooth. We want to find this prime factor. The technique is to take a ``random'' x in /N and calculate gcd(xa - 1, N) for a dividing B. Whenever this is not 1 or N we have hit on a factorisation of N. As usual, we use Pollard's idea of accumulating numbers to avoid computing GCD too often.
Let L = (l1,..., lk) be a list of all primes less than or equal to B. We pick an x in /N (which is usual taken to be ``small''). We also a pick an s which is the number of steps over which we will accumulate. We initialise our accumulator P as 1. We also initialise by setting i = 1 so that we pick the first prime. We now loop over the following steps.
We first keep a y and j so that we can backtrack over these s steps; these are initialised as x and i. We compute the largest power pi of li that is less than B and replace x by xpi. We multiple P by x - 1. We then increment i. Every s steps (or if i becomes k), we compute gcd(P, N). If this is 1, then we re-initialise y and j to be the current values of x and i respectively and set P = 1 and loop (unless i is k in which case we have proved that N is not divisible by a p so that p - 1 is a B-powersmooth number!). Otherwise, we have found a non-trivial GCD, for some power of y which divides the powers pj,...,pi (here i is at most j + s).
Now, we set P = 1, and starting with m = j do the following. Replace y by its pm-th power y and check gcd(y - 1, N). We increment m and continue. We know that for some k i, we will find a non-trivial GCD. If this is N, then we know that N does have a factor p so that p - 1 is B-powersmooth so we should try again with some other choice of x. What has happened in this case is that the order of the chosen x has coincided in the group of units modulo different factors of N; so a different choice of x should do the trick.
Even when the above computation proves that N has no B-powersmooth factors, the above computation should not be thrown away! There is a second stage process which examines the case when N has a factor p so that p - 1 is the product of a B-powersmooth number and a prime number less than B2 (in other words p - 1 is completely factored by trial division upto B). More specifically, let us assume the p - 1 is of the form fq where q is a prime less than C and f is B-powersmooth (where C > > B). We keep the list D = (dk + 1,..., dl) of successive differences for primes between B and C (i. e. dk + 1 = lk + 1 - lk and so on). One we have exited from the previous algorithm, we put b = x and compute the list of powers bdj. We replace x by xlk and set i = k and then loop as follows.
We set our accumulator P to 1, y to x and j to i (which are for backtracking as before). We increment i and multiple x by bdi, (which we have already computed). Then we multiple P by (x - 1). Every s steps (or if i becomes l), we compute gcd(P, N). It this GCD is 1, we loop back (or if i = l then we have shown that N does not have a prime facor of the required form). Otherwise, there is some prime between pj and pi which is like q above.
We continue the analysis at this level as follows. We start at m = j and multiply y by bdm and check gcd(y - 1, N). If this is 1, then we increment m and continue (we will do this at most s times). Otherwise we have found a non-trivial GCD. If this is not N, then we have a factor. On the other hand, if this is N, then as before we must take a different starting x at stage 1 and repeat the process, because we have shown that there is a factor p of the reuqired form.
We can replace the B-powersmooth-ness condition above by B-smoothness since we have an upper bound for the powers in any case. Thus an appropriate modification to stage 1 (call it stage 1!) will alow us to incorporate B-smooth factorisations as well. This approach will replace a constant (essentially log(B)) in the complexity (number of steps in terms of log(N)) by log(N). Thus the order of complexity is increased by 1.