On Lempel-Ziv complexity of sequences

Date

2006-01-01

Author

Doğanaksoy, Ali

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

122
views

0
downloads

We derive recurrences for counting the number a(n, r) of sequences of length n with Lempel-Ziv complexity r, which has important applications, for instance testing randomness of binary sequences. We also give algorithms to compute these recurrences. We employed these algorithms to compute a(n, r) and expected value, EPn, of number of patterns of a sequence of length n, for relatively large n. We offer a randomness test based on the algorithms to be used for testing randomness of binary sequences. We give outputs of the algorithms for some n. We also provide results of the proposed test applied to the outputs of contestant stream ciphers of ECRYPT's eSTREAM.

URI

https://hdl.handle.net/11511/53306

Journal

SEQUENCES AND THEIR APPLICATIONS - SETA 2006

Collections

Department of Mathematics, Article

Suggestions

OpenMETU
Core

On multiplication in finite fields Cenk, Murat; Özbudak, Ferruh (2010-04-01) We present a method for multiplication in finite fields which gives multiplication algorithms with improved or best known bilinear complexities for certain finite fields. Our method generalizes some earlier methods and combines them with the recently introduced complexity notion (M) over cap (q)(l), which denotes the minimum number of multiplications needed in F-q in order to obtain the coefficients of the product of two arbitrary l-term polynomials modulo x(l) in F-q[x]. We study our method for the finite ...
MODIFICATIONS OF KNUTH RANDOMNESS TESTS FOR INTEGER AND BINARY SEQUENCES Koçak, Onur Ozan; SULAK, FATİH; Doğanaksoy, Ali; Uğuz, Muhiddin (2018-01-01) Generating random numbers and random sequences that are indistinguishable from truly random sequences is an important task for cryptography. To measure the randomness, statistical randomness tests are applied to the generated numbers and sequences. Knuth test suite is the one of the first statistical randomness suites. This suite, however, is mostly for real number sequences and the parameters of the tests are not given explicitly.
Efficient subquadratic space complexity binary polynomial multipliers based on block recombination Cenk, Murat; Negre, Christophe (2014-09-01) Some applications like cryptography involve a large number of multiplications of binary polynomial. In this paper we consider two, three and four-way methods for parallel implementation of binary polynomial multiplication. We propose optimized three and four-way split formulas which reduce the space and time complexity of the best known methods. Moreover, we present a block recombination method which provides some further reduction in the space complexity of the considered two, three and four-way split mult...
NEW EFFICIENT CHARACTERISTIC THREE POLYNOMIAL MULTIPLICATION ALGORITHMS AND THEIR APPLICATIONS TO NTRU PRIME Yeniaras, Esra; Cenk, Murat; Department of Cryptography (2022-1-21) Some of the post-quantum cryptographic protocols require polynomial multiplication in characteristic three fields, thus the efficiency of such multiplication algorithms gain more importance recently. In this thesis, we propose four new polynomial multiplication algorithms in characteristic three fields and we show that they are more efficient than the current state-of-the-art methods. We first analyze the well-known algorithms such as the schoolbook method, Karatsuba 2-way and 3-way split methods, Bernstein...
ON THE LATTICE STRUCTURE OF A NONLINEAR GENERATOR WITH MODULUS 2-ALPHA EICHENAUERHERRMANN, J; GROTHE, H; NIEDERREITER, H; TOPUZOGLU, A (1990-07-24) Nonlinear congruential pseudorandom number generators based on inversions have been introduced and analysed recently. These generators do not show the simple lattice structure of the widely used linear congruential generators which are too regular for certain simulation purposes. In the present paper a nonlinear congruential generator based on inversions with respect to a power of two modulus is considered. It is shown that the set of points formed by consecutive pseudorandom numbers has a more complicated ...

Citation Formats

A. Doğanaksoy, “On Lempel-Ziv complexity of sequences,” SEQUENCES AND THEIR APPLICATIONS - SETA 2006, pp. 180–189, 2006, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/53306.