On the k-error linear complexity over of Legendre and Sidelnikov sequences
H Aly, A Winterhof - Designs, Codes and Cryptography, 2006 - Springer
Designs, Codes and Cryptography, 2006•Springer
We determine exact values for the k-error linear complexity L k over the finite field F _ p of
the Legendre sequence L of period p and the Sidelnikov sequence T of period pm− 1. The
results are L_k (L)=\left {(p+ 1)/2,\quad 1 ≤ k ≤ (p-3)/2,\0,\quad k ≥ (p-1)/2,. L_k (T)
≥\min\left (\left (p+ 1 2\right)^ m-1,\left ⌈ p^ m-1 k+ 1\right ⌉-\left (p+ 1 2\right)^ m+ 1\right) for
1≤ k≤(pm− 3)/2 and L_k (T)= 0 for k≥(pm− 1)/2. In particular, we prove L_k (T)=\left (p+ 1
2\right)^ m-1,\quad 1 ≤ k ≤ 1 2\left (3 2\right)^ m-1.
the Legendre sequence L of period p and the Sidelnikov sequence T of period pm− 1. The
results are L_k (L)=\left {(p+ 1)/2,\quad 1 ≤ k ≤ (p-3)/2,\0,\quad k ≥ (p-1)/2,. L_k (T)
≥\min\left (\left (p+ 1 2\right)^ m-1,\left ⌈ p^ m-1 k+ 1\right ⌉-\left (p+ 1 2\right)^ m+ 1\right) for
1≤ k≤(pm− 3)/2 and L_k (T)= 0 for k≥(pm− 1)/2. In particular, we prove L_k (T)=\left (p+ 1
2\right)^ m-1,\quad 1 ≤ k ≤ 1 2\left (3 2\right)^ m-1.
Abstract
We determine exact values for the k-error linear complexity L k over the finite field of the Legendre sequence of period p and the Sidelnikov sequence of period p m − 1. The results are $$ L_k(\mathcal{L}) =\left\{\begin{array}{ll} (p+1)/2, \quad 1 \le k \le (p-3)/2,\\ 0, \quad k\ge (p-1)/2, \end{array}\right.$$ $$L_k(\mathcal{T})\ge \min \left( \left( \frac{p+1}{2} \right)^{m}-1, \left \lceil \frac{p^m-1}{k+1} \right \rceil - \left(\frac{p+1}{2} \right)^{m} + 1 \right)$$ for 1 ≤ k ≤ (p m − 3)/2 and for k≥ (p m − 1)/2. In particular, we prove $$L_k(\mathcal{T}) = \left(\frac{p+1}{2} \right)^{m}-1,\quad 1\le k\le \frac{1}{2}\left(\frac{3}{2}\right)^{m}-1.$$
Springer