Решето поля функций

Решето поля функции — эффективный метод извлечения дискретного логарифма над конечным полем небольшой характеристики (в математике), введённый в 1994 году Леонардом Адлеманом, разработан Адлеманом и Хуангом в 1999 году.

Просеивание точек, в которых полиномозначная функция делится на данный полином, не намного сложнее, чем просеивание целых чисел – базовая структура довольно похожа, и код Грея предоставляет очень эффективный удобный способ перехода через кратности данного многочлена.

Ссылки

Статья Адлемана–Хуанга доступна по адресу Science Direct, но рассматривает проблему с использованием истинного алгебро-геометрического языка.

Теоретико-числовые алгоритмы
Тесты простоты	Миллера Миллера — Рабина Люка — Лемера Пепина Агравала — Каяла — Саксены Соловея — Штрассена
Поиск простых чисел	Перебор делителей Решето Эратосфена Решето Аткина Решето Сундарама
Факторизация	Перебор делителей Метод Ферма p−1-метод Полларда ρ-алгоритм Полларда Метод Лемана Метод эллиптических кривых (алгоритм Ленстры) Алгоритм Диксона Квадратичное решето
Дискретное логарифмирование	Алгоритм Гельфонда — Шенкса Алгоритм Полига — Хеллмана ρ-метод Полларда Алгоритм «кенгуру» Полларда Алгоритм Адлемана Алгоритм COS
Нахождение НОД	Алгоритм Евклида Расширенный алгоритм Бинарный алгоритм
Арифметика по модулю	Алгоритм Монтгомери Китайская теорема об остатках
Умножение и деление чисел	Алгоритм Карацубы Алгоритм Тоома — Кука Алгоритм Шёнхаге — Штрассена Алгоритм Фюрера Алгоритм Харви — ван дер Хувена Алгоритм Бурникеля — Циглера
Вычисление квадратного корня	Алгоритм Тонелли — Шенкса Алгоритм Берлекэмпа — Рабина