Linearcomplexityofn-periodiccyclotomicsequencesoverF

22 浏览量 2021-02-11 23:38:25 上传评论收藏 133KB PDF 举报

### Linear Complexity of n-Periodic Cyclotomic Sequences Over F_p #### 摘要与背景本研究探讨了在有限域 \(F_p\) 上 n-周期的拟合圆序列的线性复杂度问题，其中 \(n\) 和 \(p\) 分别是两个不同的奇素数。这种序列作为密码系统中的密钥具有重要的应用价值，特别是对于流密码的设计至关重要。为了抵抗 Berlekamp-Massey (B-M) 算法等线性攻击，这些周期性序列必须具备高线性复杂度。 #### 序列与线性复杂度的概念在密码学领域，周期性序列常被用作流密码中的密钥。流密码是一种加密技术，它将明文中的每个位或符号与密钥流中的对应位或符号进行组合，从而产生密文。为了确保密钥的安全性和不可预测性，需要使用具有高线性复杂度的序列。 **线性复杂度**（Linear Complexity）是指序列能够表示为一个线性反馈移位寄存器 (LFSR) 的最小长度，这个 LFSR 能够生成该序列。简单来说，如果一个序列的线性复杂度很高，则意味着它难以通过简单的线性关系来预测，这对于抵御线性攻击至关重要。 #### 拟合圆序列的构造本研究中，序列是由拟合圆类（Cyclotomic cosets）构建而成的。拟合圆类是有限域 \(F_n\) 中的一组元素，其中 \(n-1 = e k\)（\(e \geq 2\)），且 \(F_n\) 是包含 \(n\) 个元素的有限域。假设 \(\theta\) 是 \(F_n^*\) 中的一个原根，则可以定义拟合圆类 \(C_\lambda\) 如下： \[C_0 = \langle \theta^e \rangle\] \[C_\lambda = \theta^\lambda C_0, \quad (0 \leq \lambda \leq e-1)\] 这里，\(C_0\) 表示由 \(\theta^e\) 生成的 \(F_n^*\) 的子群，而 \(C_\lambda\) (\(0 \leq \lambda \leq e-1\)) 是 \(C_0\) 在 \(F_n^*\) 中的余类。设 \(S\) 是集合 \(\{0, 1, \ldots, e-1\}\) 的一个子集，则可以定义序列 \(c_S\) 为： \[c_S = (c_i)_{i=0}^\infty\] 其中， \[c_i = \begin{cases} 1 & \text{若 } i \in \bigcup_{\lambda \in S} C_\lambda \\ 0 & \text{否则} \end{cases}\] #### 主要结果与结论本文的主要贡献在于计算了特定情况下 n-周期的 2 阶和 4 阶拟合圆序列在有限域 \(F_p\) 上的线性复杂度，并证明了这些序列通常具有较高的线性复杂度。这意味着这些序列能够有效抵抗线性攻击，因此它们在密码学中有潜在的应用价值。具体而言，研究发现当 \(n\) 和 \(p\) 是两个不同的奇素数时，这类 n-周期的 2 阶和 4 阶拟合圆序列的线性复杂度通常较高。这表明这些序列不仅适用于密码学中的密钥生成，还能提供良好的安全性和抗攻击能力。 #### 关键词解释 - **Legendre 序列**：一类特殊的二元周期序列。 - **拟合圆序列**：利用有限域中拟合圆类构造的周期序列。 - **线性复杂度**：衡量周期序列随机性的指标，即表示该序列所需的最短线性反馈移位寄存器长度。 - **Gauss 周期**：与拟合圆类紧密相关的数学概念，在本研究中用于分析序列的性质。本研究不仅深化了我们对拟合圆序列线性复杂度的理解，还为进一步探索这类序列在密码学中的应用提供了理论基础。

资源推荐

资源详情

资源评论

IEICE TRANS. FUNDAMENTALS, VOL.Exx–??, NO.xx XXXX 200x

LETTER

Linear complexity of n-periodic cyclotomic sequences over F

Qiuyan WANG

†a)

, Member and Yang YAN

††b)

, Nonmember

SUMMARY Periodic sequences, used as keys in cryptosystems, plays

an important role in cryptography. Such periodic sequences should possess

high linear complexity to resist B-M algorithm. Sequences constructed by

cyclotomic cosets have been widely studied in the past few years. In this

paper, the linear complexity of n-periodic cyclotomic sequences of order

2 and 4 over F

has been calculated, where n and p are two distinct odd

primes. The conclusions reveal that the presented sequences have high

linear complexity in many cases, which indicates that the sequences can

resist the linear attack.

key words: Legendre sequences Cyclotomic sequences Linear complexity

Gauss periods

1. Introduction

Periodic sequences used for stream ciphers are required to

have qualities of unpredictability. The linear complexity

is shown to have valuable properties as a measure for the

randomness (or equivalently the unpredictability) of peri-

odic sequences. Let c = (c

)

∞

i=0

be a sequence of peri-

od n over the ﬁnite ﬁeld F

. The linear complexity (also

called linear span) of c over F

, denoted by L

(c), is de-

ﬁned to be the smallest positive integer l such that there

are constants a

, 0, a

, . . ., a

∈ F

satisfying −a

i−1

+ a

i−2

+ ···+ a

i−l

= 0 for all i ≥ l. The Berlekamp-

Massey algorithm [1], [10] states that if L

is considered good with respect to its linear complexity.

For an odd prime n, let n −1 = ek (e ≥ 2) and F

be the

ﬁnite ﬁeld with n elements. Suppose θ is a primitive element

of F

∗

= F

\{0}. Let

= C

(e)

= θ

, (0 ≤ λ ≤ e − 1),

where C

= hθ

i is the subgroup of F

∗

generated by θ

and

(0 ≤ λ ≤ e − 1) are the cosets of C

in F

∗

. Let S be a

subset of {0, 1, . . . , e − 1} and

[

λ∈S

We deﬁne the following binary periodic sequence c

)

∞

i=0

with period n by

Manuscript received 0, 0.

Manuscript revised 0, 0.

†

School of Computer Science and Technology, Tiangong Uni-

versity, Tianjin, China

††

School of Information Technology Engineering, Tianjin Uni-

versity of Technology and Education, Tianjin, China

a) E-mail: wangyan198801@163.com

b) E-mail: yanyangucas@126.com

DOI: 10.1587/transfun.E0.A.1

(

1, if (i mod n) ∈ Σ

0, otherwise,

for all i ≥ 0.

Such sequences are called binary cyclotomic sequences of

order e and used as keys in cryptography since they have

good pseudo-random properties and correlation properties

[6], [8], [11]–[13]. The linear complexity of such sequences

over F

has been determined by Ding et al. [5] for order

2 case (Legendre sequences) and Edemskii [7] for order 4

case. Since c

is either 0 or 1, such sequences can be viewed

over F

, where q = p

and p is a prime number. When

(n − 1)/4 ≡ 0 (mod p), Ding [4] has determined the lin-

ear complexity of cyclotomic sequences of order 4 over F

from the view point of coding theory. In this paper, our

ﬁrst contribution is to give a general formula on the linear

complexity of cyclotomic sequences by using Gauss period-

s. Our second contribution is to determine the linear com-

plexity of binary n-periodic cyclotomic sequences of order

2 and 4 over a ﬁnite ﬁeld F

, where p and n are two distinct

odd primes. The results show that the linear complexity of

c over F

is nearly equal to the period n in many cases so

that they can resist the linear attack in cryptography.

This paper is organized as follows. Section 2 contains

the deﬁnitions and formulas of linear complexity of periodic

sequences and Gauss periods. In section 3, we determine

the linear complexity of the binary cyclotomic sequences of

order 2 and 4 over F

2. Preliminaries

Firstly, we introduce the deﬁnition and formula of linear

complexity of periodic sequences over a ﬁnite ﬁeld. See

[3] or [9] for more details.

Let q be a power of a prime p and let c = (c

)

∞

i=0

be a

periodic sequence over F

with period n, where c

∈ F

(i ≥

0). The sequence c can be viewed as a power series

∞

(x) =

∞

n=0

u(x)

1 − x

u(x) = c

+ c

x + c

+ ··· + c

n−1

∈ F

[x]

in the power series ring F

[[x]].

Let h(x) = gcd(u(x), 1 − x

) , then

∞

(x) =

w(x)

v(x)

, v(x) =

1 − x

h(x)

w(x) =

u(x)

h(x)

where u(x), v(x), h(x) ∈ F

[x].

 200x The Institute of Electronics, Information and Communication Engineers

IEICE TRANS. FUNDAMENTALS, VOL.Exx–??, NO.xx XXXX 200x

Deﬁnition 2.1 ([9]) The polynomial v(x) is called the min-

imal polynomial of the periodic sequence c over F

. The

deg v(x) = n − deg h(x) is called the linear complexity of

the sequence c over F

, which is denoted by L

(c).

Indeed, L

back shift register which generates the sequence c.

If gcd(n, p) = 1, then 1 − x

has n distinct zeros ζ

(0 ≤

i ≤ n − 1) in the algebraic closure Ω

of F

. Let

m = #{i : 0 ≤ i ≤ n − 1, u(ζ

) = 0}.

Then it is easy to see that deg h(x) = m and L

In order to determine L

sequences, we introduce Gauss periods.

Deﬁnition 2.2 ([2]) For a prime power q = p

(p , n), let

be a primitive n-th root of unity in the algebraic closure

Ω

of F

. The Gauss periods of order e are deﬁned by

x∈C

, (0 ≤ λ ≤ e − 1).

The following Lemma states some basic properties on

Gauss periods which can be derived from the deﬁnition di-

rectly.

Lemma 2.3 ([2]) Let symbols be the same as before. Then

we have

(1)

e−1

λ=0

= −1;

(2) For a = θ

x∈C

= η

s+λ

;

(3) For 0 ≤ λ ≤ e −1, let

n−1

x=0

Then

= 1 + eη

;

(4) For p ∈ C

= η

λ+i

The values of Gauss periods of order 2 and 4 can be

determined explicitly (see [2] or [9]) by Gauss sums. In this

paper, we need the following results on the modiﬁed period

polynomial

f (x) = (x − g

)(x −g

) ···(x − g

e−1

For e = 2 and n − 1 = 2k, it is well known that [2]

(x −g

)(x −g

) = x

−

−1

For e = 4, n = 4k + 1 can be expressed by

n = a

+ b

, a, b ∈ Z,

where a is determined by a ≡ −





(mod 4), the even in-

teger b is determined up to sign and





is the Legendre

symbol ([2], Theorem 3.2.1).

Lemma 2.4 ([2], Theorem 4.2.1, Corollary 4.2.2)

(1) For e = 4 and n − 1 = 4k,

f (x) =

λ=0

(x −g

) = x

− 2n

1 + 2

− 8

anx

1 − 4

+ 4b

where

(

1, i f n ≡ 1 (mod 8),

−1, i f n ≡ 5 (mod 8).

(2) The discriminant of f (x) is

4 = 2

1 − 2

+ a

Therefore, f (x) has multiple zeros in Ω

if and only if

2bn

n(1 − 2

) + a

≡ 0 (mod p).

(3) For g

, we have

√

n ±



n + a

√



3. Results and Proofs

Let n be an odd prime and n − 1 = ek. Let q = p

for

an odd prime p and satisfy gcd(n, q) = 1. For a non-empty

subset S of {0, 1, . . . , e −1}, the binary cyclotomic sequence

= (c

)

∞

i=0

with period n is deﬁned by

(

1, if (i mod n) ∈ Σ

0, otherwise,

for all i ≥ 0. (3.1)

Let c(x) =

n−1

i=0

∈ F

[x]. It is not diﬃcult to see that

c(x) =

n−1

i=1

i∈Σ

. (3.2)

Let h(x) = gcd(x

− 1, c(x)). Then

) = n − deg h(x). (3.3)

Since the greatest common divisor of c(x) and 1−x

over F

is equal to that of these two polynomials over F

, we then

get the following fact. For a binary periodic sequence c, we

have L

(c).

Due to the above fact, we will focus on the prime ﬁeld

in the following. Let ζ

be an n-th primitive root of unity

剩余6页未读，继续阅读

评论收藏

内容反馈

weixin_38641111

粉丝: 1
资源: 931

Linear complexity of n-periodic cyclotomic sequences over F_p

最新资源

Linear complexity of n-periodic cyclotomic sequences over F_p

Linear complexity of generalized cyclotomic sequences of order 4 over F_l

Python库 | lameenc-1.2.0-cp36-cp36m-macosx_10_6_intel.whl

fdk-aac-2.0.1_FDK_tool_averagedbb_

KNN-complexity-reduced-method.rar_KNN LOCALIZATION_LANDMARC定位_ra

A-low-complexity-transmit-antenna-selection-for-li_antenna selec

BM.rar_BM-algorithm_Berlekamp-Massey_The Returned_berlekamp _bm

数据分析视频 --The Data Scientist’s Toolbox.zip

switbhing-complexity.rar_complexity_分形几何

给定k-错线性复杂度的2_n-周期二元序列条数及Matlab程序.zip

fdk-aac-2.0.1.zip_aac_fdk acc_fdk-aac_fdk-aac-2.0.1_fdkacc

The Complexity of Theorem-Proving Procedures

MATLAB-code-of-OFDMA-power-allocation.rar_OFDMA allocation_OFDMA

Fibr--For next idea_fiber_

allbest-o-00012642_C++_

jefqr-radian-complexity.rar_Linux/Unix编程_complexity_信道估计

continuous time linear equalizer.rar

TestU01-1.2.3_changekcj_worepem_testu01_

ISO-IEC_13818-4.pdf.tar.gz_13818_13818-4_ISO 13818-4_ISO_IEC_138

A Low-Complexity Method for.rar_sm_spatial modulation

Losses-Data-hide.rar_Reversible Data_The Cover_decryption

Low Complexity Iterative LMMSE-PIC Equalizer for OTFS代码

tftb-0.2_Spectrum_fft_divider_tripi3m_傅里叶_

Asymptotic_Complexity_Judge-0.0.1-py3-none-any.whl.zip

8-On-the-Wiener-and-Hammerstein-Models-for-Power-_Hammerstein_Mo

Ultra-Low Power Integrated Circuit Design_ Circuits, Systems

On the linear complexity of some new q-ary sequences

domain driven design tackling complexity in the heart of software

基于CORDIC的反正弦和反余弦计算的FPGA实现

最新资源