Autocorrelation values of two classes of generalized cyclotomic sequences
-
摘要: 基于广义分圆理论,构造了一类周期为2p的二元广义分圆序列和一类周期为pq的二元广义分圆序列,利用分圆数和差集理论讨论了这2类序列的自相关函数值。对于周期为2p的二元广义分圆序列,当p ≡ 1(mod8)时,该类序列具有几乎最优的自相关函数值;当p ≡ 3(mod8)时,该类序列的自相关函数值是四值。对于周期为pq的二元广义分圆序列,当(p - 1)(q - 1)/4是偶数时,该类序列具有几乎最优的自相关函数值;当(p - 1)(q - 1)/4是奇数时,该类序列的自相关函数值为四值。结果表明,构造的2类二元广义分圆序列都具有低值自相关性质。Abstract: A class of generalized cyclotomic binary sequences with period 2p and a class of generalized cyclotomic binary sequences with periods pq are constructed based on generalized cyclotomic theory. The autocorrelation values of two classes of generalized cyclotomic binary sequences with periods 2p and pq are determined by cyclotomic number and different sets. The class of binary sequences with period 2p have almost optimal autocorrelation function values when p ≡ 1(mod8) and 4-value autocorrelation when p ≡ 3(mod8). The class of binary sequences with periods pq have almost optimal autocorrelation function values when (p-1) (q-1)/4 is even and 4-value autocorrelation when(p-1) (q-1)/4 is odd. Results show that the class of sequences with periods pq and 2p in this paper have low-value autocorrelation.
-
Keywords:
- stream cipher /
- autocorrelation /
- cyclotomy /
- pseudorandom sequence
-
0. 引言
在伪随机序列构造中,周期自相关函数是衡量伪随机序列性质的一个重要指标。具有理想自相关值的序列在密码学及其他领域有着重要的应用[1-2],因此,二元序列和四元序列的自相关值得到了广泛深入的研究[3-4]。
伪随机序列的构造和自相关值的研究是密码学领域的核心问题。有限域 F2上的伪随机序列的自相关性在加密应用中占有十分重要的地位。基于模 N剩余类环分割得到分圆类构造序列是构造伪随机序列的重要方法[1],其中 N是序列的周期。当 N为素数时,其割圆类称为经典分圆类;当 N为合数时,其割圆类称为广义分圆类。相应地,基于经典分圆类构造的序列称为经典分圆序列;基于广义分圆类构造的序列称为广义分圆序列。Legendre序列是基于二阶分圆类构造得到的一类序列,其具有好的自相关性[5]。文献[6-9]研究了具有理想自相关值的二元序列;文献[10]研究了一类自相关函数为三值的广义分圆序列;Ding[11]构造了一类新的分圆类,并得到了一类循环码;Liu和Chen[12]确定了基于这类新的分圆类构造的广义分圆序列的自相关性和线性复杂度。基于二阶广义分圆类的构造方法,Kim等[13]定义了一类周期为2p的四元分圆序列,其中 p为素数,并且得到了这类序列的自相关值[14]。另外,周期为 pqr的伪随机序列的自相关值和线性复杂度也被进一步研究[15]。
二元流密码是一种对称密码系统,其中明文和密文是有限域上的有限序列,通过同一字符串的位加减法进行加密和解密。后一个字符串作为加密和解密密钥,在流密码中被称为密钥流。序列构造的核心是,密钥流应该是随机的,测量密钥流随机性的主要工具是自相关。给定一个周期为 N的二元序列 s∞ = (s0,s1,⋯),其中 si ∈ GF (2)。周期为 N的二元序列 s∞的自相关函数被定义为
$$ C_{s}(\omega)=\frac{1}{N} \sum\limits_{i \in Z_{N}}(-1)^{s_{i+w}+s_{i}}, $$ (1) 式中$0 \leqslant \omega \leqslant N-1$。二元序列的理想自相关值是二值, 其自相关函数被定义为
$$ C_{s}(\omega)= \begin{cases}1, & \omega=0, \\ 1 / N, & \text { 其他。 }\end{cases} $$ (2) 具有理想自相关函数的伪随机序列在密码学、编码理论及通讯工程等领域应用广泛。
本文利用二阶分圆类的方法构造一类周期为 pq的二元分圆序列和一类周期为2p的二元分圆序列,计算这2类序列的自相关值,并且讨论参数的选取,使得这类序列具有好的自相关性。
1. 预备知识
1.1 构造周期为 pq的二元序列
假设 p、q是2个不同的素数,并且gcd(p − 1,q − 1) = 2。根据中国剩余定理[16],存在模 p和模q的公共本元根 q,整数 x满足
$$ x \equiv g(\text{mod}p), x \equiv 1(\text{mod} q), $$ (3) 中国剩余定理保证了上述同余方程组的解存在并且唯一。
定义周期$N=p q, e=(p-1)(q-1) / 2$, 由于$g$是模$p$和模$q$的公共本元根, 根据中国剩余定理得
$$ \begin{gathered} \operatorname{ord}_{N}(g)=\operatorname{lcm}\left(\operatorname{ord}_{p}(g), \operatorname{ord}_{q}(g)\right)= \\ \operatorname{lcm}(p-1, q-1)=e, \end{gathered} $$ 式中$\operatorname{ord}_{N}(g)$表示$g$模$N$得乘法阶。
二阶Whiteman广义分圆类$D_{0}$和$D_{1}$定义为 [17]
$$ D_{i}=\left\{g^{s} x^{i}: s=0, 1, \cdots, e-1\right\}, i=0, 1 。 $$ 根据$x$的定义得
$$ Z_{p q}^{*}=D_{0} \cup D_{1}, D_{0} \cap D_{1}=\varnothing, $$ 式中$\varnothing$表示空集。
二阶广义分圆数定义为
$$ (i, j)=\left|\left(D_{i}+1\right) \cap D_{j}\right|, i=0, 1 ; j=0, 1 。 $$ (4) 对于$Z_{N}$上得任一子集$A, a \in Z_{N}$, 定义
$$ \begin{array}{c} A+a=\{x+a: x \in A\} \text { 和 } A a=\{a x: x \in A\} 。 \\ P=\{p, 2 p, \cdots, (q-1) p\}, \\ Q=\{q, 2 q, \cdots, (p-1) q\}, \\ R=\{0\}, C_0=R \cup P \cup D_0, C_1=Q \cup D_1 。 \end{array} $$ 则
$$ C_{0} \cup C_{1}=Z_{p q}, C_{0} \cap C_{1}=\varnothing。 $$ 关于模$p q$的二阶广义分圆序列$\left\{t_{i}\right\}, i \geqslant 0$定义为
$$ S_{i}=\left\{\begin{array}{l} 0, i(\text{mod}p q) \in C_{0}, \\ 1, i(\text{mod}p q) \in C_{1}。 \end{array}\right. $$ (5) 上述序列可写成表达式$S_{i}=F(i\text{mod}N)$, 对于所有$0 \leqslant i \leqslant N-1$,
$$ F(i)= \begin{cases}0, & i \in R \cup P, \\ 1, & i \in Q, \\ \left(1-\left(\frac{i}{p}\right)\left(\frac{i}{p}\right)\right) / 2, & \text { 其他, }\end{cases} $$ (6) 式中$\left(\frac{i}{p}\right)$代表Legendre符号。
1.2 构造周期为2p的二元序列
设$p$是奇素数,$g$是奇数, 且$g$是模$p$和$2 p$的公共本原元,$<g^{2}>$表示由$g^{2}$生成的子群, 记模$2 p$的剩余类环为$Z_{2 p}=\{0, 1, \cdots, 2 p-1\}$。
记
$$ \begin{aligned} D_0^{(p)}=< & g^2>(\text{mod}p)= \\ & \left\{g^{2 k}(\text{mod}p): k=0, 1, \cdots, \frac{p-1}{2}-1\right\}, \\ D_0^{(2 p)}=< & g^2>(\text{mod} 2 p)= \\ & \left\{g^{2 k}(\text{mod} 2 p): k=0, 1, \cdots, \frac{p-1}{2}-1\right\}, \\ D_1^{(p)}= & g D_0^{(p)}=g<g^2>(\text{mod}p)= \\ & \left\{g^{2 k+1}(\text{mod}p): k=0, 1, \cdots, \frac{p-1}{2}-1\right\}, \\ D_1^{(2 p)}= & g D_0^{(2 p)}=g<g^2>(\text{mod} 2 p)= \\ & \left\{g^{2 k+1}(\text{mod} 2 p): k=0, 1, \cdots, \frac{p-1}{2}-1\right\}, \end{aligned} $$ 式中$D_{0}^{(n)}$和$D_{1}^{(n)}$表示二阶广义分圆类。记$Z_{n}^{*}=\{1 \leqslant$$i \leqslant n-1: \operatorname{gcd}(i, n)=1\}$, 则
$$ Z_{2 p}^{*}=D_{0}^{(2 p)} \cup D_{1}^{(2 p)}, Z_{p}^{*}=D_{0}^{(p)} \cup D_{1}^{(p)}, Z_{2}^{*}=\{1\}, $$ 进而,
$$ Z_{2 p}=D_{0}^{(2 p)} \cup D_{1}^{(2 p)} \cup 2 D_{0}^{(p)} \cup 2 D_{1}^{(p)} \cup\{0\}。 $$ 记
$$ C_{0}=D_{1}^{(2 p)} \cup 2 D_{1}^{(p)} \cup\{0\}, C_{1}=D_{0}^{(2 p)} \cup 2 D_{0}^{(p)} \cup p Z_{2}^{*}, $$ 则$Z_{2 p}=C_{0} \cup C_{1}$, 并且$C_{0} \cap C_{1}=\varnothing$, 其中$\varnothing$为空集。
构造周期为$2 p$的广义分圆二元序列$\left\{s_{i}\right\}:$
$$ s_{i}= \begin{cases}0, & i(\text{mod} 2 p) \in C_{1}, \\ 1, & i(\text{mod} 2 p) \in C_{0}。\end{cases} $$ (7) 2. 主要结果
2.1 周期为 pq的二元序列的自相关值
可利用如下定义的差集函数确定二元序列的自相关函数值。
$$ d_{S}(i, j ; \omega)=\left|C_{i} \cap\left(C_{j}+\omega\right)\right|, \omega \in Z_{N}, i=0, 1 ; j=0, 1。 $$ 计算周期为$p q$的二元序列的自相关值需要以下引理。
引理1[18] 对于任意$a \neq 0(\text{mod} N)$, 有
$$ C_{S}(a)=1-\frac{4 d_{S}(1, 0 ; a)}{N} 。 $$ (8) 引理2[19] 对于任意$\omega \in Z_N^*$, 则有
$$ \left|\left(D_{0}+\omega\right) \cap D_{1}\right|= \begin{cases}(0, 1), & \omega \in D_{0}, \\ (1, 0), & \omega \in D_{1}。\end{cases} $$ (9) 引理3 对于任一$\omega \in P \cup Q$, 有
$$ \left|\left(D_{0}+\omega\right) \cap D_{1}\right|=\frac{(p-1)(q-1)}{4} 。 $$ (10) 引理4 对于任一$\omega \in P \cup Q$, 有
$$ \left|D_{1} \cap((P \cup R)+\omega)\right|= \begin{cases}0, & \omega \in P \cup R, \\ \frac{q-1}{2}, & \text { 其他。 }\end{cases} $$ (11) 证明 如果$\omega \in P \cup Q$, 显然$\left|D_{1} \cap((P \cup R)+\omega)\right|=$ 0; 如果$\omega \notin P \cup R$, 则存在$z$, 使得$z=g^{s} x \in(P \cup R)+$$\omega$当且仅当
$$ g^{s} x-\omega \equiv 0(\text{mod}p), $$ (12) 注意到$x \equiv g(\text{mod}p)$和$x \equiv 1(\text{mod} q)$。设$\omega$模$q$的逆是$v$, 由于$g$是模$p$的本元根, 所以一定存在整数$t, 0 \leqslant t \leqslant q-1$, 使得$v \equiv g^{t}(\text{mod}p)$。因此, 式(12)等价于$g^{s-t} \equiv 1(\text{mod}p)$, 进一步等价于$s-$$t \equiv 0(\text{mod}p-1)$。所以式(12)中$s(0 \leqslant s \leqslant e-1)$的解的数目为$e /(q-1)$, 即$(p-1) / 2$。
引理5[16] (广义中国剩余定理) 设$m_{1}, \cdots, m_{t}$为正整数。对于整数集合$a_{1}, \cdots, a_{t}$, 同余方程组$y \equiv a_{i}\left(\text{mod} m_{i}\right), i=1, \cdots, t$有解当且仅当
$$ a_{i} \equiv a_{j}\left(\operatorname{modgcd}\left(m_{i}, m_{j}\right)\right), i \neq j, 1 \leqslant i \leqslant t, 1 \leqslant j \leqslant t。 $$ (13) 如果式(13) 成立, 则方程$\mathrm{lcm}\left(m_{1}, m_{2}, \cdots, m_{t}\right)$有唯一解。
引理6 如果$|p-q| / 2$是奇数, 则$-1 \in D_{1}$; 如果$|p-q| / 2$是偶数, 则$-1 \in D_{0}$。
证明 由于
$$ g^{s} \equiv-1(\text{mod}p q), $$ (14) 当且仅当存在整数$s(0 \leqslant s \leqslant e-1)$, 由中国剩余定理知, 其等价于$g^{s} \equiv-1(\text{mod}p)$和$g^{s} \equiv-1(\text{mod} q)$。因为$g$是模$p$和模$q$的公共本元根, 所以$g^{(p-1) / 2} \equiv-1(\text{mod}p), g^{(q-1) / 2} \equiv-1(\text{mod} q)$。其等价于$g^{s-(p-1) / 2} \equiv 1(\text{mod}p), g^{s-(q-1) / 2} \equiv 1(\text{mod} q)$。由引理5可知, 式(14) 有解当且仅当$|p-q| / 2$为偶数。
引理7 对于任一$\omega \in Z_N^*$, 有如下结果。
(1)
$$ \left|Q \cap\left(D_0+\omega\right)\right|=\left\{\begin{array}{l} \frac{p-1}{2}, \omega \in P, \\ 0, \quad \omega \in Q, \\ \frac{p-1}{2}, \omega \in D_1, \frac{|p-q|}{2} \text { 是偶数, } \\ \frac{p-3}{2}, \omega \in D_1, \frac{|p-q|}{2} \text { 是奇数, } \\ \frac{p-3}{2}, \omega \in D_0, \frac{|p-q|}{2} \text { 是偶数, } \\ \frac{p-1}{2}, \omega \in D_0, \frac{|p-q|}{2} \text { 是奇数。 } \end{array}\right. $$ (2)
$$ |Q \cap((P \cup R)+\omega)|=\left\{\begin{array}{ll} 0, & \omega \in P, \\ 1, & \omega \in Q, \\ 1, & \omega \in D_0 \cup D_1。 \end{array}\right. $$ (15) 证明 (1) 与引理4的证明类似, 可以得到
$$ \left|(P \cup R) \cap\left(D_0+\omega\right)\right|=\left\{\begin{array}{ll} 0, & \omega \in P \cup R, \\ \frac{p-1}{2}, & \omega \notin P \cup R 。 \end{array}\right. $$ (16) 由引理6得
$$ \left|R \cap\left(D_0+\omega\right)\right|=\left\{\begin{array}{ll} 0, & \omega \in P, \\ 0, & \omega \in D_1, \frac{|p-q|}{2} \text { 是偶数, } \\ 1, & \omega \in D_1, \frac{|p-q|}{2} \text { 是奇数, } \\ 1, & \omega \in D_0, \frac{|p-q|}{2} \text { 是偶数, } \\ 0, & \omega \in D_0, \frac{|p-q|}{2} \text { 是奇数。 } \end{array}\right. $$ 又因为
$$ \begin{array}{l} \left|Q \cap\left(D_0+\omega\right)\right|=\left|(Q \cup R) \cap\left(D_0+\omega\right)\right|- \\ \left|R \cap\left(D_0+\omega\right)\right|=\frac{p-1}{2}-\left|R \cap\left(D_0+\omega\right)\right|, \end{array} $$ 将$\left|R \cap\left(D_{0}+\omega\right)\right|$带入后可得结果。
(2) 注意到
$$ \begin{array}{c} |Q \cap((P \cup R)+\omega)|=|Q \cap(P+\omega)|+ \\ |Q \cap(R+\omega)|= \\ |Q \cap(P+\omega)|+|Q \cap\{\omega\}|, \end{array} $$ (17) 所以, 如果$\omega \in P$, 则$|Q \cap((P \cup R)+\omega)|=0$; 如果$\omega \in Q$, 则$|Q \cap((P \cup R)+\omega)|=1$。
由$P$和$Q$的定义, 对于任一给定$\omega \in Z_N^*$, 有
$$ u p-v q \equiv \omega(\text{mod}p q), $$ (18) 式中:$1 \leqslant u \leqslant q-1 ; 1 \leqslant v \leqslant p-1$。假设上式有2个解$\left(u_{1}, v_{1}\right)$和$\left(u_{2}, v_{2}\right)$。则
$$ u_1 p-v_1 q \equiv u_2 p-v_2 q(\text{mod}pq), $$ (19) 因此,$u_{1} p \equiv u_{2} p(\text{mod} q), v_{1} q \equiv v_{2} q(\text{mod}p)$,
又
$$ \begin{array}{l} 0 \leqslant u_1 \leqslant q-1, 0 \leqslant u_2 \leqslant q-1, \\ 0 \leqslant v_1 \leqslant p-1, 0 \leqslant v_2 \leqslant p-1, \end{array} $$ 且
$$ \operatorname{gcd}(p, q)=1, $$ (20) 所以
$$ \left(u_1, v_1\right)=\left(u_2, v_2\right) \text { 。 } $$ (21) 因此, 当$u$跑遍$\{1, 2, \cdots, q-1\}$且$v$跑遍$\{1, 2, \cdots, q-1\}$时, 函数$u p-v q$在$Z_N^*$上取$(p-$ 1)$(q-1)$个不同的元, 但是$Z_N^*$中仅有$(p-1)(q-$ 1) 个元。所以, 对于任一给定$\omega \in Z_N^*$, 有
$$ |Q \cap(P+\omega)|=1 。 $$ 引理8 如果$(p-1)(q-1) / 4$为偶数, 则$(0, 0)=(1, 0)=(1, 1)$且有2个差集分圆数
$$ \begin{array}{l} (0, 0)=\frac{(p-2)(q-2)+1}{4}, \\ (0, 1)=\frac{(p-2)(q-2)-3}{4} 。 \end{array} $$ 如果$(p-1)(q-1) / 4$为奇数, 则$(0, 0)=$$(1, 0)=(1, 1)$且有2个差集分圆数
$$ \begin{array}{l} (0, 0)=\frac{(p-2)(q-2)+3}{4}, \\ (0, 0)=\frac{(p-2)(q-2)-1}{4} 。 \end{array} $$ 在下一部分需要用到以下公式:
$$ \begin{array}{c} d_s(1, 0 ; \omega)=\left|C_1 \cap\left(C_0+\omega\right)\right|= \\ \left|\left(Q \cup D_1\right) \cap\left(\left(R \cup P \cup D_0\right)+\omega\right)\right|= \\ \mid\left(D_1 \cap\left(D_0+\omega\right)|+| D_1 \cap((P \cup R)+\omega) \mid+\right. \\ \left|Q \cap\left(D_0+\omega\right)\right|+|Q \cap((P \cup R)+\omega)|, \end{array} $$ (22) 设各个符号定义同上,相应的主要结果如下。
定理1 设$(p-1)(q-1) / 4$为偶数, 则
$$ C_S(w)=\left\{\begin{array}{ll} \frac{-p+q+1}{p q}, & w \in P, \\ \frac{-p+q-3}{p q}, & w \in Q, \\ \frac{-1}{p q}, & w \in Z_N^*。 \end{array}\right. $$ (23) 证明 由式(22), 引理2~4,7和8可得
$$\begin{array}{c} d_s(1, 0 ; \omega)=\\ \left\{\begin{array}{ll} \frac{(p-1)(q-1)}{4}+0+\frac{p-1}{2}+0, & \omega \in P, \\ \frac{(p-1)(q-1)}{4}+\frac{p-1}{2}+0+1, & \omega \in Q, \\ \frac{(p-2)(q-2)-3}{4}+\frac{q-1}{2}+\frac{p-1}{2}+1, & \omega \in D_0, \\ \frac{(p-2)(q-2)}{4}+\frac{q-1}{2}+\frac{p-3}{2}+1, & \omega \in D_1, \end{array}=\right.\\ \left\{\begin{array}{ll} \frac{p q+p-q-1}{4}, & \omega \in P, \\ \frac{p q+p-q+3}{4}, & \omega \in Q, \\ \frac{p q+1}{4}, & \omega \in D_0 \cup D_1 。 \end{array}\right. \end{array} $$ (24) 再由引理1可得如下定理。
定理2 设$(p-1)(q-1) / 4$为奇数, 则
$$ C_S(w)=\left\{\begin{array}{ll} \frac{-p+q-3}{p q}, & \omega \in P, \\ \frac{-p+q+1}{p q}, & \omega \in Q, \\ \frac{-3}{p q}, & \omega \in D_0, \\ \frac{1}{p q}, & \omega \in D_1 。 \end{array}\right. $$ (25) 证明与定理1的证明类似。
由定理1和定理2可以看出, 当$|p-q|$非常小时, 二阶广义分圆二元序列的自相关值差异很小。
对于二元序列的自相关值,最好的情形是$p-$$q=2$, 即$p$和$q$是孪生素数。在这种情形下, 当$(p-$ 1)$(q-1) / 4$为偶数时, 此类序列的自相关值$C_{s}(\omega)$是二值的,即这类序列具有理想自相关值;当$(p-$ 1)$(q-1) / 4$为奇数时, 此类序列的自相关值$C_{s}(\omega)$为四值。
另一种情形是当$p-q=4$时。在这种情形下, 当$(p-1)(q-1) / 4$为偶数时, 此类序列的自相关值$C_{s}(\omega)$是四值; 当$(p-1)(q-1) / 4$为奇数时, 此类序列的自相关值$C_{s}(\omega)$为三值。因此,这类序列具有好的自相关性。
2.2 周期为2p的二元序列的自相关值
引理9[4] 设$D_{0}^{(p)} 、D_{1}^{(p)} 、D_{0}^{(2 p)} 、D_{1}^{(2 p)}$是由1.2节中定义的二阶广义分圆类,则
(1) $2 \in D_{0}^{(p)}$当且仅当$p \equiv \pm 1(\text{mod} 8)$;
(2) $2 \in D_{1}^{(p)}$当且仅当$p \equiv \pm 3(\text{mod} 8)$。
引理10[19] 设$t$是一个奇数, 则对于$i=0, 1$, 有
(1) $2 D_{i}^{(p)}+p t(\text{mod} 2 p)= \begin{cases}D_{i}^{(2 p)}, & 2 \in D_{0}^{(p)}, \\ D_{i+1}^{(2 p)}, & 2 \in D_{1}^{(p)} 。\end{cases}$
(2) $D_{i}^{(2 p)}+2 p t(\text{mod} 2 p)=D_{i}^{(2 p)}$。
设$D_{0}^{(p)} 、D_{1}^{(p)}$是关于$p$的二阶广义分圆类, 定义
$$ (i, j)_p=\left|\left(D_i^{(p)}+1\right) \cap D_j^{(p)}\right|, i, j \in\{0, 1\}, $$ (26) 为模 p的二阶分圆数。
引理11[19] 若$p \equiv 1(\text{mod} 4)$, 则
$$ \begin{array}{c} (0, 1)_p=(1, 0)_p=(1, 1)_p=\frac{p-1}{4}, \\ (0, 0)_p=\frac{p-5}{4} ; \end{array} $$ 若$p \equiv 3(\text{mod} 4)$, 则
$$ \begin{array}{c} (1, 0)_p=(0, 0)_p=(1, 1)_p=\frac{p-3}{4}, \\ (0, 1)_p=\frac{p+1}{4} 。 \end{array} $$ 引理12[19] 对于任意$\tau \in Z_{p}^{*}, i=0, 1$, 有
(1)
$$ \left|\left(D_i^{(p)}+\tau\right)(\text{mod}p) \cap D_i^{(p)}\right|=\left\{\begin{array}{ll} (0, 0), & \tau \in D_i^{(p)}, \\ (1, 1), & \tau \in D_{i+1}^{(p)}。 \end{array}\right. $$ (2)
$$ \left|\left(D_i^{(p)}+\tau\right)(\text{mod}p) \cap D_{i+1}^{(p)}\right|=\left\{\begin{array}{ll} (0, 1), & \tau \in D_i^{(p)} , \\ (1, 0), & \tau \in D_{i+1}^{(p)}。 \end{array}\right. $$ (3) 若$(-\tau)(\text{mod}p) \cap D_{i}^{(p)}$, 则
$$ Z_{p}^{*} \cup\{0\} \subseteq\left(D_{i}^{(p)}+\tau\right)(\text{mod}p)。 $$ 引理13 设$\tau \in 2 Z_{p}^{*}, i \in Z_{2}$, 有
(1) 若$2 \in D_{0}^{(p)}$, 则
$$ \begin{array}{l} \left|\left(D_i^{(2 p)}+\tau\right) \bigcap 2 D_i^{(p)}\right|=\left\{\begin{array}{ll} (0, 0), & \tau \in D_i^{(2 p)}, \\ (1, 1), & \tau \in D_{i+10}^{(2 p)}。 \end{array}\right. \\ \left|\left(D_i^{(2 p)}+\tau\right) \bigcap 2 D_{i+1}^{(p)}\right|=\left\{\begin{array}{ll} (0, 1), & \tau \in D_i^{(2 p)}, \\ (1, 0), & \tau \in D_{i+1}^{(2 p)}。 \end{array}\right. \\ \left|\left(2 D_i^{(p)}+\tau\right) \cap D_i^{(2 p)}\right|=\left\{\begin{array}{ll} (0, 0), & \tau \in D_i^{(2 p)}, \\ (1, 1), & \tau \in D_{i+1}^{(2 p)}。 \end{array}\right. \\ \left|\left(2 D_i^{(p)}+\tau\right) \cap D_{i+1}^{(2 p)}\right|=\left\{\begin{array}{ll} (0, 1), & \tau \in D_i^{(2 p)}, \\ (1, 0), & \tau \in D_{i+1}^{(2 p)}。 \end{array}\right. \\ \end{array} $$ (2) 若$2 \in D_{1}^{(p)}$, 则
$$ \begin{array}{l} \left|\left(D_i^{(2 p)}+\tau\right) \cap 2 D_i^{(p)}\right|=\left\{\begin{array}{ll} (0, 1), & \tau \in D_i^{(2 p)}, \\ (1, 0), & \tau \in D_{i+1 }^{(2 p)}。 \end{array}\right. \\ \left|\left(D_i^{(2 p)}+\tau\right) \cap 2 D_{i+1}^{(p)}\right|=\left\{\begin{array}{ll} (0, 0), & \tau \in D_i^{(2 p)}, \\ (1, 1), & \tau \in D_{i+1}^{(2 p)}。 \end{array}\right. \\ \left|\left(2 D_i^{(p)}+\tau\right) \cap D_i^{(2 p)}\right|=\left\{\begin{array}{ll} (1, 0), & \tau \in D_i^{(2 p)}, \\ (0, 1), & \tau \in D_{i+1}^{(2 p)}。 \end{array}\right.\\ \left|\left(2 D_i^{(p)}+\tau\right) \cap D_{i+1}^{(2 p)}\right|=\left\{\begin{array}{ll} (1, 1), & \tau \in D_i^{(2 p)}, \\ (0, 0), & \tau \in D_{i+1}^{(2 p)}。 \end{array}\right. \end{array} $$ 引理14[19] 设$\tau \in Z_{2 p}^{*}, i \in Z_{2}$,
(1) 若$2 \in D_{0}^{(p)}$, 则
$$ \begin{array}{l} \left|\left(\mathrm{D}_i^{(2 p)}+\tau\right) \cap D_i^{(2 p)}\right|=\left\{\begin{array}{ll} (0, 0), & \tau \in D_i^{(p)}, \\ (1, 1), & \tau \in D_{i+1}^{(p)}。 \end{array}\right. \\ \left|\left(D_i^{(2 p)}+\tau\right) \cap D_{i+1}^{(2 p)}\right|=\left\{\begin{array}{ll} (0, 1), & \tau \in D_i^{(p)}, \\ (1, 0), & \tau \in D_{i+1}^{(p)}。 \end{array}\right. \\ \left|\left(2 D_i^{(p)}+\tau\right) \cap 2 D_i^{(p)}\right|=\left\{\begin{array}{ll} (0, 0), & \tau \in D_i^{(p)}, \\ (1, 1), & \tau \in D_{i+1}^{(p)}。 \end{array}\right. \\ \left|\left(2 D_i^{(p)}+\tau\right) \bigcap 2 D_{i+1}^{(p)}\right|=\left\{\begin{array}{ll} (0, 1), & \tau \in D_i^{(p)}, \\ (1, 0), & \tau \in D_{i+1}^{(p)}。 \end{array}\right. \\ \end{array} $$ (2) 若$2 \in D_{1}^{(p)}$, 则
$$ \begin{array}{l} \left|\left(D_i^{(2 p)}+\tau\right) \cap D_i^{(2 p)}\right|=\left\{\begin{array}{ll} (1, 1), & \tau \in D_i^{(p)}, \\ (0, 0), & \tau \in D_{i+1}^{(p)}。 \end{array}\right. \\ \left|\left(D_i^{(2 p)}+\tau\right) \cap D_{i+1}^{(2 p)}\right|=\left\{\begin{array}{ll} (1, 0), & \tau \in D_i^{(p)}, \\ (0, 1), & \tau \in D_{i+1}^{(p)}。 \end{array}\right. \\ \left|\left(2 D_i^{(p)}+\tau\right) \cap 2 D_i^{(p)}\right|=\left\{\begin{array}{ll} (0, 0), & \tau \in D_i^{(p)}, \\ (1, 1), & \tau \in D_{i+1}^{(p)}。 \end{array}\right. \\ \left|\left(2 D_i^{(p)}+\tau\right) \bigcap 2 D_{i+1}^{(p)}\right|=\left\{\begin{array}{ll} (0, 1), & \tau \in D_i^{(p)}, \\ (1, 0), & \tau \in D_{i+1}^{(p)}。 \end{array}\right. \\ \end{array} $$ 定理3 设$\left\{s_{i}\right\}$是由1.2节中定义的二元广义分圆序列,$p$是奇素数。
(1) 当$p \equiv 1(\text{mod} 8)$时, 序列$\left\{s_{i}\right\}$的自相关函数$C_{s}(\tau)$满足
$$ C_s(\tau)=\left\{\begin{array}{ll} 2 p, & \tau=0 \\ 2 p-4, & \tau=p, \\ -2, & \tau \in Z_{2 p}^* \cup 2 Z_p^*。 \end{array}\right. $$ (27) (2) 当$p \equiv 3(\text{mod} 8)$时, 序列$\left\{s_{i}\right\}$的自相关函数$C_{s}(\tau)$满足
$$ C_s(\tau)=\left\{\begin{array}{ll} 2 p, & \tau=0 \\ -2 p, & \tau=p, \\ 2, & \tau \in Z_{2 p}^*, \\ -2, & \tau \in 2 Z_p^*。 \end{array}\right. $$ (28) 证明 (1) 当$p \equiv 1(\text{mod} 8)$时, 根据引理9可知,$2 \in D_{0}^{(p)}$, 所以
$$ \begin{array}{c} C_s(\tau)=\sum\limits_{i=0}^{2 p-1}(-1)^{s_{i+\tau}-s_i}=\sum\limits_{i \in\{0, p\}}(-1)^{s_{i+\tau}-s_i}+ \\ \sum\limits_{i \in D_0^{(2 p)} \cup D_1^{(2 p)}}(-1)^{s_{i+\tau}-s_i}+\sum\limits_{i \in 2 D_0^{(p)} \cup 2 D_1^{(p)}}(-1)^{s_{i+\tau}-s_i} 。 \end{array} $$ 若$\tau=0$, 则$C_{s}(\tau)=2 p$。
若$\tau=p$, 则$\sum\limits_{i \in\{0, p\}}(-1)^{s_{i+\tau}-s_{i}}=-2$, 由引理10可知$D_{i}^{(2 p)}+p=2 D_{i}^{(p)}, i=0, 1$。因此
$$ C_s(\tau)=-2+2 p-2=2 p-4 。 $$ 若$\tau \in D_{0}^{(2 p)}$, 则$s_{\tau}=0$, 由引理10可知,$p+\tau \in p+$$D_{0}^{(2 p)} \in 2 D_{0}^{(p)}$, 所以$s_{p+\tau}=0$。因此
$\sum\limits_{i \in\{0, p\}}(-1)^{s_{i+\tau}-s_i}=0$, 再根据引理12和引理13可知
$$ \begin{array}{l} \sum\limits_{t \in D_0^{(2 p)} \cup D_1^{(2 p)}}(-1)^{s_{t+\tau}-s_t}+\sum\limits_{t \in 2 D_0^{(p)} \cup 2 D_1^{(p)}}(-1)^{s_{t+\tau}-s_t}= \\ 2((0, 1)-(1, 0)+(0, 0)-(1, 1))=-2, \end{array} $$ 所以$C_{s}(\tau)=-2$。
同理可得, 若$\tau \in D_{1}^{(2 p)}$, 则$C_{S}(\tau)=-2$; 若$\tau \in 2 D_{0}^{(p)}$, 则$C_{S}(\tau)=-2$; 若$\tau \in 2 D_{1}^{(p)}$, 则$C_{S}(\tau)=$-2。
(2) 当$p \equiv 3(\text{mod} 8)$时, 证明与(1) 类似。
定理3表明当$p \equiv 1(\text{mod} 8)$时, 序列$\left\{s_{i}\right\}$的自相关函数是三值; 当$p \equiv 3(\text{mod} 8)$时, 序列$\left\{s_{i}\right\}$的自相关函数是四值,即这类序列具有低值自相关性。
3. 结束语
基于广义分圆类,本文分别构造了两类周期为$p q$和$2 p$的二元广义分圆序列,利用分圆数和差集理论确定了这2类序列的自相关函数值。当$(p-$ 1)$(q-1) / 4$为偶数时, 周期为$p q$的二元序列自相关函数值为三值; 当$(p-1)(q-1) / 4$为奇数时, 周期为$p q$的二元序列自相关函数值为四值。当$p \equiv 1(\text{mod} 8)$时, 周期为$2 p$的二元序列自相关函数值为三值; 当$p \equiv 3(\text{mod} 8)$时, 周期为$2 p$的二元序列自相关函数值为四值。结果表明,这2类序列都具有好的密码学性质。
-
[1] WANG Y, HAN X L, WANG W Q, et al. Linear complexity over Fq and 2-adic complexity of a class of binary generalized cyclotomic sequences with low-value autocorrelation[J]. Designs, Codes and Cryptography, 2022, 90: 1695-1712. doi: 10.1007/s10623-022-01068-6 [2] TOPUZOGGLU A, WINTERHOF A. Pseudorandom sequences[J]. Topics in Geometry, Coding Theory and Cryptography, Algebra and Applications, 2006, 6(AA): 135-166. [3] CHEN X, LIU H, Autocorrelation values of generalized cyclotomic sequences with period pn+1[J]. Mathematics, 2019, 7(10): 950. [4] WANG Q, KONG W, YAN Y, et al. Autocorrelation of a class of quaternary sequences of period 2pm[J]. arXiv: 2002.00375, 2020. [5] DING C, HELLESETH T, SHAN W. On the linear complexity of Legendre sequences[J]. IEEE Transaction on Communications, 1998, 44: 1276-1278. [6] JANG W J, KIM Y S, KIM S H, et al. New quaternary sequences with ideal autocorrelation constructed from binary sequences with ideal autocorrelation[J]. IEEE International Symposium on Information Theory, 2009, E96(A): 278-281. [7] LIM T, NO J S, CHUNG H. New construction of quaternary sequences with good correlation using binary sequences with good correlation[J]. IEICE Transaction, Fundamentals, 2011, 94(8): 1701-1705. [8] EDEMSKIY V, IVANOV A. The linear complexity of balanced quaternary sequences with optimal autocorrelation value[J]. Cryptography and Communications, 2015, 7(4): 485-496. doi: 10.1007/s12095-015-0130-0 [9] TANG X, DING C. New classes of balanced quaternary and almost balanced binary sequences with optimal autocorrelation value[J]. IEEE Transactions on Information Theory, 2010, 56(12): 6398-6405. doi: 10.1109/TIT.2010.2081170 [10] CHUNG J H, HAN Y K, YANG K. New quaternary sequences with even period and three-valued autocorrelation[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2010, 93(1): 309-315. [11] DING C. Cyclotomic constructions of cyclic codes with length being the product of two primes[J]. IEEE Transactions on Information Theory, 2011, 58(4): 2231-2236. [12] LIU H, CHEN X. Autocorrelation values and linear complexity of new generalized cyclotimic sequences[J]. Acta Mathematica Sinica (Chinese Series), 2019, 62(2): 233-246. [13] KIM Y J, HONG Y P, SONG H Y. Autocorrelation of some quaternary cyclotomic sequences of length 2p[J]. IEICE Transaction on Fundamentals of Electronics, Communications and Computer Sciences, 2008, 91(12): 3679-3684. [14] DU X N, CHEN Z X. Linear complexity of quaternary sequences generated using generalized cyclotomic classes modulo 2p[J]. IEICE Transaction on Fundamentals of Electronics, Communications and Computer Sciences, 2011, 94(5): 1214-1217. [15] JIA W J, GAO J T, ZHANG P. Linear complexity and autocorrelation of a new class of binary generalized cyclotomic sequences of order two and length pqr[J]. Journal of Systems Engineering and Electronics, 2019, 30(4): 651-661. doi: 10.21629/JSEE.2019.04.03 [16] PEI D, SALOMAA A, DING C. Chinese remainder theorem: applications in computing, coding, cryptography[M]. Hongkong: World Scientific, 1996. [17] WHITEMAN A L. A family of difference sets[J]. Illinois Journal of Mathematics, 1962, 6(1): 107-121. [18] DING C S. Autocorrelation values of generalized cyclotomic sequences of order two[J]. IEEE Transactions on Information Theory, 1998, 44(4): 1699-1702. doi: 10.1109/18.681354 [19] KE P H, ZHANG J, ZHANG S Y. On the linear complexity and the autocorrelation of generalized cyclotomic binary sequences of length 2pm[J]. Designs, Codes and Cryptography, 2013, 67(3): 325-339. doi: 10.1007/s10623-012-9610-9