Перестановочные многочлены малой длины над простыми конечными полями
Ключевые слова:
перестановочные многочлены, конечные поля, криптография с открытым ключомАннотация
Постановка проблемы: перестановочным многочленом над конечным полем называется многочлен, реализую-
щий перестановку элементов конечного поля. В настоящее время не известно эффективных критериев для определе-
ния перестановочных многочленов над конечными полями даже для многочленов малой длины, состоящих из несколь-
ких мономов. Для построения таких критериев нами была поставлена задача о построении таблиц перестановочных
многочленов, зависимости в которых можно использовать для нахождения новых серий перестановочных многочленов,
а также для построения эффективных критериев таких многочленов. Методы: реализация алгоритма перебора на С++,
численные эксперименты в системе компьютерной алгебры Sage, вычисление порядков групп перестановок в системе
компьютерной алгебры GAP. Результаты: разработан метод перечисления перестановочных многочленов, работающий
для многочленов малой длины, на основе которого были вычислены таблицы перестановочных пятичленов для простых
конечных полей характеристики до 100. Полученные таблицы пятичленов были сравнены с таблицами перестановочных
четырехчленов, трехчленов и двучленов над конечными полями из предыдущих работ. Исследование общих зависимо-
стей и сравнение с предыдущей гипотезой о классификации многочленов меньшей длины позволили сформулировать
гипотезу об общей классификации перестановочных многочленов с не более чем пятью членами. Также было прове-
дено исследование статистических свойств случайных перестановок, соответствующих случайному выбору равнорас-
пределенных случайных перестановочных многочленов c фиксированным количеством мономов. Было показано, что
получающееся распределение на перестановках уже не является равномерно распределенным. Практическая значи-
мость: сформулированные гипотезы о классификации перестановочных многочленов малой длины являются шагом к
построению полной доказанной классификации перестановочных многочленов, а также могут быть использованы при
построении криптографических протоколов с открытым ключом на основе перестановочных многочленов.
