next up previous
Next: 5.3 Primality Certificates Up: 5 Factorisation and Certificates Previous: 5.1 Pollard's

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(pe) as a product of G(p) and a group naturally isomorphic to a direct sum of $ \mathbb {Z}$/pe - 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 lB = lcm(1,..., B) of all numbers less than B, whereas a B-smooth number can be arbitrarily large when B > 1 (for example 2n 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(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 $ \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 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 $ \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 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 $ \sqrt{N}$ for the powers in any case. Thus an appropriate modification to stage 1 (call it stage 1% latex2html id marker 15458
$ {\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.

next up previous
Next: 5.3 Primality Certificates Up: 5 Factorisation and Certificates Previous: 5.1 Pollard's
Kapil Hari Paranjape 2002-10-20