Constructions of sequences with almost perfect linear complexity profile from curves over finite fields
type: Item
instance of: scholarly article
title: Constructions of sequences with almost perfect linear complexity profile from curves over finite fields
zbMATH Open document ID: 0943.94005
author: Cunsheng Ding
author: Chaoping Xing
author: Harald Niederreiter
author: Kwok Yan Lam
published in: Finite Fields and their Applications
publication date: 2000-09-06T00:00:00Z
review text: Let \(\mathbb{F}_q\) denote the finite field with \(q\) elements. The linear complexity of a sequence \(a_1,a_2,\dots,a_n\) of elements from \(\mathbb{F}_q\) is the least \(k\) such that the sequence is a \(k\)th-order shift-register sequence. This notion is important in the theory of stream ciphers. Given an infinite sequence \({\mathbf a}=a_1,a_2,\dots\) of elements from \(\mathbb{F}_q\), let \(l(n)\) denote the linear complexity of \(a_1,a_2,\dots,a_n\). Then the sequence of integers \(\{l(n)\}\) is called the linear complexity profile of \textbf{a}. The sequence \textbf{a} is said to have a \(d\)-almost perfect linear complexity profile if \[ {{n+1-d}\over 2}\leq l(n)\leq {{n+d}\over 2} \] for all \(n\geq 1\). In this paper, the authors generalize a construction given by the first and the third authors [IEEE Trans. Inf. Theory 45, 1267-1270 (1999; Zbl 0943.94013)] that uses the coefficients in the local expansion of a rational function \(f\) at a rational point \(P\) on a curve defined over \(\mathbb{F}_q\) to form a \(d\)-almost perfect sequence, where \(d\) depends on the degree of \(f\) and the order of \(f\) at \(P\). To perform the construction, one needs a local parameter \(t\) at \(P\) such that the divisor of \(t\) is \(P+Q-D\), where \(D\) is a positive divisor of degree two. Thus, the construction requires a hyperelliptic (or rational or elliptic) curve. The authors give some examples using the projective line and an elliptic curve over \(\mathbb{F}_3\).
Mathematics Subject Classification ID: 94A55
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 14G15
Mathematics Subject Classification ID: 65C10
zbMATH DE Number: 1398790
zbMATH Keywords: shift-register sequence
zbMATH Keywords: linear complexity
zbMATH Keywords: algebraic curves over finite fields
reviewed by: Robert F. Lax
MaRDI profile type: Publication
OpenAlex ID: W2078445005
DOI: 10.1006/FFTA.1999.0251
Recommended article: Sequences with almost perfect linear complexity profiles and curves over finite fields
Recommended article: Q2708618
Recommended article: Q2712133
Recommended article: On the use of expansion series for stream ciphers
Recommended article: Multisequences with almost perfect linear complexity profile and function fields over finite fields
Recommended article: Q4330636
Recommended article: Q4421625
Recommended article: Linear complexity profiles: Hausdorff dimensions for almost perfect profiles and measures for general profiles
Recommended article: Q3797089
Recommended article: Multi-sequences with \(d\)-perfect property
description: scientific article; zbMATH DE number 1398790