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

扫码查看

原文链接

NETL

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

作者：

何大可、王建波

展开 >

作者单位：

西南交通大学信息安全与国家计算网格实验室(成都)

关键词：

Markov密码转移概率矩阵并行算法随机矩阵

主办单位：

中科院计算机网络信息中心

会议名称：

国际并行算法与计算环境专题讨论会

会议时间：

2003-10-01

会议地点：

香港

会议母体文献：

国际并行算法与计算环境专题讨论会论文集

页码：

168-176

出版时间：

2003