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

• 作 者: 何大可 王建波
• 机 构: 西南交通大学,信息安全与国家计算网格实验室,成都,610031
• 出 处: 第七届全国并行计算学术交流会
• 发表日期: 2003年7期
• 关键词: Markov密码 转移概率矩阵 矩阵特征值 并行算法 随机矩阵 迭代法

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