密码学报（中英文）2025，Vol.12Issue(4)：752-765,14.DOI:10.13868/j.cnki.jcr.000792
基于CUDA并行的线性复杂度快速检测方法
CUDA-Based Parallel Algorithm for Fast Linear Complexity Test
摘要
Abstract
The linear complexity test is a crucial tool for assessing the randomness quality of a random number generator's output.It also serves as an effective metric to evaluate the randomness of binary sequences.Nevertheless,the Berlekamp-Massey algorithm,which is commonly used in this test,suffers from high computational complexity,leading to the low efficiency of the test compared to other randomness detection methods.Especially,as the length of samples increases,the test efficiency is particularly prominent,and gradually becomes a bottleneck restricting its applicability.This study focuses on addressing the inefficiency problem of linear complexity testing of binary sequences and pro-poses a parallel optimization method based on the NVIDIA CUDA technology to achieve fast detection of linear complexity.A fast shift method is introduced into the improved Berlekamp-Massey algorithm and a parallel detection strategy is proposed for binary sequence linear complexity in combination with the NVIDIA CUDA model.By parallelizing the Berlekamp-Massey algorithm,thread synchronization is designed and implemented to achieve parallelism between thread blocks through cooperation of the deeply parallel Berlekamp-Massey algorithm.Additionally,the detection process is further optimized by adjusting thread configuration parameters and introducing the CUDA collaboration group with warp shuffle mechanism.Experimental results demonstrate that the optimized algorithm proposed in this study achieves a significant speedup of up to approximately 20 000 times compared to the NIST-STS version of linear complexity test and a stable speedup of up to approximately 3-3.5 times compared to the fastest parallel linear complexity test methods.关键词
随机性检测/线性复杂度检测/Berlekamp-Massey算法/NVIDIA CUDA/GPU并行Key words
randomness/linear complexity test/Berlekamp-Massey algorithm/NVIDIA CUDA/GPU parallelization分类
信息技术与安全科学引用本文复制引用
付一方,范丽敏,陈华,陈东昱..基于CUDA并行的线性复杂度快速检测方法[J].密码学报（中英文）,2025,12(4):752-765,14.基金项目
国家重点研发计划(2020YFA0309704) （2020YFA0309704）
国家密码科学基金(2025NCSF02057)National Key Research and Development Program of China(2020YFA0309704) （2025NCSF02057）
National Cryptologic Science Fund of China(2025NCSF02057) （2025NCSF02057）
