關于一些二進制數列的族復雜度和互相關測度

梁嘉怡,王曉瑛

(西北大學數學學院,陜西 西安 710127)

1 引言

隨著計算機和互聯網的普及,傳統的業務處理與服務等日常活動已經不能滿足日益發展的新時代的需要.目前人類已經進入了信息時代,許多問題都可以通過計算機和網絡等工具來實現,此時就更需要一個安全的網絡環境.偽隨機二進制數列已經成為密碼學中的一個基本工具,并有著廣泛的應用(見文獻[1-3]).

為了衡量二進制數列的性質,人們引入了各種偽隨機測度.例如,f-復雜度[4],互相關測度[5],一致分布測度和高階相關測度[6],等等.文獻 [4]給出了f-復雜度(f-complexity)的定義.

定義 1.1設F是一族長度為N的二進制數列EN∈{?1,+1}N.族F的f-復雜度C(F)是指最大的整數j≥0,使得對任意的1≤i1

2 定理1.1的證明

3 定理1.2的證明