О пермутационных малочленах над конечными полями и кольцами вычетов

Пермутационные полиномы над конечным полем или кольцом – это полиномы, осуществляющие биекции соответствующего кольца или поля. Полиномиальные биекции образуют группу относительно суперпозиции, которая в случае конечного поля является симметрической группой. Интерес к пермутационным полиномам во многом вызван их возможными применениями в криптографии. Наиболее известный криптографический протокол RSA основан на биекциях, осуществляемых простейшими пермутационными многочленами – мономами. В докладе будет рассказано о перестановочныx малочленах, в частности о биномах и триномах над конечными полями, описаны некоторые известные серии таких полиномов. Будет рассмотрена задача построения таких многочленов и алгоритмическая сложность нахождения обратных функций к ним. Обсуждается возможность применения таких многочленов в качестве функций шифрования. Также будет рассказано о разбиении на циклы для полиномиальных перестановок.