Special Day on Sequences, Randomness, and Complexity

Special Day on Sequences, Randomness, and Complexity

24 November, Thursday, Sabancı University Campus, FENS 2019
11:00-11:50:  On some measures of pseudorandomness
by Arne Winterhof (RICAM, Linz)
13:40-14:30 Results and problems on randomness and complexity of sequences
by Harald Niederreiter (Austrian Academy of Sciences)
14:40-15:30 Quadratic forms and maximal/minimal curves
by Ferruh Ozbudak (METU, Ankara)
16:00-16:50 Linear complexity and Edwards curves
by Laszlo Merai (Hungarian Academy of Sciences)
17:00-18:00 (Informal) discussion

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




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.