Abstract: This paper analyzes the computational complexity of the algorithm for computing the XOR differential probability of addition modulo 2n. With the idea of time-memory trade-off, by computing and storing the products of matrices algorithm in advance, and replacing the computing of matrices products with looking up tables, it improves the computing algorithm. The computational complexity of new algorithm is less than 7.7% times of that of the existing method.

Key words: additional modulo 2n, XOR differential probability, fast computing

摘要： 分析模2n加变换的异或差分概率计算算法的计算复杂性，利用以空间换时间的思想，将该算法中的矩阵乘积运算预先计算并予以存储，从而以查表运算替代多个矩阵乘积运算等方法对模2n加变换的异或差分概率计算算法进行改进，改进后算法的计算复杂性小于现有方法计算复杂性的7.7%。

关键词: 模2n加, 异或差分概率, 快速计算

CLC Number: 

• TN918.1