Research On Legendre And Jacobi Sequences

Designing a good pseudo-random sequence (PSG) for key is always a hot research topic for stream ciphers. The major randomness measurements for PSG are long period, large linear span and low-level correlation. PSG with two-level auto correlation has very important applications in wireless communication systems, stream ciphers, multi-user radar systems, sonar systems and so on. Legendre and Jacobi sequences are based on quadratic residue theories. They have good auto correlation, high linear complexity and proven security. So Legendre and Jacobi sequences are good and complete random sequences, and researches on them have big theoretical and practical meaning.This paper describes the research conditions about Legendre and Jacobi sequences both in and out of China, and gives a comprehensive introduction of their random properties as well. In 2000, Hu defined generalized Legendre sequences and two classes of generalized Jacobi sequences, and also discussed their linear complexity under some situations. In this paper, we utilize the theory and methods of finite domain and number theory to prove the linear complexity and minimal polynomial of generalized Legendre sequences when b is natural arrangement, and then generalize the result to Lλb,αband b r.We prove the auto correlation and merit factor of generalized Legendre sequences and two classes of generalized Jacobi sequences when b is some particular arrangements. We also discuss their sampling properties, and then make a systematic conclusion about all the research results nowadays about these sequences.