Testing stream ciphers by finding the longest substring of a given density

Abstract

Given a string x[1..n] drawn from the alphabet {0,1}, and a rational density parameter 0 ≤ θ ≤ 1, this paper considers algorithms for finding the longest substring of x with density θ. That is, if the length of the substring is m, the number of one-bits in the substring is exactly θ×m. It is surprisingly difficult to devise an algorithm that has worst case time less than the obvious brute-force algorithm's O(n2). We present three new approaches to reducing the running time, and an algorithm that solves the problem in O(nlogn) expected time. We then apply the new algorithm, as well as an empirical estimate of the lim-sup and the lim-inf of a centred statistic which is expected to obey a law o..