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(*x*^{a} - 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* = (*l*_{1},..., *l*_{k}) 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 *p*_{i} of *l*_{i} that is less than *B* and replace *x* by
*x*^{pi}. 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
*p*_{j},...,*p*_{i} (here *i* is at most *j* + *s*).

Now, we set *P* = 1, and starting with *m* = *j* do the following. Replace
*y* by its *p*_{m}-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 *B*^{2} (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* = (*d*_{k + 1},..., *d*_{l}) of successive differences for primes
between *B* and *C* (i. e.
*d*_{k + 1} = *l*_{k + 1} - *l*_{k} and so on). One we have
exited from the previous algorithm, we put *b* = *x* and compute
the list of powers *b*^{dj}. We replace *x* by *x*^{lk} 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
*b*^{di}, (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 *p*_{j} and *p*_{i} which is like
*q* above.

We continue the analysis at this level as follows. We start at *m* = *j*
and multiply *y* by *b*^{dm} 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.