周期为2^n，u2^v的二元序列线性复杂度的GPU并行算法
omputation of the Linear Complexity of 2^n&u2^v-Periodic Sequence on CUDA
对于周期为N(2^n)的二元序列，Games and Chan提出了复杂度为O(N)的线性复杂度计算算法，改进了原有的计算一般序列复杂度的Berlekamp-Massey算法。Wilfried Meidl进一步提出了针对序列周期为u2^v的算法，通过分解成若干个周期为2^v序列，来降低计算复杂度。针对这类特殊的二元周期序列，上述算法的计算过程可以描述为迭代的字节异或运算，基于CUDA（Compute Unified Device Architecture）计算平台实现部分计算步骤的GPU（Graphics Processing Units）并行化，大幅度提高了线性复杂度的计算效率。实验比较了串行算法、基于机群的并行算法和CUDA算法，结果显示CUDA平台计算效率比其他环境提高了近一个数量级，实验表明CUDA平台适合这类特殊序列的线性复杂度计算。
Games and Chan gave a fast algorithm determining the linear complexity of a period N(2^n) binary sequence with time complexity O(N), which improves the common Berlekamp-Massey algorithm. Also, Meidl proposed a revised algorithm for u2^v-periodic sequence by dividing a sequence into u 2^v-periodic sub-sequences. We apply the algorithms to some parallel platforms because some part of calculations can be parallelized, and transform the computation of the linear complexity into bytes XORs. With several groups of serial, cluster, and CUDA implementations, our results show that the CUDA implementation is more efficient compared with others.
王刚、刘晓光、杨云鹏、苏明
计算技术、计算机技术
流密码周期序列线性复杂度Games-Chan算法UDA
Stream cipherPeriodic sequenceLinear complexityGames-Chan algorithmCUDA
王刚,刘晓光,杨云鹏,苏明.周期为2^n，u2^v的二元序列线性复杂度的GPU并行算法[EB/OL].(2011-12-05)[2025-08-04].http://www.paper.edu.cn/releasepaper/content/201112-97.点此复制
评论