Special Day on Sequences, Randomness, and Complexity

- FENS
- Special Day on Sequences, Randomness, and Complexity

**Special Day on Sequences, Randomness, and Complexity**

**24 November, Thursday, Sabancı University Campus, FENS 2019**

by

by

by

by

This workshop is supported by TUBITAK ISBAP project 107T897 and Sabancı University.

**Abstracts:**

*Laszlo Merai:*

**Linear complexity and Edwards curves**

In this talk I study the pseudorandomness properties of congruential generators over different types of curves. More precisely, I summarize the statistical and complexity behavior of elliptic curve congruential generators and point out some limitations of elliptic curves represented by the Weierstrass equation in applications, particularly in cryptography. Next I introduce the Edwards curve and the Edwards curve congruential generators. Finally I state a theorem which is concerned with linear complexity of Edwards curve congruential generators and I sketch the proof.

This is a joint work with Arne Winterhof.

-----------------------------------------------------------------

*Harald Niederreiter*

**Results and problems on randomness and complexity of sequences **

There are many ways of assessing the (pseudo)randomness of a sequence. We focus on several complexity measures, including the recently introduced expansion complexity, and on the statistical property of complete uniform distribution. We discuss important facts, logical relationships, and open problems for these concepts.

-----------------------------------------------------------------

*Ferruh Ozbudak*

**Quadratic forms and maximal/minimal curves**

We give certain relations between quadratic forms and maximal/minimal curves over finite fields and we also give some characterization results. Parts of this talk are based on joint works with Elif Saygi and Zulfukar Saygi.

-----------------------------------------------------------------

*Arne Winterhof *

**On some measures of pseudorandomness**

We have different measures of pseudorandomness for binary sequences in view of different applications. For example, on the one hand, in cryptography unpredictability is the most desirable feature of a sequence which is usually analyzed in terms of its linear complexity and related figures of merit. On the other hand, in wireless communication we need sequences with a small autocorrelation such that the original signal can be distinguished from a delayed signal.

These measures of pseudorandomness are often not independent and here we present some relations between them focussing on linear complexity and correlation measure.

One of the best known sequence construction in view of these measures is the Legendre sequence $(l_n)$ where $l_n=1$ if and only if $n$ is a quadratic nonresidue modulo $p$ and $l_n=0$ otherwise. We also explain a general method how to derive 'good' binary sequences from 'good' $m$-ary sequences as sequences defined with characters of higher order.

Finally, we mention relations between some quality measures for binary sequences and their corresponding Boolean functions.

© Copyright 2017 by Sabanci University.