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

梁嘉怡,王曉瑛

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

1 引言

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

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

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

2 定理1.1的證明

3 定理1.2的證明