Let *p* be a prime factor of *n* and *k* such that *p*^{k}| *n* while
*p*^{k + 1} *n*. Replacing *g*_{i} by
*g*_{i}^{n/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 *p*^{k} 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
(*b*_{1},..., *b*_{r}) between the elements *g*_{i}^{p} which lie in the group
*G*^{p} which has order *p*^{j} for some *j* < *k*. Now, we only need to find
(again using the Baby step-Giant step method) a sequence
(*a*_{1},..., *a*_{r}) with *a*_{i} < *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.