Date Available

4-28-2016

Year of Publication

2016

Document Type

Doctoral Dissertation

Degree Name

Doctor of Philosophy (PhD)

College

Engineering

Department/School/Program

Computer Science

Advisor

Dr. Andrew Klapper

Abstract

Random numbers (in one sense or another) have applications in computer simulation, Monte Carlo integration, cryptography, randomized computation, radar ranging, and other areas. It is impractical to generate random numbers in real life, instead sequences of numbers (or of bits) that appear to be ``random" yet repeatable are used in real life applications. These sequences are called pseudorandom sequences. To determine the suitability of pseudorandom sequences for applications, we need to study their properties, in particular, their statistical properties. The simplest property is the minimal period of the sequence. That is, the shortest number of steps until the sequence repeats. One important type of pseudorandom sequences is the sequences generated by feedback with carry shift registers (FCSRs). In this dissertation, we study statistical properties of N-ary FCSR sequences with odd prime connection integer q and least period (q-1)/2. These are called half-ℓ-sequences. More precisely, our work includes:

  • The number of occurrences of one symbol within one period of a half-ℓ-sequence;
  • The number of pairs of symbols with a fixed distance between them within one period of a half-ℓ-sequence;
  • The number of triples of consecutive symbols within one period of a half-ℓ-sequence.

In particular we give a bound on the number of occurrences of one symbol within one period of a binary half-ℓ-sequence and also the autocorrelation value in binary case. The results show that the distributions of half-ℓ-sequences are fairly flat. However, these sequences in the binary case also have some undesirable features as high autocorrelation values. We give bounds on the number of occurrences of two symbols with a fixed distance between them in an ℓ-sequence, whose period reaches the maximum and obtain conditions on the connection integer that guarantee the distribution is highly uniform.

In another study of a cryptographically important statistical property, we study a generalization of correlation immunity (CI). CI is a measure of resistance to Siegenthaler's divide and conquer attack on nonlinear combiners. In this dissertation, we present results on correlation immune functions with regard to the q-transform, a generalization of the Walsh-Hadamard transform, to measure the proximity of two functions. We give two definitions of q-correlation immune functions and the relationship between them. Certain properties and constructions for q-correlation immune functions are discussed. We examine the connection between correlation immune functions and q-correlation immune functions.

Digital Object Identifier (DOI)

http://dx.doi.org/10.13023/ETD.2016.159

Download

Share

COinS