Search

Pseudo-random sequences are ubiquitous in modern electronics and information technology. High speed generators of such sequences play essential roles in various engineering applications, such as stream ciphers, radar systems, multiple access systems, and quasi-Monte-Carlo simulation. Given a short prefix of a sequence, it is undesirable to have an efficient algorithm that can synthesize a generator which can predict the whole sequence. Otherwise, a cryptanalytic attack can be launched against the system based on that given sequence. Linear feedback shift registers (LFSRs) are the most widely studied pseudorandom sequence generators. The LFSR synthesis problem can be solved by the Berlekamp-Massey algorithm, by constructing a system of linear equations, by the extended Euclidean algorithm, or by the continued fraction algorithm. It is shown that the linear complexity is an important security measure for pseudorandom sequences design. So we investigate lower bounds of the linear complexity of different kinds of pseudorandom sequences. Feedback with carry shift registers (FCSRs) were first described by Goresky and Klapper. They have many good algebraic properties similar to those of LFSRs. FCSRs are good candidates as building blocks of stream ciphers. The FCSR synthesis problem has been studied in many literatures but there are no FCSR synthesis algorithms for multi-sequences. Thus one of the main contributions of this dissertation is to adapt an interleaving technique to develop two algorithms to solve the FCSR synthesis problem for multi-sequences. Algebraic feedback shift registers (AFSRs) are generalizations of LFSRs and FCSRs. Based on a choice of an integral domain R and π ∈ R, an AFSR can produce sequences whose elements can be thought of elements of the quotient ring R/(π). A modification of the Berlekamp-Massey algorithm, Xu's algorithm solves the synthesis problem for AFSRs over a pair (R, π) with certain algebraic properties. We propose two register synthesis algorithms for AFSR synthesis problem. One is an extension of lattice approximation approach but based on lattice basis reduction and the other one is based on the extended Euclidean algorithm.

The main theme of this thesis is to develop de Finetti type theorems in noncommutative probability. In noncommutative area, there are independence relations other than classi- cal independence, e.g. Voiculescu’s free independence, Boolean independence and Muraki’s monotone independence. Free analogues of de Finetti type theorems were discovered by Ko ̈stler and Speicher and were developed by Banica, Curran and Speicher. Here, we will define noncommutative distributional symmetries for Boolean and monotone independence and we will prove de Finetti type theorems for them. These distributional symmetries are defined via coactions of quantum structures including Woronowicz C∗-algebra and So ltan’s quantum families of maps. We show that the joint distribution of an infinite sequence of noncommutative random variables satisfies boolean exchangeability is equivalent to the fact that the sequence of the random variables is identically distributed and boolean independent with respect to the conditional expectation onto its tail algebra. Then, we define noncom- mutative versions of spreadability and show Ryll-Nardzewski type theorems for monotone independence and boolean independence. We will show that, roughly speaking, an infinite bilateral sequence of random variables is monotonically(boolean) spreadable if and only if the variables are identically distributed and monotone(boolean) with respect to the conditional expectation onto its tail algebra. In the end of this thesis, we will prove general de Finetti theorems for classical, free and boolean independence. Our general de Finetti theorems work for non-easy quantum groups, which generalizes a recent work of Banica, Curran and Spe- icher. For infinite sequences, we determine maximal distributional symmetries which means the corresponding de Finetti theorem fails if the sequence satisfies more symmetries other than the maximal one.