В математике полиномы деления позволяют вычислять кратные точки на эллиптических кривых и изучать поля, создаваемые точками кручения. Они играют центральную роль при изучении подсчета точек на эллиптических кривых в алгоритме Шуфа .
Множество полиномов деления представляет собой последовательность полиномов от
с
свободные переменные, которые рекурсивно определяются следующим образом:








Полином
называется н й полином деления.
- На практике устанавливают
, а потом
и
. - Полиномы деления образуют общую эллиптическую последовательность делимости над кольцом.
. - Если эллиптическая кривая
задается в форме Вейерштрасса
над каким-то полем
, то есть
, можно использовать эти значения
и рассмотрим полиномы деления в координатном кольце
. Корни
являются
-координаты точек
, где
это
торсионная подгруппа
. Аналогично, корни
являются
-координаты точек
. - Учитывая точку
на эллиптической кривой
над каким-то полем
, мы можем выразить координаты n й кратный
в терминах полиномов деления:

- где
и
определяются: 

Используя соотношение между
и
, наряду с уравнением кривой, функции
,
,
все внутри
.
Позволять
будь простым и позволь
— эллиптическая кривая над конечным полем
, то есть,
.
-торсионная группа
над
изоморфен
если
, и чтобы
или
если
. Отсюда и степень
равно либо
,
, или 0.
Рене Шуф заметил, что работа по модулю
Полином деления позволяет работать со всеми
-точки кручения одновременно. Это широко используется в алгоритме Шуфа для подсчета точек на эллиптических кривых.
- А. Энге: Эллиптические кривые и их приложения в криптографии: Введение . Kluwer Academic Publishers, Дордрехт, 1999.
- Н. Коблиц: Курс теории чисел и криптографии , Тексты для аспирантов по математике. № 114, Springer-Verlag, 1987. Второе издание, 1994 г.
- Мюллер: Вычисление количества точек эллиптических кривых над конечными простыми телами . Магистерская диссертация. Саарский университет, Саарбрюккен, 1991 г.
- Г. Мюзикер: Алгоритм Шуфа для подсчета очков на
. Доступно по адресу https://www-users.cse.umn.edu/~musiker/schoof.pdf. - Шуф: Эллиптические кривые над конечными полями и вычисление квадратных корней mod p . Математика. Comp., 44(170):483–494, 1985. Доступно по адресу http://www.mat.uniroma2.it/~schoof/ctpts.pdf.
- Р. Шуф: Подсчет точек на эллиптических кривых над конечными полями . Дж. Теория. Nombres Bordeaux 7:219–254, 1995. Доступно по адресу http://www.mat.uniroma2.it/~schoof/ctg.pdf.
- Л. К. Вашингтон: Эллиптические кривые: теория чисел и криптография . Чепмен и Холл/CRC, Нью-Йорк, 2003 г.
- Дж. Сильверман: Арифметика эллиптических кривых , Springer-Verlag, GTM 106, 1986.