生成可逆模m矩阵的方法和装置.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN108509386A(43)申请公布日2018.09.07(21)申请号201810353989.2(22)申请日2018.04.19(71)申请人武汉轻工大学地址430023湖北省武汉市东西湖区常青花园学府南路68号(72)发明人王防修(74)专利代理机构深圳市世纪恒程知识产权代理事务所44287代理人胡海国(51)Int.Cl.G06F17/16(2006.01)权利要求书3页说明书18页附图4页(54)发明名称生成可逆模m矩阵的方法和装置(57)摘要本发明公开了一种生成可逆模m矩阵的方法和装置。本发明的结合高斯消去算法和模m矩阵的特性，进而得出更快生成可逆模m矩阵的方法，本发明利用模m矩阵的行列式与模m的互质性，从大量随机产生的模m矩阵中，可以快速淘汰不满足互质性的矩阵，保留满足互质性的矩阵，进而能够精确快速地生成一个可逆模m矩阵，通用性好。CN108509386ACN108509386A权利要求书1/3页1.一种生成可逆模m矩阵的方法，其特征在于，所述方法包括：接收用户输入的矩阵阶数n，产生n2个整数，基于所产生的n2个整数生成模m矩阵，将所产生的n2个整数作为所述模m矩阵的矩阵元素；对所述模m矩阵的矩阵元素进行遍历，在遍历到的目标矩阵元素与数值m互质时，认定所述模m矩阵为可逆模m矩阵。2.如权利要求1所述的方法，其特征在于，所述接收用户输入的矩阵阶数n，产生n2个整数，基于所产生的n2个整数生成模m矩阵，具体包括：2随机生成n个值在0到m-1之间的整数aij，其中，i为1到n之间的整数，j为1到n之间的整数；2(0)根据生成的n个整数aij创建所述模m矩阵A，其中，n表示所述模m矩阵的阶数n，表示所述模m矩阵的第i行第j列的矩阵元素，i表示所述模m矩阵的行，j表示所述模m矩阵的列。3.如权利要求2所述的方法，其特征在于，所述创对所述模m矩阵的矩阵元素进行遍历，在遍历到的目标矩阵元素与数值m互质时，认定所述模m矩阵为可逆模m矩阵，具体还包括：在所述模m矩阵中的第i行且i≠1第1列中至少存在一个满足时，将所述模m矩阵A(0)的第i行元素和第1行元素互易位置，以使得当前模m矩阵的矩阵元素与数值m互质，其中，表示模m矩阵A(0)的第i行第一列矩阵元素与数值m互质；确定所述矩阵元素的逆元通过公式将所述逆元遍乘所述模m矩阵A(0)的第1行除第1列的矩阵元素；通过公式将所述模m矩阵A(0)的第i行减去变换后的第1行的ai1倍，获得其中，重复执行上述步骤k-1次之后，使得当前矩阵A(k-2)变成2CN108509386A权利要求书2/3页其中第k次步骤为：从矩阵A(k-1)的第1列查找是否存在与数值m互质的矩阵元素，若找到的矩阵元素不是则将该矩阵元素所在的行与所在的行位置互换以使得新的与数值m互素；或在不存在与数值m互质的矩阵元素时，返回所述确定并重新生成所述模m矩阵的矩阵元素的步骤；通过公式将的逆元乘以A(k-1)的第1行除以外的矩阵元素；通过公式将A(k-1)的第i行减去变换后的第1行的倍，以获得其中重复执行上述步骤n-1步之后，以使得当前模m矩阵变为在矩阵元素与数值m互质时，认定所述当前模m矩阵为可逆模m矩阵。4.如权利要求3所述的方法，其特征在于，所述在矩阵元素与数值m互质时，认定所述当前模m矩阵为可逆模m矩阵之后，还包括：通过所述当前模m矩阵对所述待处理数据进行加密，以生成加密数据。5.如权利要求4所述的方法，其特征在于，所述通过所述当前模m矩阵对所述待处理数据进行加密，以生成加密数据之后，还包括：求取所述模m矩阵的逆，通过所述模m矩阵的逆对所述加密数据进行解密，获得所述待处理数据。6.如权利要求5所述的方法，其特征在于，所述求取所述模m矩阵的逆，通过所述模m矩阵的逆对所述加密数据进行解密，获得所述待处理数据，具体包括：-1-1设AY＝B，Y＝(yij)n×n＝A，B＝(bij)n×n＝En，A＝(aij)n×n表示所述模m矩阵，A表示所述模m矩阵的逆；AY＝B表征为A(0)Y＝B(0)，A(0)和B(0)的矩阵元素分别记为所述目标终端通过公式将所述矩阵A(0)的第1行的3CN108509386A权利要求书3/3页矩阵元素遍乘所述逆元从所述矩阵A(0)的其它行中消去第1列的矩阵元素；以及将所述矩阵B(0)的第1行的矩阵元素遍乘所述逆元从所述矩阵B(0)的其它行中消去第1列的矩阵元素；所述目标终端通过公式将所述矩阵A(0)的第(0)i行的矩阵元素分别减去第1行的ai1倍，并将所述矩阵B的第i行的矩阵元素分别减去第1行的ai1倍；重复执行以上步骤k-1次，生成形式矩阵从所述形式矩阵的中选取与所述数值m互质矩阵元素；在k≠1时，将所述形式矩阵中的第i行