Skip to content

Pohlig-Hellman algorithm

Description

If group order is not a prime number, but a smooth one with little factors, the ECDLP problem can be solved in less time. Instead of \(O(\sqrt{n})\), \(O(\sum e_i*(\log{n} + \sqrt{p_{i}}))\). Where \(n = \prod p_{i}^{e_{i}}\)

Task

Given arbitary curve \(E\) with smooth order and some point \(P = d*G\), find \(d\).

Solution

This is a general ECDLP problem, but it can be simplified using Pohlig-Hellman algorithm, which restates the problem of finding ECDLP in \(n\)-order group to finding ECDLP in groups with order of divisors of \(n\).

Then after applying CRT to equations \(k = k_{i} \mod p_{i}^{e_{i}}\) we find \(k\).

How to generate task

./gen_task.sh > >(tee task.txt) 2> >(tee log.txt >&2)

You will get two files:

  • task.txt — task itself
  • log.txt — task generator log with answer