5.2 Group theoretic method

In the Miller-Rabin test we used the group of units in $\mathbb {Z}$/N$\mathbb {Z}$ (and we will continue to do so) but in fact any algebraic group scheme G can be used to study the factorisation or primality of N. Such a scheme assigns a group G(N) to an integer N. By an application of the Chinese Remainder theorem (to $\mathbb {Z}$/N$\mathbb {Z}$ and not to the group!) one can show that G(N) is a product of the groups G(a) and G(b) if N = ab with a and b coprime. Another aspect is that Hensel's lemma allows us to write (for all but a finite set of ``small'' primes p) G(p^e) as a product of G(p) and a group naturally isomorphic to a direct sum of $\mathbb {Z}$/p^{e - 1}$\mathbb {Z}$'s. The group theoretic method for factorisation depends on the possibility that G(p) has a particularly simple structure for some prime p that divides N. One such criterion for simplicity is smoothness.

Definition 1   Let B be an integer. An integer N is said to be B-powersmooth if it is a product of coprime numbers less than B. Equivalently, N of product of prime powers, each of which is less than B.

Definition 2   Let B be an integer. An integer N is said to be B-smooth it is a product of primes less than B.

We note that a number N is B-powersmooth if and only if it divides the least common multiple l_B = lcm(1,..., B) of all numbers less than B, whereas a B-smooth number can be arbitrarily large when B > 1 (for example 2ⁿ is B-smooth in this case).

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 $\mathbb {Z}$/p$\mathbb {Z}$) is B-powersmooth. We want to find this prime factor. The technique is to take a ``random'' x in $\mathbb {Z}$/N$\mathbb {Z}$ 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₁,..., l_k) be a list of all primes less than or equal to B. We pick an x in $\mathbb {Z}$/N$\mathbb {Z}$ (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^p_i. 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 $\leq$ 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² (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^d_j. We replace x by x^l_k 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^d_i, (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^d_m 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 $\sqrt{N}$ for the powers in any case. Thus an appropriate modification to stage 1 (call it stage 1${\frac{1}{2}}$!) 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.