Pseudorandomness of binary sequences derived from linear recursions

详细信息    查看全文

• 作者：László Mérai
• 关键词：Pseudorandomness ; Pseudorandom measures ; Linear recursion ; Primary 11K45
• 刊名：Periodica Mathematica Hungarica
• 出版年：2015
• 出版时间：September 2015
• 年：2015
• 卷：71
• 期：1
• 页码：64-77
• 全文大小：441 KB
• 参考文献：1.N. Alon, Y. Kohayakawa, C. Mauduit, C.G. Moreira, V. R?dl, Measures of pseudorandomness for finite sequences: typical values. Proc. Lond. Math. Soc. 95, 778-12 (2007)MathSciNet View Article
  2.J. Folláth, Construction of pseudorandom binary sequences using additive characters over \(GF(2^k)\) . Period. Math. Hung. 57(1), 73-1 (2008)View Article
  3.J. Folláth, Construction of pseudorandom binary sequences using additive characters over \(GF(2^k)\) II. Period. Math. Hung. 60(2), 127-35 (2010)View Article
  4.K. Gyarmati, A. Peth?, A. Sárk?zy, On linear recursion and pseudorandomness. Acta Arith. 118(4), 359-74 (2005)MathSciNet View Article
  5.C. Mauduit, J. Rivat, A. Sárk?zy, Construction of pseudorandom binary sequences using additive characters. Monatshefte Math. 141(3), 197-08 (2004)View Article
  6.C. Mauduit, A. Sárk?zy, On finite pseudorandom binary sequences I: measures of pseudorandomness, the Legendre symbol. Acta Arith. 82, 365-77 (1997)MathSciNet
  7.L. Mérai, Construction of pseudorandom binary lattices based on multiplicative characters. Period. Math. Hung. 59, 43-1 (2009)View Article
  8.G. I. Perel’muter, On certain character sums. Uspehi Mat. Nauk 18 no. 2 (110), 145-49 (1963)
  
• 作者单位：László Mérai (1) (2)
  
  1. Department of Computer Algebra, E?tv?s Loránd University, Pázmány Péter sétány 1/C, Budapest, 1117, Hungary
  2. Johann Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences, Altenberger Strasse 69, 4040, Linz, Austria
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Sciences
  Mathematics
  
• 出版者：Akad茅miai Kiad贸, co-published with Springer Science+Business Media B.V., Formerly Kluwer Academic
• ISSN：1588-2829

文摘

In this paper we study the pseudorandomness of finite binary sequences derived from linear recursions. We show, that the well-distribution measures of these sequences are small. Furthermore we also show that the correlation measures of these sequences are small for small correlation orders, but if the order of the correlation is greater than the order of the linear recursion, then the correlation can be large.