求双随机矩阵第二大模特征值的一种并行算法

摘要

本文探讨IDEA密码的缩小模型IDEA(16)的转移概率矩阵П0第二大(模)特征值的计算方法,这里的П0是一个65535阶非对称实方阵.首先,使用降维法将与最大特征值相关的子空间分离出去,由П0得到65534阶矩阵П.然后利用迭代法计算П的最大特征值--设计了并行算法来实现它.该算法的时间复杂度比QR算法的O(8n3)大约低半个数量级.以上算法对于类似密码的分析同样实用,比如HDEA(ZL94116286.9).