Expected values for the rational complexity of finite binary sequences |
| |
Authors: | Tian Tian Wen-Feng Qi |
| |
Affiliation: | 1.Department of Applied Mathematics,Zhengzhou Information Science and Technology Institute,Zhengzhou,People’s Republic of China;2.State Key Laboratory of Information Security,Institute of Software, Chinese Academy of Sciences,Beijing,People’s Republic of China |
| |
Abstract: | 2-Adic complexity plays an important role in cryptology. It measures the difficulty of outputting a binary sequence using a feedback with carry shift register. This paper studies the 2-adic complexity of finite sequences by investigating the corresponding rational complexity whose logarithm to the base 2 is just equal to the 2-adic complexity. Experiments show that the logarithm to the base 2 of the expected values for rational complexity is a good approximation to the expected values for the 2-adic complexity. Both a nontrivial lower bound and a nontrivial upper bound on the expected values for the rational complexity of finite sequences are given in the paper. In particular, the lower bound is much better than the upper bound. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|