Next: 11.4 Other problems Up: 11 Algorithms for groups Previous: 11.2 Shanks' Baby step-Giant

## 11.3 Pohlig-Helman factor method

We now assume that we are given the factorisation of the order n of the group G and we want to find another relation which is smaller than the obvious relation (n,..., n).

Let p be a prime factor of n and k such that pk| n while pk + 1 n. Replacing gi by gin/pk, we have effectively replaced the given problem to the case of G(p), the p-adic part of G. By the Chinese Remainder Theorem these solutions can later be combined. Thus we may assume that the order of G is a power pk of a prime p.

In the case when k = 1 we can apply the Baby step-Giant step method to find a relation as above. When k > 1, we inductively find a relation (b1,..., br) between the elements gip which lie in the group Gp which has order pj for some j < k. Now, we only need to find (again using the Baby step-Giant step method) a sequence (a1,..., ar) with ai < p such that

giai . gipbi = 1

Note that the same sorted list can be used in each step of this induction.

This algorithm can also be applied in the case when we do not know a factorisation of n but we have some given finite set of small'' primes which are known to factorise n completely.

Next: 11.4 Other problems Up: 11 Algorithms for groups Previous: 11.2 Shanks' Baby step-Giant
Kapil Hari Paranjape 2002-10-20