Алгоритм Хеллмана -- Рейнери
Рассмотрим теперь случай, когда невелико. Тогда для дискретного логарифмирования в применим следующий алгоритм (см. [HR], [Kob, гл. 4,  3]). 
    1. Поле представим в виде факторкольца , где  -- неприводимый многочлен степени . Поэтому можно считать, что элементы есть многочлены из степени не выше . Элемент имеет порядок , следовательно, он является порождающим . Зная его, составляем таблицу логарифмов "констант" -- элементов (логарифмы по основанию ). Так как невелико, то это можно сделать эффективно. 
    2. Пусть  -- множество всех неприводимых многочленов из степени не выше , где  -- некоторое натуральное число, меньшее . 
    3. Случайно перебирая , , находим те из них, для которых 

где и . (Разложение на множители можно находить, например, с помощью алгоритма Берлекэмпа (см. [Акр, разд. 6.2.4]), эффективного при малых ). Им соответствуют уравнения 

относительно неизвестных . 
    4. Получив на предыдущем этапе достаточно много уравнений относительно , , решаем систему уравнений и находим , . 
    5. Находим , такое, что 

где и . Тогда искомый дискретный логарифм равен 

Этот алгоритм имеет субэкспоненциальную сложность. 
Несколько иную схему логарифмирования в предложил Эль Гамаль [ElG84], [ElG85], [ElG86]. Оценка сложности алгоритмов Эль Гамаля субэкспоненциальная (при некоторых эвристических допущениях).