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 p^k| n while p^{k + 1} $\not\vert$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₁,..., 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₁,..., a_r) with a_i < p such that

$$\prod_{i}^{}$$g_i^{a_i .} $$\prod_{i}^{}$$g_i^pb_i = 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.