The construction of circulant matrices related to MDS matrices

Цель данной работы — предложить метод построения таких циркулянтных матриц, которые могут быть MDS-матрицами, используемыми в криптографии. Мы рассматриваем так называемые би-регулярные циркулянтные матрицы и, кроме того, налагаем на них дополнительные ограничения с тем, чтобы они имели максимальное число вхождений некоторого элемента и минимальное количество различных элементов. Интерес к би-регулярным матрицам обусловлен тем, что любая MDS-матрица обязательно является би-регулярной, а дополнительные ограничения на элементы матриц позволяют эффективнее реализовывать матрично-векторные операции с использованием таких матриц. Полученные результаты включают верхнюю границу числа вхождений некоторого элемента, при котором циркулянтная матрица остаётся би-регулярной, а также необходимые и достаточные условия би-регулярности циркулянтной матрицы. Кроме того, описан эффективный алгоритм проверки би-регулярности циркулянтной матрицы. С его помощью построены шаблоны би-регулярных циркулянтных матриц порядка до 31 с максимальным числом вхождений некоторого элемента и установлено отсутствие би-регулярных циркулянтных матриц (и следовательно, MDS-матриц) порядка 32 с более чем пятью вхождениями одного элемента.