On the k-Error Linear Complexity of Binary Sequences Derived from the Discrete Logarithm in Finite Fields
Let Fq be the finite field with q=pr elements, where p is an odd prime. For the ordered elements ξ0,ξ1,…,ξq-1∈Fq, the binary sequence σ=(σ0,σ1,…,σq-1) with period q is defined over the finite field F2={0,1} as follows: σn=0, if n=0, (1-χ(ξn))/2, if 1≤n<q, σn+q=σn, where χ is the quadratic c...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2019-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2019/8635209 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832552174150746112 |
|---|---|
| author | Zhixiong Chen Qiuyan Wang |
| author_facet | Zhixiong Chen Qiuyan Wang |
| author_sort | Zhixiong Chen |
| collection | DOAJ |
| description | Let Fq be the finite field with q=pr elements, where p is an odd prime. For the ordered elements ξ0,ξ1,…,ξq-1∈Fq, the binary sequence σ=(σ0,σ1,…,σq-1) with period q is defined over the finite field F2={0,1} as follows: σn=0, if n=0, (1-χ(ξn))/2, if 1≤n<q, σn+q=σn, where χ is the quadratic character of Fq. Obviously, σ is the Legendre sequence if r=1. In this paper, our first contribution is to prove a lower bound on the linear complexity of σ for r≥2, which improves some results of Meidl and Winterhof. Our second contribution is to study the distribution of the k-error linear complexity of σ for r=2. Unfortunately, the method presented in this paper seems not suitable for the case r>2 and we leave it open. |
| format | Article |
| id | doaj-art-a392237451bb4cffb4ca14001f00b86b |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2019-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-a392237451bb4cffb4ca14001f00b86b2025-02-03T05:59:20ZengWileyComplexity1076-27871099-05262019-01-01201910.1155/2019/86352098635209On the k-Error Linear Complexity of Binary Sequences Derived from the Discrete Logarithm in Finite FieldsZhixiong Chen0Qiuyan Wang1Provincial Key Laboratory of Applied Mathematics, Putian University, Putian, Fujian 351100, ChinaProvincial Key Laboratory of Applied Mathematics, Putian University, Putian, Fujian 351100, ChinaLet Fq be the finite field with q=pr elements, where p is an odd prime. For the ordered elements ξ0,ξ1,…,ξq-1∈Fq, the binary sequence σ=(σ0,σ1,…,σq-1) with period q is defined over the finite field F2={0,1} as follows: σn=0, if n=0, (1-χ(ξn))/2, if 1≤n<q, σn+q=σn, where χ is the quadratic character of Fq. Obviously, σ is the Legendre sequence if r=1. In this paper, our first contribution is to prove a lower bound on the linear complexity of σ for r≥2, which improves some results of Meidl and Winterhof. Our second contribution is to study the distribution of the k-error linear complexity of σ for r=2. Unfortunately, the method presented in this paper seems not suitable for the case r>2 and we leave it open.http://dx.doi.org/10.1155/2019/8635209 |
| spellingShingle | Zhixiong Chen Qiuyan Wang On the k-Error Linear Complexity of Binary Sequences Derived from the Discrete Logarithm in Finite Fields Complexity |
| title | On the k-Error Linear Complexity of Binary Sequences Derived from the Discrete Logarithm in Finite Fields |
| title_full | On the k-Error Linear Complexity of Binary Sequences Derived from the Discrete Logarithm in Finite Fields |
| title_fullStr | On the k-Error Linear Complexity of Binary Sequences Derived from the Discrete Logarithm in Finite Fields |
| title_full_unstemmed | On the k-Error Linear Complexity of Binary Sequences Derived from the Discrete Logarithm in Finite Fields |
| title_short | On the k-Error Linear Complexity of Binary Sequences Derived from the Discrete Logarithm in Finite Fields |
| title_sort | on the k error linear complexity of binary sequences derived from the discrete logarithm in finite fields |
| url | http://dx.doi.org/10.1155/2019/8635209 |
| work_keys_str_mv | AT zhixiongchen onthekerrorlinearcomplexityofbinarysequencesderivedfromthediscretelogarithminfinitefields AT qiuyanwang onthekerrorlinearcomplexityofbinarysequencesderivedfromthediscretelogarithminfinitefields |