Для эффективной реализации быстрого преобразования Фурье требуется, чтобы n разлагалось на как можно меньшие множители. Это требование приводит к тому, что p-1 должно разлагаться на как можно меньшие множители. Идеальный вариант, когда p-1 является степенью двойки.
Утверждение. Если p – простое и p-1 степень двойки, то .
Доказательство. Пусть не так, то есть , где r - нечетное число, большее 1. Но тогда p делится на число , что противоречит простоте p.
Таким образом, простые числа, для которых p-1 степень двойки, имеют вид .
Учитывая организацию памяти ЭВМ, такой выбор простого числа приводит либо к неэкономному использованию памяти, либо к дополнительным сложностям при программировании.
Лучше всего выбирать максимально возможный модуль p, убирающийся в отведенные ему ячейки памяти, и в тоже время p-1 должен раскладываться на как можно меньшие множители. Ниже приведена таблица простых чисел не превосходящих вида с первообразными корнями.
Простое число
Первообразный
корень
Простое число
Первообразный
корень
Видно, что простых чисел вида достаточно много, и распределены они достаточно равномерно. Из таблицы видно, что отношение между двумя следующими друг за другом простыми числами такого вида не превосходит 2.
Из простых чисел вида приведем только наибольшее число, убирающееся в тип данных longint, это - 1036800001, первообразный корень - 7.
.
, где r - нечетное число, большее 1. Но тогда p делится на число 
, что противоречит простоте p.
.
вида 
с первообразными корнями.
достаточно много, и распределены они достаточно равномерно. Из таблицы видно, что отношение между двумя следующими друг за другом простыми числами такого вида не превосходит 2.
приведем только наибольшее число, убирающееся в тип данных longint, это - 1036800001, первообразный корень - 7.