Pseudorandom Sequences

Sequences, which are generated by deterministic algorithms to simulate truly random sequences are said to be pseudorandom (PR). Our main aim is to find PR sequences with some specific properties that foster their use in cryptography and in quasi-Monte Carlo methods. Various quality measures for randomness of PR sequences are in use. One should note here that the hierarchy among them varies according to the type of problem where PR sequences are needed. For example, if one wishes to employ a quasi-Monte Carlo method one should make sure that the PR sequences in use are `distributed uniformly`. On the other hand `unpredictability` is often the most desirable property for cryptographic applications. We are going to analyze the following randomness measures - linear complexity and related measures - correlation and distribution measures of the following classes of PR sequences - binary sequences like Legendre sequence and related sequences - nonlinear sequences over finite fields and residue class rings. We use mainly number theoretic methods including - exponential sums and character sums - equations over finite fields and residue class rings - cyclotomy. The proposed project is meant as a continuation of the very successful project S8313 (2002-2005) entitled Number Theoretic Methods in Cryptography and Pseudorandom Number Generation.

Sequences, which are generated by deterministic algorithms to simulate truly random sequences are said to be pseudorandom (PR). Our main aim is to find PR sequences with some specific properties that foster their use in cryptography and in quasi-Monte Carlo methods. Various quality measures for randomness of PR sequences are in use. One should note here that the hierarchy among them varies according to the type of problem where PR sequences are needed. For example, if one wishes to employ a quasi-Monte Carlo method one should make sure that the PR sequences in use are `distributed uniformly`. On the other hand `unpredictability` is often the most desirable property for cryptographic applications. We are going to analyze the following randomness measures: linear complexity and related measures correlation and distribution measures of the following classes of PR sequences: binary sequences like Legendre sequence and related sequences nonlinear sequences over finite fields and residue class rings. We use mainly number theoretic methods including exponential sums and character sums equations over finite fields and residue class rings cyclotomy. The proposed project is meant as a continuation of the very successful project S8313 (2002-2005) entitled Number Theoretic Methods in Cryptography and Pseudorandom Number Generation.