首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号