On the linear complexity of Legendre-Sidelnikov sequences

作     者：Su, Ming 

作者机构：Nankai Univ Dept Comp Sci Tianjin 300071 Peoples R China 

出 版 物：《DESIGNS CODES AND CRYPTOGRAPHY》 (设计、编码与密码学)

年 卷 期：2015年第74卷第3期

页      面：703-717页

核心收录：

学科分类：07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

基　　金：National Natural Science Foundation of China NSFC [61070014, 61373018] 

主　　题：Linear complexity Legendre-Sidelnikov sequence Legendre sequence Sidelnikov sequence Cryptography 

摘      要：Linear complexity is an important cryptographic index of sequences. We study the linear complexity of -periodic Legendre-Sidelnikov sequences, which combine the concepts of Legendre sequences and Sidelnikov sequences. We get lower and upper bounds on the linear complexity in different cases, and experiments show that the upper bounds can be attained. Remarkably, we associate the linear complexity of Legendre-Sidelnikov sequences with some famous primes including safe prime and Fermat prime. If is a primitive root modulo , and is a safe prime greater than 7, the linear complexity is the period if;if , and if . If is a Fermat prime, the linear complexity is the period if , and if . It is very interesting that the Legendre-Sidelnikov sequence has maximal linear complexity and is balanced if we choose to be some safe prime.