Алгоритм Гельфонда
В настоящее время не известно полиномиальных алгоритмов дискретного логарифмирования в произвольной группе . Мы изложим алгоритм А. О. Гельфонда, который применим к произвольной группе и имеет сложность 
    1. Положить . 
    2. Вычислить 
    3. Построить наборы и элементов . 
    4. Найти некоторый элемент, входящий в оба набора. Если  -- такой элемент, то это значит, что и  -- искомый дискретный логарифм по основанию . 
Отметим, что любой элемент представим в виде при некоторых (это следует из того, что ). Поэтому элемент, входящий в оба набора из этапа 3 алгоритма, существует.