# The 4-adic complexity of quaternary sequences with low autocorrelation and
high linear complexity

Feifei Yan  School of Mathematics and Statistics, Fujian Normal University,
Fuzhou, Fujian, 350117, P. R. China Pinhui Ke Corresponding author:
<EMAIL_ADDRESS>This work is supported by the National Natural Science
Foundation of China (No.62272420), Natural Science Foundation of Fujian
Province (No. 2023J01535). Key Laboratory of Analytical Mathematics and
Applications (Ministry of Education), Fujian Normal University, Fuzhou,
Fujian, 350117, P. R. China Lingmei Xiao  Provincial Key Laboratory of Applied
Mathematics, Putian University, Putian, Fujian, 351100, P. R. China

###### Abstract

Recently, Jiang et al. proposed several new classes of quaternary sequences
with low autocorrelation and high linear complexity by using the inverse Gray
mapping (JAMC, 69 (2023): 689–706). In this paper, we estimate the 4-adic
complexity of these quaternary sequences. Our results show that these
sequences have large 4-adic complexity to resist the attack of the rational
approximation algorithm.

Keywords: Quaternary sequence, 4-adic complexity, cyclotomy, inverse Gray
mapping

##  1 Introduction

Pseudo-random sequences are widely used in many fields, such as modern
communication, software testing, radar system, coding theory, stream cipher
systems, and so on [1, 2]. In practical applications, sequences are required
to have low correlation and high complexity. For the sake of simplify
implementation, binary and quaternary sequences with good properties are
preferred sequences in many applications.

Theoretically, quaternary sequences can be generated by linear feedback shift
registers(LFSRs) [3] or feedback with carry shift registers(FCSRs) [4, 5]. The
shortest lengths of LFSR and FCSR that can generate a given quaternary
sequence are called linear complexity and 4-adic complexity, respectively.
Compared to the linear complexity, research on the 4-adic complexity of
quaternary sequences has not been fully developed. The concept of 4-adic
complexity was proposed by Klapper, Goresky and Xu in the 1990’s [5, 6]. In
order to resist the attack of the rational approximation algorithm(RAA), the
4-adic complexity of a quaternary sequence with period $N$ should exceed
$\frac{N-16}{6}$ [5]. Recently, some works have been devoted to studying the
4-adic complexity of sequences [7, 8, 9, 10, 11, 12, 13]. Yang et al. proved
the 4-adic complexity of some even period quaternary sequences with ideal
autocorrelation, and the results show that the 4-adic complexity of these
quaternary sequences are large enough to resist the attack of the RAA [7, 8].
Edemskiy et al. considered the symmetric 4-adic complexity of several odd
period quaternary sequences with low autocorrelation, and showed that these
sequences have a sufficiently large 4-adic complexity to resist the attack of
the RAA [10, 11].

Quaternary sequences can be constructed by using the inverse Gray mapping [14,
15, 16]. Recently, Jiang et al. constructed some new quaternary sequences by
using the inverse Gray mapping, which have low correlation and high linear
complexity [14]. In this paper, we will estimate the 4-adic complexity of
these sequences.

The rest of this paper is organized as follows. In Section 2, we recall some
related concepts and the required lemmas. In Section 3, we estimate the 4-adic
complexity of quaternary sequences proposed in [14]. And the last section is
the conclusion of this paper.

##  2 Preliminaries

In this section, we will introduce some notations and concepts which will be
used later.

###  2.1 Cyclotomic classes and cyclotomic numbers

Let $p$ be an odd prime number with $p=4f+1=x^{2}+4y^{2}$, where $f$ is an odd
integer, $y$ is an integer, and $x\equiv 1\pmod{4}$. Let $\theta$ be a
primitive element of $\mathbb{F}_{p}$. Define
$D_{i}=\left\\{\theta^{i+4j}:j=0,1,2,\dots,f-1\right\\}$, where $i=0,1,2,3$.
$D_{i}$ is called the cyclotomic classes of order 4 in $\mathbb{F}_{p}$. It is
easy to verify that $\mathbb{F}_{p}=\left\\{0\right\\}\cup D_{1}\cup D_{2}\cup
D_{3}\cup D_{4}$.

###### Definition 2.1

[17] The cyclotomic numbers of order 4 in $\mathbb{F}_{p}$ are defined as

$(i,j)_{4}=|(D_{i}+1)\cap D_{j}|,0\leq i,j\leq 3.$

The formula for calculating cyclotomic numbers of order 4 was given as
follows.

###### Lemma 2.1

[18] Let $p=x^{2}+4y^{2}$, $x,y\in\mathbb{Z}$ and $x\equiv 1\pmod{4}$. When
$p\equiv 5\pmod{8}$, the relationship and formula of these cyclotomic numbers
are shown in Table 1,

Table 1:

$\mathrm{\;The\;relationship\;between\;cyclotomic\;numbers}$ when $p\equiv
5\pmod{8}$

$(i,j)_{4}$ | $0$ | $1$ | $2$ | $3$
---|---|---|---|---
$0$ | A | B | C | D
$1$ | E | E | D | B
$2$ | A | E | A | E
$3$ | E | D | B | E

where

$A=\frac{p-7+2x}{16},B=\frac{p+1+2x-8y}{16},C=\frac{p+1-6x}{16},$
$D=\frac{p+1+2x+8y}{16},E=\frac{p-3-2x}{16}.$

$y$ is two possible values, depending on the choice of the primitive element
$\theta$ of $\mathbb{F}_{p}$.

Define $\eta_{i}(4)=\sum_{t\in D_{i}}4^{t}(\mathrm{mod}\;4^{p}-1),i=0,1,2,3.$
Obviously, we have
$\eta_{0}(4)+\eta_{1}(4)+\eta_{2}(4)+\eta_{3}(4)\equiv-1(\textup{mod}\>\frac{4^{p}-1}{3})$.
And we have the following lemma.

###### Lemma 2.2

[12] Let $k,l=0,1,2,3$. Then

$\eta_{l}(4)\cdot\eta_{l+k}(4)\equiv\sum_{f=0}^{3}(k,f)_{4}\eta_{f+l}(4)+\delta(\textup{mod}\;4^{p}-1),$

where

$\delta=\begin{cases}\frac{p-1}{4},\qquad&\textup{if }\;p\equiv
1(\textup{mod}8),k=0\textup{ or }p\equiv 5(\textup{mod}8),k=2,\\\
0,&\textup{otherwise }.\end{cases}$

Let $H(4)=\eta_{0}(4)+\eta_{2}(4)-\eta_{1}(4)-\eta_{3}(4)$. Then we have the
following lemma.

###### Lemma 2.3

[19] $H^{2}(4)\equiv p(\textup{mod}\;\frac{4^{p}-1}{3})$.

###  2.2 Definition of sequences

Let $\mathbb{Z}_{N}=\left\\{0,1,\dots,N-1\right\\}$ denotes the ring of
residue classes of modulo $N$ and $\mathbb{Z}_{N}^{*}$ denotes the set of the
elements in $\mathbb{Z}_{N}$ that are coprime with $N$. The set
$\textup{Supp}(s)=\left\\{t\in\mathbb{Z}_{N}:s(t)=1\right\\}$ is called the
support set of a binary sequence $s$ with a period of $N$. The inverse Gray
mapping $\phi$ is defined by $\phi[0,0]=0$, $\phi[0,1]=1$, $\phi[1,1]=2$,
$\phi[1,0]=3$. This is a common method for constructing quaternary sequences.

In reference [14], four classes of quaternary sequences with period $p$ were
defined by using inverse Gray mapping. Due to the different support sets of
component sequences, there are four sequences in each class. The first class
of quaternary sequences are $u_{1}=\phi[s_{1},s_{2}]$,
$u_{2}=\phi[s_{1},s_{3}]$, $u_{3}=\phi[s_{2},s_{4}]$,
$u_{4}=\phi[s_{3},s_{4}]$; the second class of quaternary sequences are
$u_{5}=\phi[s_{1},s_{2}+1]$, $u_{6}=\phi[s_{1},s_{3}+1]$,
$u_{7}=\phi[s_{2},s_{4}+1]$, $u_{8}=\phi[s_{3},s_{4}+1]$; the third class of
quaternary sequences are $u_{9}=\phi[s_{1}+1,s_{2}]$,
$u_{10}=\phi[s_{1}+1,s_{3}]$, $u_{11}=\phi[s_{2}+1,s_{4}]$,
$u_{12}=\phi[s_{3}+1,s_{4}]$; the fourth class of quaternary sequences are
$u_{13}=\phi[s_{1}+1,s_{2}+1]$, $u_{14}=\phi[s_{1}+1,s_{3}+1]$,
$u_{15}=\phi[s_{2}+1,s_{4}+1]$, $u_{16}=\phi[s_{3}+1,s_{4}+1]$. Here $s_{1}$,
$s_{2}$, $s_{3}$, $s_{4}$ are four binary cyclotomic sequences with support
sets $D_{0}\cup D_{1}$, $D_{0}\cup D_{3}$, $D_{1}\cup D_{2}$ and $D_{2}\cup
D_{3}$, respectively.

For a quaternary sequence $u$ with period $N$, its generating polynomial
$U(x)$ is defined as $\sum_{t=0}^{N-1}u(t)x^{t}$. The 4-adic complexity,
denoted by $\Phi_{4}(u)$, is defined by

$\lfloor\mathrm{log}_{4}(\dfrac{4^{N}-1}{\mathrm{gcd}(4^{N}-1,U(4))}+1)\rfloor,$

where $\lfloor m\rfloor$ is the greatest integer that is less than or equal to
$m$ [7].

In the rest of the paper, $(\frac{\cdot}{\cdot})$ denotes the Legendre symbol.

##  3 4-Adic complexity of quaternary sequences

In this section, we will estimate the 4-adic complexity of four classes of
quaternary sequences in reference [14].

###### Lemma 3.1

Let $p=x^{2}+4y^{2}$, where $x,y\in\mathbb{Z}$ and $x\equiv
1(\textup{mod}\;4)$. When $p\equiv 5(\textup{mod}\;8)$, then

  * (1)

$4(3+\eta_{1}(4)+2\eta_{2}(4)+3\eta_{3}(4))(3+\eta_{3}(4)+2\eta_{0}(4)+3\eta_{1}(4))\equiv-2(3+4y)H(4)+5p+9(\textup{mod}\;\frac{4^{p}-1}{3});$

  * (2)

$4(1+\eta_{2}(4)+2\eta_{1}(4)+3\eta_{0}(4))(1+\eta_{0}(4)+2\eta_{3}(4)+3\eta_{2}(4))\equiv-2(1+4y)H(4)+5p+1(\textup{mod}\;\frac{4^{p}-1}{3});$

  * (3)

$4(\eta_{3}(4)+2\eta_{0}(4)+3\eta_{1}(4))(\eta_{1}(4)+2\eta_{2}(4)+3\eta_{3}(4))\equiv
2(3-4y)H(4)+5p+9(\textup{mod}\;\frac{4^{p}-1}{3});$

  * (4)

$4(\eta_{2}(4)+2\eta_{3}(4)+3\eta_{0}(4))(\eta_{0}(4)+2\eta_{1}(4)+3\eta_{2}(4))\equiv-2(3-4y)H(4)+5p+9(\textup{mod}\;\frac{4^{p}-1}{3});$

  * (5)

$4(\eta_{3}(4)+2\eta_{2}(4)+3\eta_{1}(4))(\eta_{1}(4)+2\eta_{0}(4)+3\eta_{3}(4))\equiv
2(3+4y)H(4)+5p+9(\textup{mod}\;\frac{4^{p}-1}{3});$

  * (6)

$4(1+\eta_{3}(4)+2\eta_{0}(4)+3\eta_{1}(4))(1+\eta_{1}(4)+2\eta_{2}(4)+3\eta_{3}(4))\equiv
2(1-4y)H(4)+5p+1(\textup{mod}\;\frac{4^{p}-1}{3});$

  * (7)

$4(1+\eta_{1}(4)+2\eta_{0}(4)+3\eta_{3}(4))(1+\eta_{3}(4)+2\eta_{2}(4)+3\eta_{1}(4))\equiv
2(1+4y)H(4)+5p+1(\textup{mod}\;\frac{4^{p}-1}{3});$

  * (8)

$4(2+\eta_{1}(4)+2\eta_{0}(4)+3\eta_{3}(4))(2+\eta_{3}(4)+2\eta_{2}(4)+3\eta_{1}(4))\equiv-2(1-4y)H(4)+5p+1(\textup{mod}\;\frac{4^{p}-1}{3}).$

Proof. The proof of this lemma can be completed by using Lemmas 2.1 and 2.2.
Since the proofs are similar, we only prove (1). Firstly, it is easy to verify
that

$\displaystyle
4(3+\eta_{1}(4)+2\eta_{2}(4)+3\eta_{3}(4))(3+\eta_{3}(4)+2\eta_{0}(4)+3\eta_{1}(4))$
$\displaystyle=36+24\eta_{0}(4)+48\eta_{1}(4)+24\eta_{2}(4)+48\eta_{3}(4)+8\eta_{1}(4)\eta_{0}(4)+12\eta_{1}(4)\eta_{1}(4)$
$\displaystyle+4\eta_{1}(4)\eta_{3}(4)+16\eta_{2}(4)\eta_{0}(4)+24\eta_{2}(4)\eta_{1}(4)+8\eta_{2}(4)\eta_{3}(4)+24\eta_{3}(4)\eta_{0}(4)$
$\displaystyle+36\eta_{3}(4)\eta_{1}(4)+12\eta_{3}(4)\eta_{3}(4).$

According to Lemmas 2.1 and 2.2, we have

$\eta_{1}(4)\eta_{0}(4)=E\eta_{0}(4)+E\eta_{1}(4)+D\eta_{2}(4)+B\eta_{3}(4)(\textup{mod}\;4^{p}-1);$
$\eta_{1}(4)\eta_{1}(4)=D\eta_{0}(4)+A\eta_{1}(4)+B\eta_{2}(4)+C\eta_{3}(4)(\textup{mod}\;4^{p}-1);$
$\eta_{1}(4)\eta_{3}(4)=E\eta_{0}(4)+A\eta_{1}(4)+E\eta_{2}(4)+A\eta_{3}(4)+\frac{p-1}{4}(\textup{mod}\;4^{p}-1);$
$\eta_{2}(4)\eta_{0}(4)=A\eta_{0}(4)+E\eta_{1}(4)+A\eta_{2}(4)+E\eta_{3}(4)+\frac{p-1}{4}(\textup{mod}\;4^{p}-1);$
$\eta_{2}(4)\eta_{1}(4)=B\eta_{0}(4)+E\eta_{1}(4)+E\eta_{2}(4)+D\eta_{3}(4)(\textup{mod}\;4^{p}-1);$
$\eta_{2}(4)\eta_{3}(4)=D\eta_{0}(4)+B\eta_{1}(4)+E\eta_{2}(4)+E\eta_{3}(4)(\textup{mod}\;4^{p}-1);$
$\eta_{3}(4)\eta_{0}(4)=E\eta_{0}(4)+D\eta_{1}(4)+B\eta_{2}(4)+E\eta_{3}(4)(\textup{mod}\;4^{p}-1);$
$\eta_{3}(4)\eta_{1}(4)=E\eta_{0}(4)+A\eta_{1}(4)+E\eta_{2}(4)+A\eta_{3}(4)+\frac{p-1}{4}(\textup{mod}\;4^{p}-1);$
$\eta_{3}(4)\eta_{3}(4)=B\eta_{0}(4)+C\eta_{1}(4)+D\eta_{2}(4)+A\eta_{3}(4)(\textup{mod}\;4^{p}-1),$

then we get

$\displaystyle
4(3+\eta_{1}(4)+2\eta_{2}(4)+3\eta_{3}(4))(3+\eta_{3}(4)+2\eta_{0}(4)+3\eta_{1}(4))$
$\displaystyle=(16A+36B+20D+72E+24)\eta_{0}(4)$
$\displaystyle+(52A+8B+12C+24D+48E+48)\eta_{1}(4)$
$\displaystyle+(16A+36B+20D+72E+24)\eta_{2}(4)$
$\displaystyle+(52A+8B+12C+24D+48E+48)\eta_{3}(4)+14p+22(\textup{mod}\;4^{p}-1).$

Again by Lemma 2.1, we get

$\displaystyle
4(3+\eta_{1}(4)+2\eta_{2}(4)+3\eta_{3}(4))(3+\eta_{3}(4)+2\eta_{0}(4)+3\eta_{1}(4))$
$\displaystyle=(9p+7-8y)\eta_{0}(4)+(9p+19+8y)\eta_{1}(4)+(9p+7-8y)\eta_{2}(4)$
$\displaystyle+(9p+19+8y)\eta_{3}(4)+14p+22(\textup{mod}\;4^{p}-1)$
$\displaystyle=(9p+13)(\eta_{0}(4)+\eta_{1}(4)+\eta_{2}(4)+\eta_{3}(4))$
$\displaystyle-(8y+6)(\eta_{0}(4)-\eta_{1}(4)+\eta_{2}(4)-\eta_{3}(4))+14p+22(\textup{mod}\;4^{p}-1)$
$\displaystyle\equiv-2(3+4y)H(4)+5p+9(\textup{mod}\;\frac{4^{p}-1}{3}),$

which completes the proof.

###### Lemma 3.2

Let $U_{3}(4)=\eta_{2}(4)+2\eta_{3}(4)+3\eta_{0}(4)(\textup{mod}\;4^{p}-1)$.
If $d_{3}>3$ is a prime divisor of $gcd(U_{3}(4),\frac{4^{p}-1}{3})$. Then
either $d_{3}=11$ or $d_{3}=1+2p$ where $3p=4(3-4y)^{2}+83$.

Proof. Let $p\equiv 5\pmod{8}$ and $d_{3}>3$ be a prime divisor of
$\textup{gcd}(U_{3}(4),\frac{4^{p}-1}{3})$. According to Lemma 3.1 (4), we
have $d_{3}|-2(3-4y)H(4)+5p+9$, that is $2(3-4y)H(4)\equiv
5p+9(\textup{mod}\;d_{3})$. Then by Lemma 2.3 we have $4(3-4y)^{2}p\equiv
25p^{2}+90p+81(\textup{mod}\;d_{3})$. From $4^{p}\equiv
1(\textup{mod}\;d_{3})$ and $d_{3}\not=3$, we have the order of 4 modulo
$d_{3}$ is $p$. Since $d_{3}$ is odd prime, by Euler’s Theorem we have
$4^{d_{3}-1}\equiv 1(\textup{mod}\;d_{3})$. Thus $p|d_{3}-1$. Then
$d_{3}=1+2fp$, where $f\in\mathbb{N_{+}}$, that is
$2fp\equiv-1(\textup{mod}\;d_{3})$. Hence we have
$-4(3-4y)^{2}+25p+90-162f\equiv 0(\textup{mod}\;d_{3})$ or
$-4(3-4y)^{2}+25p+90-162f=(1+2h)(1+2fp)$. From the last congruence we get
$3-2f\equiv 1+2h+2f+4fh\pmod{8}$. Thus $h\equiv 1\pmod{2}$ and $1+2h=3+8t$
where $t\in\mathbb{Z}$. So, we get

$-4(3-4y)^{2}+25p+90-162f=(3+8t)(1+2fp)$ (1)

The discussion can be divided into three cases as follows.

(i) Case 1: If $t<0$, since $25p+90-4(3-4y)^{2}\geq
36y^{2}+96y+79=(6y+8)^{2}+15>0$, then by (1) we have $-162f<(3+8t)(1+2fp)$,
that is $162f>(-3-8t)(1+2fp)\geq 5+10fp$. Hence $p=5$ or $p=13$. Combining (1)
we have, when $p=5$, $d_{3}=11$; when $p=13$, we obtain a contradiction.

(ii) Case 2: If $t>0$, since $90-162f-4(3-4y)^{2}<0$, then by (1) we get
$25p>(3+8t)(1+2fp)$. Hence $f=1$, $t=1$, that is $d_{3}=1+2p$ is a prime
divisor of $\frac{4^{p}-1}{3}$ and $3p=4(3-4y)^{2}+83$.

(iii) Case 3: If $t=0$, we have $-4(3-4y)^{2}+25p+90-162f=3(1+2fp)$. Since
$90-4(3-4y)^{2}-162f-3<0$, it follows that $25p>6fp$. Hence, the possible
values of $f$ are $1,2,3,4$ and $-y^{2}+p\equiv 0\pmod{3}$, thus $p\equiv
y^{2}\equiv 1\pmod{3}$. In this case $f\not=1$ and $f\not=4$; if not,
$1+2fp\equiv 0\pmod{3}$, which is contradictory.

(iii-a) Let $f=2$. Then $d_{3}=1+4p$ and $d_{3}\equiv 5\pmod{8}$. Thus
$(\frac{2}{d_{3}})=(-1)^{\frac{d_{3}^{2}-1}{8}}=-1$, that is 2 is not a
quadratic residue of modulo $d_{3}$. Further $2^{2p}\not\equiv
1(\textup{mod}\;d_{3})$. Then $4^{p}\not\equiv 1(\textup{mod}\;d_{3})$. This
contradicts with $d_{3}|4^{p}-1$, thus $d_{3}\not=1+4p$.

(iii-b) Let $f=3$. Then $d_{3}=1+6p$, thus $-4(3-4y)^{2}+25p+90-486=3(1+6p)$,
that is $-4(3-4y)^{2}=7(57-p)$. Hence $3-4y=7k$, where $k\in\mathbb{Z}$ and
$-4\times 7k^{2}+p-57=0$, then $p=4\times 7k^{2}+57\equiv 1(\textup{mod}\;7)$,
also by $p\equiv 5\pmod{8}$ and Chinese Remainder Theorem, we arrive at a
contradiction.

The proof is completed.

###### Theorem 3.1

Let $u_{3}=\phi[s_{2},s_{4}]$. Then the 4-adic complexity of quaternary
sequence $u_{3}$ satisfies
$\Phi_{4}(u_{3})\geq\lfloor\textup{log}_{4}(\frac{4^{p}-1}{3(1+2p)}+1)\rfloor$.

Proof. To calculate the 4-adic complexity of $u_{3}=\phi[s_{2},s_{4}]$, we
need to consider $\textup{gcd}(U_{3}(4),4^{p}-1)$. Since

$\displaystyle U_{3}(4)$
$\displaystyle=\sum_{t=0}^{p-1}u_{3}(t)4^{t}(\textup{mod}\;4^{p}-1)$
$\displaystyle=\sum_{t=0}^{p-1}\phi[s_{2}(t),s_{4}(t)]4^{t}(\textup{mod}\;4^{p}-1)$
$\displaystyle=\sum_{\begin{subarray}{c}t=0\\\ t\in
D_{2}\end{subarray}}^{p-1}4^{t}+2\sum_{\begin{subarray}{c}t=0\\\ t\in
D_{3}\end{subarray}}^{p-1}4^{t}+3\sum_{\begin{subarray}{c}t=0\\\ t\in
D_{0}\end{subarray}}^{p-1}4^{t}(\textup{mod}\;4^{p}-1)$
$\displaystyle=\eta_{2}(4)+2\eta_{3}(4)+3\eta_{0}(4)(\textup{mod}\;4^{p}-1),$

we have $U_{3}(4)\equiv 6\times\frac{p-1}{4}\equiv 0\pmod{3}$ and $4^{p}\equiv
1\pmod{3}$, hence 3 is a divisor of $\textup{gcd}(U_{3}(4),4^{p}-1)$. If
$9|4^{p}-1$, then from $4^{3}\equiv 1\pmod{9}$ and $4^{p}\equiv 1\pmod{9}$, we
obtain $p=3$, which contradicts with $p\equiv 5\pmod{8}$. Thus 9 does not
divide $4^{p}-1$, that is 9 does not divide $\textup{gcd}(U_{3}(4),4^{p}-1)$.

Let $p\equiv 5\pmod{8}$ and $r_{3}$ be a divisor of
$\textup{gcd}(U_{3}(4),4^{p}-1)$ and $\textup{gcd}(r_{3},3)=1$. For $p=5$, by
the definition of sequence, $U_{3}(4)=4^{4}+2\times 4^{3}+3\times 4=396$, thus
$\textup{gcd}(U_{3}(4),4^{5}-1)=\textup{gcd}(396,1023)=33$ and
$\Phi_{4}(u_{3})=2$. For $p>5$, according to Lemma 3.2 we get $r_{3}$ is a
power of $2p+1$ and $2p+1$ is a prime satisfying $3p=4(3-4y)^{2}+83$. If
$(2p+1)^{2}|r_{3}$, by Lemma 3.1 (4), we get $(2p+1)^{2}|-2(3-4y)H(4)+5p+9$,
thus $4(3-4y)^{2}p\equiv 25p^{2}+90p+81(\textup{mod}\;(2p+1)^{2})$ and by
Lemma 3.2 we have $3p=4(3-4y)^{2}+83$, that is $4(3-4y)^{2}=3p-83$. Thus
$(3p-83)p-25p^{2}-90p-81\equiv 0(\textup{mod}\;(2p+1)^{2})$. Then we have
$-22p^{2}-173p-81=2(2p+1)^{2}m$, where $m\in\mathbb{Z}$. This is impossible.

Therefore, the possible prime factor of $\textup{gcd}(U_{3}(4),4^{p}-1)$ is
$2p+1$, and there is no repetition factor. And
$\textup{gcd}(U_{3}(4),4^{p}-1)=3$ when $2p+1$ is not a prime divisor of
$4^{p}-1$, which completes the proof.

###### Theorem 3.2

Let $u_{1}=\phi[s_{1},s_{2}]$, $u_{9}=\phi[s_{1}+1,s_{2}]$,
$u_{11}=\phi[s_{2}+1,s_{4}]$. Then for $i=1,9,11$, the 4-adic complexity of
these quaternary sequences $u_{i}$ satisfies
$\Phi_{4}(u_{i})\geq\lfloor\textup{log}_{4}(\frac{4^{p}-1}{3(1+2p)}+1)\rfloor$,
where $1+2p=11$ or the $p$ in $1+2p$ satisfies $3p=4(3-4y)^{2}+83$.

Proof. Since the proof is similar to Theorem 3.1, we omit it.

###### Lemma 3.3

Let $U_{5}(4)=1+\eta_{2}(4)+2\eta_{1}(4)+3\eta_{0}(4)(\textup{mod}\;4^{p}-1)$.
If $d_{5}>3$ is a prime divisor of $gcd(U_{5}(4),\frac{4^{p}-1}{3})$. Then the
possible values of $d_{5}$ are (1) $d_{5}=11$; (2) $d_{5}=1+2p$ and
$3p=4(1+4y)^{2}+3$; (3) $d_{5}=1+6p$ and $7p=4(1+4y)^{2}-1$; (4) $d_{5}=1+8p$
and $p=4(1+4y)^{2}+1$.

Proof. Let $p\equiv 5\pmod{8}$ and $d_{5}>3$ be a prime divisor of
$\textup{gcd}(U_{5}(4),\frac{4^{p}-1}{3})$. According to Lemma 3.1 (2), we
have $d_{5}|-2(1+4y)H(4)+5p+1$, thus $5p+1\equiv
2(1+4y)H(4)(\textup{mod}\;d_{5})$. Then by Lemma 2.3 we have
$4(1+4y)^{2}p\equiv 25p^{2}+10p+1(\textup{mod}\;d_{5})$. From $4^{p}\equiv
1(\textup{mod}\;d_{5})$ and $d_{5}\not=3$, we have the order of 4 modulo
$d_{5}$ is $p$. Since $d_{5}$ is odd prime, by Euler’s Theorem we have
$4^{d_{5}-1}\equiv 1(\textup{mod}\;d_{5})$. Thus $p|d_{5}-1$. Then
$d_{5}=1+2fp$, where $f\in\mathbb{N_{+}}$, that is
$2fp\equiv-1(\textup{mod}\;d_{5})$. Hence we have
$-4(1+4y)^{2}+25p+10-2f\equiv 0(\textup{mod}\;d_{5})$ or
$-4(1+4y)^{2}+25p+10-2f=(1+2h)(1+2fp)$. From the last congruence we get
$3-2f\equiv 1+2f+2h+4fh(\textup{mod}\;8)$. Thus $h\equiv 1(\textup{mod}\;2)$
and $1+2h=3+8t$ where $t\in\mathbb{Z}$. So, we get

$-4(1+4y)^{2}+25p+10-2f=(3+8t)(1+2fp)$ (2)

The discussion can be divided into three cases as follows.

(i) Case 1: If $t<0$, since $25p+10-4(1+4y)^{2}\geq
36y^{2}-32y+31=(6y-\frac{8}{3})^{2}+\frac{215}{9}>0$, then by (2) we have
$-2f<(3+8t)(1+2fp)$, that is $2f>(-3-8t)(1+2fp)\geq 5+10fp$. It is impossible.

(ii) Case 2: If $t>0$, since $10-2f-4(1+4y)^{2}<0$, then by (2) we get that
$25p>(3+8t)(1+2fp)$. Hence $f=1,t=1$, that is $d_{5}=1+2p$ is a prime divisor
of $\frac{4^{p}-1}{3}$ and $3p=4(1+4y)^{2}+3$.

(iii) Case 3: If $t=0$, we have $-4(1+4y)^{2}+25p+10-2f=3(1+2fp)$. Since
$10-2f-4(1+4y)^{2}-3<0$, it follows that $25p>6fp$. Hence, the possible values
of $f$ are $1,2,3,4$.

(iii-a) Let $f=1$. Then $d_{5}=1+2p$, thus $-4(1+4y)^{2}+25p+8=3(1+2p)$ or
$19p=4(1+4y)^{2}-5$. In this case, only holds true when $x=1$ and $y=1$. It
follows that $p=x^{2}+4y^{2}=5$ and $d_{5}=1+2p=11$.

(iii-b) Let $f=2$. Then $d_{5}=1+4p$ and $d_{5}\equiv 5\pmod{8}$. Thus
$\left(\frac{2}{d_{5}}\right)=-1$, that is 2 is not a quadratic residue of
modulo $d_{5}$. Further $2^{2p}\not\equiv 1(\textup{mod}\;d_{5})$. Then
$4^{p}\not\equiv 1(\textup{mod}\;d_{5})$. This contradicts with
$d_{5}|4^{p}-1$, thus $d_{5}\not=1+4p$.

(iii-c) Let $f=3$. Then $d_{5}=1+6p$, thus $-4(1+4y)^{2}+25p+4=3(1+6p)$ or
$7p=4(1+4y)^{2}-1$.

(iii-d) Let $f=4$. Then $d_{5}=1+8p$, thus $-4(1+4y)^{2}+25p+2=3(1+8p)$ or
$p=4(1+4y)^{2}+1$.

The proof is completed.

###### Theorem 3.3

Let $u_{5}=\phi[s_{1},s_{2}+1]$. Then the 4-adic complexity of quaternary
sequence $u_{5}$ satisfies
$\Phi_{4}(u_{5})\geq\lfloor\textup{log}_{4}(\frac{4^{p}-1}{(1+2p)(1+6p)(1+8p)}+1)\rfloor$.

Proof. To calculate the 4-adic complexity of $u_{5}=\phi[s_{1},s_{2}+1]$, we
need to consider $\textup{gcd}(U_{5}(4),4^{p}-1)$. Since

$\displaystyle U_{5}(4)$
$\displaystyle=\sum_{t=0}^{p-1}u_{5}(t)4^{t}(\textup{mod}\;4^{p}-1)$
$\displaystyle=\sum_{t=0}^{p-1}\phi[s_{1}(t),s_{2}(t)+1]4^{t}(\textup{mod}\;4^{p}-1)$
$\displaystyle=\sum_{\begin{subarray}{c}t=0\\\ t\in
D_{2}\cup\left\\{0\right\\}\end{subarray}}^{p-1}4^{t}+2\sum_{\begin{subarray}{c}t=0\\\
t\in D_{1}\end{subarray}}^{p-1}4^{t}+3\sum_{\begin{subarray}{c}t=0\\\ t\in
D_{0}\end{subarray}}^{p-1}4^{t}(\textup{mod}\;4^{p}-1)$
$\displaystyle=1+\eta_{2}(4)+2\eta_{1}(4)+3\eta_{0}(4)(\textup{mod}\;4^{p}-1),$

we have $U_{5}(4)\equiv 1+6\times\frac{p-1}{4}\equiv 1\pmod{3}$, hence 3 does
not divide $\textup{gcd}(U_{5}(4),4^{p}-1)$. Let $p\equiv 5\pmod{8}$ and
$r_{5}$ be a divisor of $\textup{gcd}(U_{5}(4),4^{p}-1)$ and
$\textup{gcd}(r_{5},3)=1$. For $p=5$, by the definition of sequence,
$U_{5}(4)=1+4^{4}+2\times 4^{2}+3\times 4=301$, thus
$\textup{gcd}(U_{5}(4),4^{5}-1)=\textup{gcd}(301,1023)=1$ and
$\Phi_{4}(u_{5})=5$. For $p>5$, according to Lemma 3.3, the possible prime
factors of $r_{5}$ are $1+2p$, $1+6p$ and $1+8p$, and satisfy the conditions
in Lemma 3.3.

If $(1+2p)^{2}|r_{5}$, by Lemma 3.1 (2), we get
$(1+2p)^{2}|-2(1+4y)H(4)+5p+1$, then by Lemma 2.3 we get $4(1+4y)^{2}p\equiv
25p^{2}+10p+1(\textup{mod}\;(1+2p)^{2})$ and by Lemma 3.3 we have
$3p=4(1+4y)^{2}+3$, that is $4(1+4y)^{2}=3p-3$. Thus $(3p-3)p\equiv
25p^{2}+10p+1(\textup{mod}\;(1+2p)^{2})$. Then we have
$-22p^{2}-13p-1=2(1+2p)^{2}m$, where $m\in\mathbb{Z}$. We obtain a
contradiction.

If $(1+6p)^{2}|r_{5}$, according to Lemma 3.1 (2) we have
$(1+6p)^{2}|-2(1+4y)H(4)+5p+1$, then by Lemma 2.3 we get $4(1+4y)^{2}p\equiv
25p^{2}+10p+1(\textup{mod}\;(1+6p)^{2})$ and by Lemma 3.3 we have
$7p=4(1+4y)^{2}-1$, that is $4(1+4y)^{2}=7p+1$. Thus $(7p+1)p\equiv
25p^{2}+10p+1(\textup{mod}\;(1+6p)^{2})$. Then we get
$-18p^{2}-9p-1=2(1+6p)^{2}m$, where $m\in\mathbb{Z}$. This will create a
contradiction.

If $(1+8p)^{2}|r_{5}$, by Lemma 3.1 (2), we get
$(1+8p)^{2}|-2(1+4y)H(4)+5p+1$, then by Lemma 2.3 we get $4(1+4y)^{2}p\equiv
25p^{2}+10p+1(\textup{mod}\;(1+8p)^{2})$ and by Lemma 3.3 we have
$p=4(1+4y)^{2}+1$, that is $4(1+4y)^{2}=p-1$. Thus $(p-1)p\equiv
25p^{2}+10p+1(\textup{mod}\;(1+8p)^{2})$. Then we get
$-24p^{2}-11p-1=2(1+8p)^{2}m$, where $m\in\mathbb{Z}$. This is impossible.

Therefore, the possible prime factors of $\textup{gcd}(U_{5}(4),4^{p}-1)$ are
$1+2p$, $1+6p$ and $1+8p$, and there are no repetition factors. And if $1+2p$,
$1+6p$ and $1+8p$ are not prime factors of $4^{p}-1$, the prime factors of
$\textup{gcd}(U_{5}(4),4^{p}-1)$ do not contain $1+2p$, $1+6p$ and $1+8p$,
respectively, which completes the proof.

###### Theorem 3.4

Let $u_{7}=\phi[s_{2},s_{4}+1]$, $u_{13}=\phi[s_{1}+1,s_{2}+1]$,
$u_{15}=\phi[s_{2}+1,s_{4}+1]$. Then for $i=7,13,15$, the 4-adic complexity of
quaternary sequences $u_{i}$ satisfies
$\Phi_{4}(u_{i})\geq\lfloor\textup{log}_{4}(\frac{4^{p}-1}{(1+2p)(1+6p)(1+8p)}+1)\rfloor$
, where either $p=5$ or the $p$ in $1+2p$ satisfies $3p=4(1+4y)^{2}+3$, the
$p$ in $1+6p$ satisfies $7p=4(1+4y)^{2}-1$ and the $p$ in $1+8p$ satisfies
$p=4(1+4y)^{2}+1$.

Proof. Since the proof is similar to Theorem 3.3, we omit it.

###### Lemma 3.4

Let
$U_{10}(4)=3+\eta_{1}(4)+2\eta_{2}(4)+3\eta_{3}(4)(\textup{mod}\;4^{p}-1)$. If
$d_{10}>3$ is a prime divisor of $\textup{gcd}(U_{10}(4),\frac{4^{p}-1}{3})$.
Then the possible values of $d_{10}$ are $\textup{(1) }d_{10}=11$;
$\textup{(2) }d_{10}=1+2p$ and $3p=4(3+4y)^{2}+83$.

Proof. Let $p\equiv 5\pmod{8}$ and $d_{10}>3$ be a prime divisor of
$\textup{gcd}(U_{10}(4),\frac{4^{p}-1}{3})$. According to Lemma 3.1 (1), we
have $d_{10}|-2(3+4y)H(4)+5p+9$, that is $2(3+4y)H(4)\equiv
5p+9(\textup{mod}\;d_{10})$. Then by Lemma 2.3 we have $4(3+4y)^{2}p\equiv
25p^{2}+90p+81(\textup{mod}\;d_{10})$. From $4^{p}\equiv
1(\textup{mod}\;d_{10})$ and $d_{10}\not=3$, we have the order of 4 modulo
$d_{10}$ is $p$. Since $d_{10}$ is odd prime, by Euler’s Theorem we have
$4^{d_{10}-1}\equiv 1(\textup{mod}\;d_{10})$. Thus $p|d_{10}-1$. Then
$d_{10}=1+2fp$, where $f\in\mathbb{N_{+}}$, that is
$2fp\equiv-1(\textup{mod}\;d_{10})$. Hence we have
$-4(3+4y)^{2}+25p+90-162f\equiv 0(\textup{mod}\;d_{10})$ or
$-4(3+4y)^{2}+25p+90-162f=(1+2h)(1+2fp)$. From the last congruence we get
$3-2f\equiv 1+2h+2f+4fh\pmod{8}$. Thus $h\equiv 1\pmod{2}$ and $1+2h=3+8t$
where $t\in\mathbb{Z}$. So, we get

$-4(3+4y)^{2}+25p+90-162f=(3+8t)(1+2fp)$ (3)

The discussion can be divided into three cases as follows.

(i) Case 1: If $t<0$, since $25p+90-4(3+4y)^{2}\geq
36y^{2}-96y+79=(6y-8)^{2}+15>0$, then by (3) we have $-162f<(3+8t)(1+2fp)$,
that is $162f>(-3-8t)(1+2fp)\geq 5+10fp$. Hence $p=5$ or $p=13$. Combining (3)
we have, when $p=5$, $d_{10}=11$; when $p=13$, we obtain a contradiction.

(ii) Case 2 If $t>0$, since $90-162f-4(3+4y)^{2}<0$, then by (3) we get
$25p>(3+8t)(1+2fp)$. Hence $f=1$, $t=1$, that is $d_{10}=1+2p$ is a prime
divisor of $\frac{4^{p}-1}{3}$ and $3p=4(3+4y)^{2}+83$.

(iii) Case 3 If $t=0$, we have $-4(3+4y)^{2}+25p+90-162f=3(1+2fp)$. Since
$90-4(3+4y)^{2}-162f-3<0$, it follows that $25p>6fp$. Hence, the possible
values of $f$ are $1,2,3,4$ and $-y^{2}+p\equiv 0\pmod{3}$, thus $p\equiv
y^{2}\equiv 1\pmod{3}$. In this case $f\not=1$ and $f\not=4$; if not,
$1+2fp\equiv 0\pmod{3}$, which is contradictory.

(iii-a) Let $f=2$. Then $d_{10}=1+4p$ and $d_{10}\equiv 5\pmod{8}$. Thus
$(\frac{2}{d_{10}})=(-1)^{\frac{d_{10}^{2}-1}{8}}=-1$, that is 2 is not a
quadratic residue of modulo $d_{10}$. Further $2^{2p}\not\equiv
1(\textup{mod}\;d_{10})$. Then $4^{p}\not\equiv 1(\textup{mod}\;d_{10})$. This
contradicts with $d_{10}|4^{p}-1$, thus $d_{10}\not=1+4p$.

(iii-b) Let $f=3$. Then $d_{10}=1+6p$, thus $-4(3+4y)^{2}+25p+90-486=3(1+6p)$,
that is $-4(3+4y)^{2}=7(57-p)$. Hence $3+4y=7k$, where $k\in\mathbb{Z}$ and
$-4\times 7k^{2}+p-57=0$, then $p=4\times 7k^{2}+57\equiv 1(\textup{mod}\;7)$,
also by $p\equiv 5\pmod{8}$ and Chinese Remainder Theorem, we arrive at a
contradiction.

The proof is completed.

###### Theorem 3.5

Let $u_{10}=\phi[s_{1}+1,s_{3}]$. Then the 4-adic complexity of quaternary
sequence $u_{10}$ satisfies
$\Phi_{4}(u_{10})\geq\lfloor\textup{log}_{4}(\frac{4^{p}-1}{3(1+2p)}+1)\rfloor$.

Proof. To calculate the 4-adic complexity of $u_{10}=\phi[s_{1}+1,s_{3}]$, we
need to consider $\textup{gcd}(U_{10}(4),4^{p}-1)$. Since

$\displaystyle U_{10}(4)$
$\displaystyle=\sum_{t=0}^{p-1}u_{10}(t)4^{t}(\textup{mod}\;4^{p}-1)$
$\displaystyle=\sum_{t=0}^{p-1}\phi[s_{1}(t)+1,s_{3}(t)]4^{t}(\textup{mod}\;4^{p}-1)$
$\displaystyle=\sum_{\begin{subarray}{c}t=0\\\ t\in
D_{1}\end{subarray}}^{p-1}4^{t}+2\sum_{\begin{subarray}{c}t=0\\\ t\in
D_{2}\end{subarray}}^{p-1}4^{t}+3\sum_{\begin{subarray}{c}t=0\\\ t\in
D_{3}\cup\left\\{0\right\\}\end{subarray}}^{p-1}4^{t}(\textup{mod}\;4^{p}-1)$
$\displaystyle=3+\eta_{1}(4)+2\eta_{2}(4)+3\eta_{3}(4)(\textup{mod}\;4^{p}-1),$

then we have $U_{10}(4)\equiv 3+6\times\frac{p-1}{4}\equiv 0\pmod{3}$ and
$4^{p}\equiv 1\pmod{3}$, hence $3|\textup{gcd}(U_{10}(4),4^{p}-1)$. If
$9|4^{p}-1$, then from $4^{3}\equiv 1\pmod{9}$ and $4^{p}\equiv 1\pmod{9}$, we
obtain $p=3$, which contradicts with $p\equiv 5\pmod{8}$. Thus 9 does not
divide $4^{p}-1$, that is 9 does not divide $\textup{gcd}(U_{10}(4),4^{p}-1)$.

Let $p\equiv 5\pmod{8}$ and $r_{10}$ be a divisor of
$\textup{gcd}(U_{10}(4),4^{p}-1)$ and $\textup{gcd}(r_{10},3)=1$. For $p=5$,
by the definition of sequence, $U_{10}(4)=3+4^{2}+2\times 4^{4}+3\times
4^{3}=723$, thus $\textup{gcd}(U_{10}(4),4^{5}-1)=\textup{gcd}(723,1023)=3$
and $\Phi_{4}(u_{10})=4$. For $p>5$, according to Lemma 3.4 we get $r_{10}$ is
a power of $2p+1$ and $2p+1$ is a prime that satisfying $3p=4(3+4y)^{2}+83$.
If $(2p+1)^{2}|r_{10}$, by Lemma 3.1 (1), we get
$(2p+1)^{2}|-2(3+4y)H(4)+5p+9$, thus $4(3+4y)^{2}p\equiv
25p^{2}+90p+81(\textup{mod}\;(2p+1)^{2})$ and by Lemma 3.4 we have
$3p=4(3+4y)^{2}+83$, that is $4(3+4y)^{2}=3p-83$. Thus
$(3p-83)p-25p^{2}-90p-81\equiv 0(\textup{mod}\;(2p+1)^{2})$. Then we have
$-22p^{2}-173p-81=2(2p+1)^{2}m$, where $m\in\mathbb{Z}$. This is impossible.

Therefore, the possible prime factor of $\textup{gcd}(U_{10}(4),4^{p}-1)$ is
$2p+1$, and there is no repetition factor. And
$\textup{gcd}(U_{10}(4),4^{p}-1)=3$ when $2p+1$ is not a prime divisor of
$4^{p}-1$, which completes the proof.

###### Theorem 3.6

Let $u_{2}=\phi[s_{1},s_{3}]$, $u_{4}=\phi[s_{3},s_{4}]$,
$u_{12}=\phi[s_{3}+1,s_{4}]$. Then the 4-adic complexity of these quaternary
sequences satisfies
$\Phi_{4}(u_{i})\geq\lfloor\textup{log}_{4}(\frac{4^{p}-1}{3(1+2p)}+1)\rfloor$,
$i=2,4,12$, where $1+2p=11$ or the $p$ in $1+2p$ satisfies
$3p=4(3+4y)^{2}+83$. Proof. Since the proof is similar to Theorem 3.5, we omit
it.

###### Lemma 3.5

Let
$U_{16}(4)=2+\eta_{1}(4)+2\eta_{0}(4)+3\eta_{3}(4)(\textup{mod}\;4^{p}-1)$. If
$d_{16}>3$ is a prime divisor of $gcd(U_{16}(4),\frac{4^{p}-1}{3})$. Then the
possible values of $d_{16}$ are (1) $d_{16}=11$; (2) $d_{16}=1+2p$ and
$3p=4(1-4y)^{2}+3$; (3) $d_{16}=1+6p$ and $7p=4(1-4y)^{2}-1$; (4)
$d_{16}=1+8p$ and $p=4(1-4y)^{2}+1$.

Proof. Let $p\equiv 5\pmod{8}$ and $d_{16}>3$ be a prime divisor of
$\textup{gcd}(U_{16}(4),\frac{4^{p}-1}{3})$. According to Lemma 3.1 (8), we
have $d_{16}|-2(1-4y)H(4)+5p+1$, thus $5p+1\equiv
2(1-4y)H(4)(\textup{mod}\;d_{16})$. Then by Lemma 2.3 we have
$4(1-4y)^{2}p\equiv 25p^{2}+10p+1(\textup{mod}\;d_{16})$. From $4^{p}\equiv
1(\textup{mod}\;d_{16})$ and $d_{16}\not=3$, we have the order of 4 modulo
$d_{16}$ is $p$. Since $d_{16}$ is odd prime, by Euler’s Theorem we have
$4^{d_{16}-1}\equiv 1(\textup{mod}\;d_{16})$. Thus $p|d_{16}-1$. Then
$d_{16}=1+2fp$, where $f\in\mathbb{N_{+}}$, that is
$2fp\equiv-1(\textup{mod}\;d_{16})$. Hence we have
$-4(1-4y)^{2}+25p+10-2f\equiv 0(\textup{mod}\;d_{16})$ or
$-4(1-4y)^{2}+25p+10-2f=(1+2h)(1+2fp)$. From the last congruence we get
$3-2f\equiv 1+2f+2h+4fh(\textup{mod}\;8)$. Thus $h\equiv 1(\textup{mod}\;2)$
and $1+2h=3+8t$ where $t\in\mathbb{Z}$. So, we get

$-4(1-4y)^{2}+25p+10-2f=(3+8t)(1+2fp)$ (4)

The discussion can be divided into three cases as follows.

(i) Case 1: If $t<0$, since $25p+10-4(1-4y)^{2}\geq
36y^{2}+32y+31=(6y+\frac{8}{3})^{2}+\frac{215}{9}>0$, then by (4) we have
$-2f<(3+8t)(1+2fp)$, that is $2f>(-3-8t)(1+2fp)\geq 5+10fp$. It is impossible.

(ii) Case 2: If $t>0$, since $10-2f-4(1-4y)^{2}<0$, then by (4) we get that
$25p>(3+8t)(1+2fp)$. Hence $f=1,t=1$, that is $d_{16}=1+2p$ is a prime divisor
of $\frac{4^{p}-1}{3}$ and $3p=4(1-4y)^{2}+3$.

(iii) Case 3: If $t=0$, here $-4(1-4y)^{2}+25p+10-2f=3(1+2fp)$. Since
$10-2f-4(1-4y)^{2}-3<0$, it follows that $25p>6fp$. Hence, the possible values
of $f$ are $1,2,3,4$.

(iii-a) Let $f=1$. Then $d_{16}=1+2p$, thus $-4(1-4y)^{2}+25p+8=3(1+2p)$ or
$19p=4(1-4y)^{2}-5$. In this case, only holds true when $x=1$ and $y=-1$. It
follows that $p=x^{2}+4y^{2}=5$ and $d_{16}=1+2p=11$.

(iii-b) Let $f=2$. Then $d_{16}=1+4p$ and $d_{16}\equiv 5\pmod{8}$. Thus
$\left(\frac{2}{d_{16}}\right)=-1$, that is 2 is not a quadratic residue of
modulo $d_{16}$. Further $2^{2p}\not\equiv 1(\textup{mod}\;d_{16})$. Then
$4^{p}\not\equiv 1(\textup{mod}\;d_{16})$. This contradicts with
$d_{16}|4^{p}-1$, thus $d_{16}\not=1+4p$.

(iii-c) Let $f=3$. Then $d_{16}=1+6p$, thus $-4(1-4y)^{2}+25p+4=3(1+6p)$ or
$7p=4(1-4y)^{2}-1$.

(iii-d) Let $f=4$. Then $d_{16}=1+8p$, thus $-4(1-4y)^{2}+25p+2=3(1+8p)$ or
$p=4(1-4y)^{2}+1$.

The proof is completed.

###### Theorem 3.7

Let $u_{16}=\phi[s_{3}+1,s_{4}+1]$. Then the 4-adic complexity of quaternary
sequence $u_{16}$ satisfies
$\Phi_{4}(u_{16})\geq\lfloor\textup{log}_{4}(\frac{4^{p}-1}{(1+2p)(1+6p)(1+8p)}+1)\rfloor$.

Proof. To calculate the 4-adic complexity of $u_{16}=\phi[s_{3}+1,s_{4}+1]$,
we need to consider $\textup{gcd}(U_{16}(4),4^{p}-1)$. Since

$\displaystyle U_{16}(4)$
$\displaystyle=\sum_{t=0}^{p-1}u_{16}(t)4^{t}(\textup{mod}\;4^{p}-1)$
$\displaystyle=\sum_{t=0}^{p-1}\phi[s_{3}(t)+1,s_{4}(t)+1]4^{t}(\textup{mod}\;4^{p}-1)$
$\displaystyle=\sum_{\begin{subarray}{c}t=0\\\ t\in
D_{1}\end{subarray}}^{p-1}4^{t}+2\sum_{\begin{subarray}{c}t=0\\\ t\in
D_{0}\cup\left\\{0\right\\}\end{subarray}}^{p-1}4^{t}+3\sum_{\begin{subarray}{c}t=0\\\
t\in D_{3}\end{subarray}}^{p-1}4^{t}(\textup{mod}\;4^{p}-1)$
$\displaystyle=2+\eta_{1}(4)+2\eta_{0}(4)+3\eta_{3}(4)(\textup{mod}\;4^{p}-1),$

then $U_{16}(4)\equiv 2+6\times\frac{p-1}{4}\equiv 2\pmod{3}$, hence 3 does
not divide $\textup{gcd}(U_{16}(4),4^{p}-1)$. Let $p\equiv 5\pmod{8}$ and
$r_{16}$ be a divisor of $\textup{gcd}(U_{16}(4),4^{p}-1)$ and
$\textup{gcd}(r_{16},3)=1$. For $p=5$, by the definition of sequence,
$U_{16}(4)=2+4^{2}+2\times 4+3\times 4^{3}=218$, thus
$\textup{gcd}(U_{16}(4),4^{5}-1)=\textup{gcd}(218,1023)=1$ and
$\Phi_{4}(u_{16})=5$. For $p>5$, according to Lemma 3.5, the possible prime
factors of $r_{16}$ are $1+2p$, $1+6p$ and $1+8p$, and satisfy the conditions
in Lemma 3.5.

If $(1+2p)^{2}|r_{16}$, by Lemma 3.1 (8), we get
$(1+2p)^{2}|-2(1-4y)H(4)+5p+1$, then by Lemma 2.3 we get $4(1-4y)^{2}p\equiv
25p^{2}+10p+1(\textup{mod}\;(1+2p)^{2})$ and by Lemma 3.5 we have
$3p=4(1-4y)^{2}+3$, that is $4(1-4y)^{2}=3p-3$. Thus $(3p-3)p\equiv
25p^{2}+10p+1(\textup{mod}\;(1+2p)^{2})$. Then we have
$-22p^{2}-13p-1=2(1+2p)^{2}m$, where $m\in\mathbb{Z}$. We obtain a
contradiction.

If $(1+6p)^{2}|r_{16}$, according to Lemma 3.1 (8) we have
$(1+6p)^{2}|-2(1-4y)H(4)+5p+1$, then by Lemma 2.3 we get $4(1-4y)^{2}p\equiv
25p^{2}+10p+1(\textup{mod}\;(1+6p)^{2})$ and by Lemma 3.5 we have
$7p=4(1-4y)^{2}-1$, that is $4(1-4y)^{2}=7p+1$. Thus $(7p+1)p\equiv
25p^{2}+10p+1(\textup{mod}\;(1+6p)^{2})$. Then we get
$-18p^{2}-9p-1=2(1+6p)^{2}m$, where $m\in\mathbb{Z}$. This will create a
contradiction.

If $(1+8p)^{2}|r_{16}$, by Lemma 3.1 (8), we get
$(1+8p)^{2}|-2(1-4y)H(4)+5p+1$, then by Lemma 2.3 we get $4(1-4y)^{2}p\equiv
25p^{2}+10p+1(\textup{mod}\;(1+8p)^{2})$ and by Lemma 3.5 we have
$p=4(1-4y)^{2}+1$, that is $4(1-4y)^{2}=p-1$. Thus $(p-1)p\equiv
25p^{2}+10p+1(\textup{mod}\;(1+8p)^{2})$. Then we get
$-24p^{2}-11p-1=2(1+8p)^{2}m$, where $m\in\mathbb{Z}$. This is impossible.

Therefore, the possible prime factors of $\textup{gcd}(U_{16}(4),4^{p}-1)$ are
$1+2p$, $1+6p$ and $1+8p$, and there are no repetition factors. And if $1+2p$,
$1+6p$ and $1+8p$ are not prime factors of $4^{p}-1$, the prime factors of
$\textup{gcd}(U_{16}(4),4^{p}-1)$ do not contain $1+2p$, $1+6p$ and $1+8p$,
respectively, which completes the proof.

###### Theorem 3.8

Let $u_{6}=\phi[s_{1},s_{3}+1]$, $u_{8}=\phi[s_{3},s_{4}+1]$,
$u_{14}=\phi[s_{1}+1,s_{3}+1]$. Then the 4-adic complexity of these quaternary
sequences satisfies
$\Phi_{4}(u_{i})\geq\lfloor\textup{log}_{4}(\frac{4^{p}-1}{(1+2p)(1+6p)(1+8p)}+1)\rfloor$,
$i=6,8,14$, where $1+2p=11$ or the $p$ in $1+2p$ satisfies $3p=4(1-4y)^{2}+3$,
the $p$ in $1+6p$ satisfies $7p=4(1-4y)^{2}-1$, the $p$ in $1+8p$ satisfies
$p=4(1-4y)^{2}+1$.

Proof. Since the proof is similar to Theorem 3.7, we omit it.

##  4 Conclusions

It is interesting to study the 4-adic complexity of sequences with good
correlation generated by FCSRs. In this paper, we estimate the 4-adic
complexity of several classes of quaternary sequences in reference [14], which
have low autocorrelation and high linear complexity. It turns out these
sequences have high 4-adic complexity, which is sufficient safe to resist the
attack of the RAA.

## References

  * [1] F. Adachi, D. Garg, S. Takaoka and K. Takeda, Broadband CDMA techniques,  _IEEE Wireless Communications_ , 12 (2005), 8–18.
  * [2] S. W. Golomb and G. Gong,  Signal Design for Good Correlation: For Wireless Communication, Cryptography, and Radar,  Cambridge University Press, Cambridge, 2005.
  * [3] S. W. Golomb,  Shift Register Sequences,  CA:Aegean Park Press, 1967.
  * [4] M. Goresky and A. Klapper,  Algebraic Shift Register Sequences,  Cambridge University Press, Cambridgeshire, 2012.
  * [5] A. Klapper and M. Goresky,  Feedback shift registers, 2-adic span, and combiners with memory,  _Journal of Cryptology_ , 10 (1997), 111–147.
  * [6] A. Klapper and J. Xu,  Algebraic feedback shift registers,  _Theoretical Computer Science_ , 226 (1999), 61–92.
  * [7] M. Yang, S. Qiang, K. Feng and D. Lin,  On the 4-adic complexity of quaternary sequences of period $2p$ with ideal autocorrelation,  _2021 IEEE International Symposium on Information Theory (ISIT)_ , (2021), 1812–1816.
  * [8] M. Yang, S. Qiang, X. Jing, K. Feng and D. Lin,  The 4-adic complexity of quaternary sequences of even period with ideal autocorrelation,  _2022 IEEE International Symposium on Information Theory (ISIT)_ , (2022), 528–531.
  * [9] X. Jing, Z. Xu, M. Yang and K. Feng,  The 4-adic complexity of interleaved quaternary sequences of even length with optimal autocorrelation,  _arXiv preprint arXiv:2209.10279_ (2022).
  * [10] V. Edemskiy,  Symmetric 4-adic complexity of quaternary sequences with low autocorrelation and period $pq$,  _Advances in Mathematics of Communications_ , (2023), 0–0.
  * [11] V, Edemskiy and S. Koltsova,  Symmetric 4-adic complexity of quaternary sequences of length $pq$ with low autocorrelation,  _2023 IEEE Information Theory Workshop (ITW)_ , (2023), 76–80.
  * [12] V. Edemskiy and C. Wu,  4-adic complexity of quaternary cyclotomic sequences and Ding-Helleseth sequences with period $pq$,  _2022 IEEE International Symposium on Information Theory (ISIT)_ , (2022), 372–377.
  * [13] V. Edemskiy and Z. Chen,  On the 4-adic complexity of the two-prime quaternary generator,  _Journal of Applied Mathematics and Computing_ , 68 (2022), 3565–3585.
  * [14] T. Jiang and F. W. Fu,  Some new classes of quaternary sequences with low autocorrelation property via two binary cyclotomic sequences,  _Journal of Applied Mathematics and Computing_ , 69 (2023), 689–706.
  * [15] Z. Yang and P. H. Ke,  Quaternary sequences with odd period and low autocorrelation,  _Electronics letters_ , 46 (2010), 1–2.
  * [16] C. Zhang, X. Jing and Z. Xu,  The linear complexity and 4-adic complexity of quaternary sequences with period $pq$,  _Journal of Applied Mathematics and Computing_ , 69 (2023), 2003–2017.
  * [17] T. Cusick, C. Ding and A. Renvall,  Stream ciphers and number theory,  _Gulf Professional Publishing_ , (2004).
  * [18] T. Storer,  Cyclotomy and difference sets,  _Lectures in Advanced Mathematics_ , (1967).
  * [19] F. Sun, Q. Yue and X. Li,  On the 2-adic complexity of cyclotomic binary sequences of order four,  _Applicable Algebra in Engineering, Communication and Computing_ , (2023), 1–19.