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
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.