Hadamard MDS矩阵的一种快速搜索算法  

A Fast Search Algorithm of Hadamard MDS Matrices

作　　者：王石 李云青 徐运阁 曾祥勇 WANG Shi;LI Yun-Qing;XU Yun-Ge;ZENG Xiang-Yong(Hubei Key Laboratory of Applied Mathematics,Faculty of Mathematics and Statistics,Hubei University,Wuhan 430062,China)

机构地区：[1]湖北大学数学与统计学学院应用数学湖北省重点实验室,武汉430062

出　　处：《密码学报》2022年第3期560-578,共19页Journal of Cryptologic Research

基　　金：武汉市科技局应用基础前沿项目(2020010601012189);国家自然科学基金(61761166010)。

摘　　要：本文提出了一种Hadamard MDS矩阵的快速搜索算法.首先,给出了一般类型MDS矩阵的判别方法,其主要思想是利用低阶子方阵的行列式计算高阶子方阵的行列式,从而降低每个子方阵行列式的计算复杂度.其次,对于4阶和8阶Hadamard MDS矩阵,给出了更高效的判别方法.当m(m=4,8)阶Hadamard矩阵的任意i(i≤m/2)阶子方阵均满秩时,即可判定该矩阵为MDS矩阵.利用该判别方法,可以实现对有限域F_(2)^(4)和F_(2)^(6)上4阶和8阶Hadamard MDS矩阵的穷举搜索.该方法还可以用于寻找更大的有限域F_(2)^(n)(n≤16)中异或数最低的Hadamard MDS矩阵.最后,本文建立了有限交换环上4阶Hadamard MDS矩阵与有限域上8阶Hadamard MDS矩阵的联系,并利用此联系进一步优化了8阶对合Hadamard MDS矩阵的搜索算法.In this paper,a fast searching algorithm of Hadamard MDS matrices is proposed.First,a new method to judge MDS properties is introduced.The main idea is to use determinants of lowerorder submatrices to compute determinants of higher-order submatrices such that the computation complexity for verifying an MDS matrix can be effectively reduced.For Hadamard MDS matrices of orders 4 and 8,a more efficient method is given.An m-order Hadamard matrix is an MDS matrix if and only if all of its i-order submatrices are full rank,where i≤m/2 and m=4,8.In this way,all the 4×4 and 8×8 Hadamard MDS matrices over the finite fields ■or ■can be found.In addition,the Hadamard MDS matrices with the fewest XOR gates can also be obtained when n≤16.Finally,a relation between the 4×4 Hadamard MDS matrices over a finite commutative ring and 8×8 Hadamard MDS matrices over a finite field is established.By the relation,a more efficient searching method for 8×8 Hadamard involutory MDS matrices is given.

关 键 词：HADAMARD矩阵 MDS矩阵 代数余子式 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]