Алгоритм Полига -- Хеллмана
Этот алгоритм (см. также [PH], [Акр, упр. 24 к разд. 3.3.1], [Odl], [Kob, гл. 4,  3]) позволяет быстро вычислять дискретные логарифмы в группе , если гладкое, т. е. все простые делители невелики. 
Пусть , где -- некоторое конечное множество простых чисел, а . Предполагается, что множество и числа для каждого известны (их можно найти перебором). Алгоритм заключается в следующем: 
    1. (Построение таблиц.) Для каждого вычислим набор элементов , . Отметим, что порядок равен , поэтому 
	(1)	

-- все попарно различные корни -й степени из единицы в группе . Набор (1) называется таблицей корней -й степени из единицы. 
    2. (Вычисление для .) Обозначим через искомый (пока неизвестный)  -- дискретный логарифм по основанию . Для каждого пусть , где . Будем последовательно искать следующим способом: 
  2.1. Вычислим . Так как , где , мы получаем, что 

Поэтому для вычисления достаточно сравнить с элементами таблицы (1) и положить равным тому , для которого . 
  2.2. Пусть уже найдены. Вычислим 

Так как , где , мы получаем, что 

Поэтому для вычисления достаточно сравнить элемент с элементами таблицы (1) и положить равным тому , для которого . 
Таким образом, мы находим и, следовательно, для всех . 
    3. (Вычисление .) Используя китайскую теорему об остатках, вычислим искомый дискретный логарифм по для , найденным на этапе 2 (см., например, [Акр, разд. 2.3.2]). 
Отметим, что если все не превосходят некоторого полинома от , то вышеописанный алгоритм полиномиален от .