On self-dual and LCD quasi-twisted codes of index two over a
Transcript Of On self-dual and LCD quasi-twisted codes of index two over a
On self-dual and LCD quasi-twisted codes of index two over a special chain ring
Minjia Shi, Liqin Qian, Patrick Sole
To cite this version:
Minjia Shi, Liqin Qian, Patrick Sole. On self-dual and LCD quasi-twisted codes of index two over a special chain ring. Cryptography and Communications - Discrete Structures, Boolean Functions and Sequences , Springer, 2019, 11, pp.717 - 734. 10.1007/s12095-018-0322-5. hal-02411619
HAL Id: hal-02411619 https://hal.archives-ouvertes.fr/hal-02411619
Submitted on 17 Dec 2019
HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.
L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.
Cryptography and Communications (2019) 11:717–734 https://doi.org/10.1007/s12095-018-0322-5
On self-dual and LCD quasi-twisted codes of index two over a special chain ring
Liqin Qian2 · Minjia Shi1,2 · Patrick Sole´ 3
Received: 26 April 2018 / Accepted: 25 July 2018 / Published online: 13 August 2018 © Springer Science+Business Media, LLC, part of Springer Nature 2018
Abstract Let q be a prime power, and let Fq denote the finite field of order q. Consider the chain ring Rk = Fq [u]/ uk with k ≥ 1 an integer. We study self-dual and LCD quasi-twisted codes of index two and twisting constant λ over Rk for the metric induced by the standard Gray map. Some special factorizations of xm − λ over Rk are studied. By random coding, we obtain four classes of asymptotically good self-dual λ-circulant codes and four classes of asymptotically good LCD λ-circulant codes over Rk.
Keywords Double circulant codes · Gray map · Self-dual codes · LCD codes · Quasi-twisted codes
Mathematics Subject Classification (2010) 94 B15 · 94 B25 · 05 E30
This research is supported by National Natural Science Foundation of China (61672036), Excellent Youth Foundation of Natural Science Foundation of Anhui Province (1808085J20), Technology Foundation for Selected Overseas Chinese Scholar, Ministry of Personnel of China (05015133) and Key projects of support program for outstanding young talents in Colleges and Universities (gxyqZD2016008).
Minjia Shi [email protected]
Liqin Qian qianliqin [email protected] Patrick Sole´ [email protected]
1 Key Laboratory of Intelligent Computing Signal Processing, Ministry of Education, Anhui University, No.3 Feixi Road, Hefei, Anhui, 230039, China
2 School of Mathematical Sciences, Anhui University, Hefei, Anhui, 230601, China 3 CNRS/LAGA, University of Paris 8, 93 526 Saint-Denis, France
718
Cryptography and Communications (2019) 11:717–734
1 Introduction
Self-dual codes are important for a number of practical and theoretical reasons, as witnessed by [1, 3, 12]. Another important class of codes defined by their duality properties is that of Linear codes with Complementary Duals (LCD), which were introduced by Massey in 1992 for information theoretic reasons (see [18]). They have found applications recently in Boolean masking [6, 7]. Massey [18] shows that LCD codes are asymptotically good. LCD codes are universal: for q > 3 there is an algorithm that turns any linear code into an equivalent LCD code [5]. Still, it is of interest to find direct methods of construction of LCD codes as in [4]. One such method is to use quasi-cyclic and quasi-twisted codes. In that direction, self-dual double circulant (resp. double negacirculant) codes over finite fields have been studied recently in [1, 3], from the viewpoint of enumeration and asymptotic performance. Some classes of quasi-twisted codes have been studied over finite chain rings in [19]. In [2], A. Alahmadi et al. have studied the linear complementary-dual multinegacirculant codes. Motivated by the techniques in [1–3, 8, 19, 20], we use the Chinese Remainder Theorem (CRT) approach to quasi-twisted codes as introduced in [11, 13, 14]. In particular, we study two classes of self-dual (resp. LCD) negacirculant codes of index 2 over Rk. Combining with [19], we study two families of factorizations of xm − λ over Rk with m an odd prime, gcd(m, q) = 1. When these special factorizations are thus enforced, we derive exact enumeration formulae, and obtain asymptotic lower bounds on the minimum Hamming distance of the Gray image of these codes.
The material is arranged as follows. In Section 2, we give some background materials on the ring Rk and study the case when the element −1 is a square in Rk. In Section 3, we derive the enumeration formulae of self-dual (resp. LCD) double circulant and double negacirculant codes of co-index m and we study the special factorizations of xm − λ with m an odd prime, and gcd(m, q) = 1. Then, we also obtain the enumeration formulae of self-dual (resp. LCD) double λ-circulant codes. In Section 4, we derive a modified Varshamov-Gilbert bound on the relative distance of the codes considered, building on exact enumeration results. Finally, Section 5 contains conclusions and open problems.
2 Preliminaries
2.1 The ring Rk = Fq [u]/ uk
Let q be a prime power, and let Fq denote the finite field of order q. Consider the local ring Rk = Fq [u]/ uk where uk = 0 with unique maximal ideal u . In double λ-circulant codes case, we will consider the chain ring Rk = Fq [u]/ uk when it contains a square root
of −1.
Theorem 2.1 If a0 + ua1 + · · · + uk−1ak−1 ∈ Rk = Fq [u]/ uk is a square root of −1 if and only if
(1) q is a power of 2, a02 = −1, a1 = a2 = · · · = a k−2 = 0, where a k , a k+2 , · · · , ak−1 ∈
2
2
2
Fq when k is even; a02 = −1, a1 = a2 = · · · = a k−1 = 0, a k+1 , a k+2 , · · · , ak−1 ∈ Fq ,
2
2
2
when k is odd; or
(2) q = pκ where p ≡ 1(mod 4) or q = p2κ where p ≡ 3(mod 4), a02 = −1, a1 = a2 = · · · = ak−1 = 0.
Cryptography and Communications (2019) 11:717–734
719
Proof Note that the condition is obviously sufficient. To prove its necessity, when q is a
power of 2, we have (a0 + a1u + · · · + ak−1uk−1)2 = a02 + a12u2 + · · · + ak2−1u2(k−1) =
−1,when k is even, a02 = −1, a1 = a2 = · · · = a k−2 = 0, a k , a k+2 , · · · , ak−1 ∈ Fq ; when
2
2
2
k is odd, a02 = −1, a1 = a2 = · · · = a k−1 = 0, a k+1 , a k+2 , · · · , ak−1 ∈ Fq . When q is a
2
2
2
power of an odd prime, we have (a0 + a1u + · · · + ak−1uk−1)2 = a02 + 2a0a1u + (2a0a2 +
a12)u2 + · · · + (a0ak−1 + a1ak−2 + · · · + ak−1a0)uk−1 = −1,where ai ∈ Fq , 0 ≤ i ≤ k − 1.
Then we get a02 = −1, a1 = a2 = · · · = ak−1 = 0. Thus a0 is a square root of −1 over Fq
if and only if q ≡ 1(mod 4).
2.2 Codes
A linear code C over Rk of length n is an Rk-submodule of Rkn. If x = (x1, x2, · · · , xn) and y = (y1, y2, · · · , yn) are two elements of Rkn, their standard (Euclidean) inner product is defined by
n
x, y = xi yi ,
i=1
and their Hermitian scalar inner product is defined by
n
x, y H = xi y¯i ,
i=1
where the operation is performed in Rk. For all z = z0 + uz1 + · · · + uk−1zk−1 ∈ Fq2Q + uFq2Q + · · · + uk−1Fq2Q , the conjugation of z over Fq2Q + uFq2Q + · · · + uk−1Fq2Q is
z = z0qQ + uz1qQ + · · · + uk−1zkq−Q1, where Q is a positive integer. The Euclidean (resp. Hermitian) dual code of C is denoted by C⊥ (resp. C⊥H ) and defined as C⊥ = {y ∈ Rkn | x, y = 0, ∀x ∈ C} (resp. C⊥H = {y ∈ Rkn | x, y H = 0, ∀x ∈ C}).
A linear code C of length n over Rk is called a self-dual code (resp. Hermitian selfdual code) if C = C⊥ (resp. C = C⊥H ). A linear code C of length n over Rk is called a linear code with complementary dual (LCD) if C C⊥ = {0} or C C⊥H = {0}.
A matrix A over Rk is said to be λ-circulant if its rows are obtained by successive λ-
shifts from the first row. In this paper, we consider double λ-circulant codes over Rk, that
is [2m, m] codes with generator matrices G = (I, A) with A an m × m λ-circulant matrix,
we can view such a code as an Rk-module in Rk2, generated by (1, h) with the first row of
A being the x-expansion of h in the ring
Rk [x] x m −λ
.
If C(m) is a family of codes with parameters [m, km, dm] over Fq , the rate ρ and relative
distance δ are defined as ρ = limm→s∞up kmm and δ = lmim→i∞nf dmm , respectively. A family of codes is good if ρδ > 0.
In number theory, Artin’s conjecture on primitive roots states that a given integer q which is neither a perfect square nor −1 is a primitive root modulo infinitely many primes [16]. This was proved conditionally under the Generalized Riemann Hypothesis (GRH) by Hoo-
ley [9]. Hence, we can get infinite families of double λ-circulant codes C(m) over Rk where the analysis is made for xm − 1 with a special factorization.
Recall the q-ary entropy function defined for 0 ≤ t˜ ≤ q−q 1 by
Hq (t˜) = 0, t˜logq (q − 1) − t˜logq (t˜) − (1 − t˜)logq (1 − t˜),
if t˜ = 0, if 0 < t˜ ≤ q−q 1 .
720
Cryptography and Communications (2019) 11:717–734
This quantity is instrumental in the estimation of the volume of high-dimensional Hamming
balls when the base field is Fq . The result we are using is that the volume of the Hamming ball of radius t˜m is asymptotically equivalent, up to subexponential terms, to qmHq(t˜), when 0 < t˜ < 1, and m goes to infinity [10, Lemma 2.10.3].
2.3 Gray map
Any integer z can be written uniquely in base p as z = p0(z) + pp1(z) + p2p2(z) + · · · , where 0 ≤ pi (z) ≤ p − 1, i = 0, 1, 2, . . .. The Gray map : R → Fppk−1 is defined as follows:
(a) = (b0, b1, b2, . . . , bpk−1−1),
where a = a0 + a1u + · · · + ak−1uk−1. Then for all 0 ≤ i ≤ pk−2 − 1, 0 ≤ τ ≤ p − 1,we
have
⎧
⎨ ak−1 + k−2 pl−1(i)al + τ a0,
bip+τ = ⎩
l=1
a1 + τ a0,
if k ≥ 3, if k = 2.
Note that, more generally, Gray maps have been defined at the level of finite chain rings
in [15, 23], linking codes over rings to codes over finite fields. For instance, when p =
k = 2, it is easy to check that the Gray map adopted in the trace codes of [21] is the
same as the Gray map defined here. As an additional example, when p = k = 3, write (a0 + a1u + a2u2) = (b0, b1, b2, · · · , b8). According to the definition above, we have
k−2
0 ≤ i ≤ 2, 0 ≤ τ ≤ 2 and pl−1(i)al = p0(i)a1 = ia1. Then we get
l=1
b0 = a2, b1 = a2 + a0, b2 = a2 + 2a0, b3 = a2 + a1, b4 = a2 + a1 + a0,
b5 = a2 + a1 + 2a0, b6 = a2 + 2a1, b7 = a2 + 2a1 + a0, b8 = a2 + 2a1 + 2a0.
It is easy to extend the Gray map from Rkm to Fppk−1m, and we also know from [22] that is injective and linear.
3 Algebraic structure of λ-circulant codes of index two
In this section, we study the exact enumeration of the double self-dual and LCD λ-circulant codes over Rk.
3.1 Double circulant codes (λ = 1)
In this subsection, we assume m is an odd integer and gcd(m, q) = 1. We can cast the factorization of xm − 1 into distinct basic irreducible polynomials over Rk = Fq [u]/ uk in
the form
s
t
xm − 1 = δ(x − 1) gi (x) hj (x)h∗j (x),
(1)
i=2
j =1
Cryptography and Communications (2019) 11:717–734
721
where δ is a unit in Rk, the polynomial gi(x) is self-reciprocal of degree 2ei for 2 ≤ i ≤ s, and h∗j (x) is the reciprocal polynomial of hj (x) with degree dj for 1 ≤ j ≤ t. By the
Chinese Remainder Theorem (CRT), we have
Rk [x ] xm − 1
⎛
⎞
Rk[x] ⊕
s
t
R [x]/ g (x) ⊕⎝
R [x]/ h (x) ⊕ R [x]/ h∗(x) ⎠
x−1
k
i
k
j
k
j
i=2
j =1
⎛
⎞
Fq [u, x] ⊕
s
Fq [u, x]
t
⊕⎝
Fq [u, x] ⊕ Fq [u, x] ⎠
uk, x − 1 i=2 uk, gi (x)
j=1 uk, hj (x)
uk
,
h
∗ j
(
x
)
⎛
s
t
Rk ⊕
(Fq2ei + uFq2ei + · · · + uk−1Fq2ei ) ⊕⎝
Fqdj + uFqdj + · · ·
i=2
j =1
⎞
+uk−1Fqdj ⊕ (Fqdj + uFqdj + · · · + uk−1Fqdj ) ⎠
:=Rk ⊕
s
Rk(2ei )
i=2
⎛
⎞
t
⊕⎝ (Rk(dj ) ⊕ Rk(dj ))⎠ .
j =1
Note that all of these rings are extensions of Rk. This decomposition naturally extends to
(
Rk [x] x m −1
)2
as
Rk[x] 2 xm − 1
Rk ⊕
s
Rk2(2ei )
i=2
⎛
t
⊕⎝
j =1
⎞ Rk2(dj ) ⊕ Rk2(dj ) ⎠ .
In particular, each linear code C of length 2 over
Rk [x] x m −1
can be decomposed as the “CRT
sum”
⎛
⎞
s
t
C C1 ⊕
Ci ⊕ ⎝ (Cj ⊕ Cj )⎠ ,
i=2
j =1
where C1 is a linear code over Rk of length 2, Ci is a linear code over Rk(2ei) of length 2 for each 2 ≤ i ≤ s, and Cj and Cj are linear codes over Rk(dj ) of length 2 for each 1 ≤ j ≤ t, which are called the constituents of C.
Lemma 3.1 Keep the same notations as above, then
(1) C1 is LCD if and only if 1 + r2 ∈ Rk× with C1 = (1, r) ; (2) Ci is LCD if and only if 1 + ηη¯ ∈ Rk×(2ei) with Ci = (1, η) ; (3) Cj ⊕ Cj are LCD if and only if 1 + η η ∈ Rk×(dj ) with Cj = (1, η ) and Cj =
(1, η ) .
Proof (1) “ =⇒ ” If C1 is LCD, suppose 1 + r2 ∈ Rk×, then 1 + r2 ∈ u . We have uk−1(1 + r2) = 0,i.e., uk−1(1, r), (1, r) = 0,then uk−1(1, r) ∈ C1⊥,which implies uk−1(1, r) ∈ C1 ∩ C1⊥, a contradiction.
722
Cryptography and Communications (2019) 11:717–734
“ ⇐= ” If 1 + r2 ∈ Rk×, assume C1 is not LCD, then C1 ∩ C1⊥ = {0}. Hence, there exists r ∈ Rk× such that r (1, r) ∈ C1 ∩ C1⊥, then r (1, r), (1, r) = r (1 + r2) = 0,since 1 + r2 ∈ Rk×, then r = 0, a contradiction. (2) “ =⇒ ” If Ci is LCD, suppose 1 + ηη¯ ∈ Rk×(2ei), then 1 + ηη¯ ∈ u . We have uk−1(1 + ηη¯) = 0,i.e., uk−1(1, η), (1, η) H = 0,then uk−1(1, η) ∈ Ci⊥H ,which implies uk−1(1, η) ∈ Ci ∩ Ci⊥H , a contradiction.
“ ⇐= ” If 1 + ηη¯ ∈ Rk×(2ei), assume Ci is not LCD, then Ci ∩ Ci⊥H = {0}. If η ∈ Rk×(2ei),then Ci⊥H = (1, − η1¯ ) ,there exist k1, k2 ∈ Rk×(2ei) such that k1(1, η) = k2(1, − η1¯ ),i.e., k1(1 + ηη¯) = 0. And 1 + ηη¯ ∈ Rk×(2ei), then k1 = 0, a contradiction. If η ∈ u ,we can let η = ua1 + u2a2 + · · · + uk−1ak−1, ai ∈ Fq2ei , 0 ≤ i ≤ k − 1,then the generator matrix of Ci⊥H is of the form
−(ua¯1 + u2a¯2 + · · · + uk−1a¯k−1) 1
0
uk−1k3 ,
where k3 ∈ Fq2ei . Thus, there exist k4, k5, k6 ∈ Rk×(2ei) such that k4(1, ua1 + u2a2 + · · · + uk−1ak−1) = k5(−(ua¯1 + u2a¯2 + · · · + uk−1a¯k−1), 1) + k6(0, uk−1k3),we then obtain
k4 = −(ua¯1 + u2a¯2 + · · · + uk−1a¯k−1)k5,
(ua1 + u2a2 + · · · + uk−1ak−1)k4 = k5 + uk−1k3k6,
(2)
by (2), we get k4 ∈ Rk×(2ei),but −(ua¯1 + u2a¯2 + · · · + uk−1a¯k−1)k5 ∈ u , a contradiction. (3) “ =⇒ ” If Cj ⊕ Cj is LCD, assume 1 + η η ∈ Rk×(dj ), then 1 + η η ∈ u . We have uk−1(1 + η η ) = 0,i.e., uk−1(1, η ), (1, η ) = 0,then uk−1(1, η ) ∈ Cj ⊥ (or uk−1(1, η ) ∈ Cj⊥), which implies uk−1(1, η ) ∈ Cj ∩ Cj ⊥ (or uk−1(1, η ) ∈ Cj ∩ Cj⊥), a contradiction.
“ ⇐= ” If 1 + η η ∈ Rk×(dj ), assume Cj ⊕ Cj is not LCD, then
Cj ∩ Cj ⊥ = {0}, Cj ∩ Cj⊥ = {0}.
If Cj ∩ Cj ⊥ = {0}, then there exists k ∈ Rk×(dj ) such that k (1, η ) ∈ Cj ∩ Cj ⊥,i.e., k (1, η ), (1, η ) = k (1 + η η ) = 0, a contradiction.
Theorem 3.2 Let m denote a positive odd integer, and q a prime coprime with m. If xm − 1
s
can be factored into irreducible polynomials over Rk as in (1), where m = 1 + 2ei +
i=2 t
2 dj . Then
j =1
(1) the total number of self-dual double circulant codes over Rk is
s
t
B (qei + 1)qei (k−1) (qdj − 1)qdj (k−1), where
i=2
j =1
1)
when
q
is
a
power
of
2,
B
=
2q
k 2
,
k
is
even,
or
B
=
2q
k−1 2
,
k
is
odd;
Cryptography and Communications (2019) 11:717–734
723
2) when q is a power of odd prime, B = 2.
(2) the total number of LCD double circulant codes over Rk is
s
t
(q − 2)qk−1 (q2ei − (qei + 1))q2(k−1)ei (q2kdj − q2(k−1)dj (qdj − 1)).
i=2
j =1
Proof (1) We can count the number of self-dual double circulant codes by counting their
constituent codes.
Let (1, r) be the generator of the self-dual code C1 over Rk. By Theorem 2.1, when
k
k−1
q is a power of 2, the number of r is equal to 2q 2 , where k is even (2q 2 ,where k is
odd); when q is a power of odd prime, the number of choices for r is equal to 2.
Let (1, cei ) be the generators of Hermitian self-dual codes Ci over Rk(2ei), 2 ≤ i ≤ s, then (1, cei ), (1, cei ) H = 1 + cei cei = 0. Let cei = c0 + uc1 + · · · + uk−1ck−1, where c ∈ Fq2ei , 0 ≤ ≤ k − 1, we then have
⎧ qei
⎪⎪⎪⎪⎪⎪ cc0cc0qei
= −1, + c cqei
= 0,
⎪⎪⎪⎪⎪⎨ c00c12qeei + c11c01qeei + c2c0qeei = 0, e
c0c3q i + c1c2q i + c2c1q i + c3c0q i = 0,
(3)
⎪⎪⎪⎪⎪ c0c4qei + c1c3qei + c2c2qei + c3c1qei + c4c0qei = 0,
⎪⎪⎪⎪⎪ ...
⎪⎩ qei
q ei
q ei
c0ck−1 + c1ck−2 + · · · + ck−1c0 = 0.
⎧
⎪⎪⎪⎪⎪
N orm(c0 T r(c cqei
) = −1, ) = 0,
⎪⎪⎪⎪⎪
T
r
0
(c
1
cq
ei
)
+
N
or
m(c
) = 0,
⎪⎪⎪⎪⎨ T r(c00c23qqeeii )+T r(c1c2qqee1ii ) = 0, )+T r(c c )+Norm(c ) = 0,
⇐⇒
⎪⎪⎪
T .
r (c0 c4
13
2
⎪⎪ .
⎪⎪⎪⎪⎪⎪
. T
r
(c
cq ei
)+T r(c
cq ei
)+· · ·+T r(c
c ) = 0, when k is even, or
⎪⎪⎪⎩ T r(c00ckkq−−ei11)+T r(c11ckkq−−ei22)+· · ·+T r(c kk−−223 c kk2+1 )+N orm(c k−1 ) = 0, when k is odd,
2
2
2
where the N orm() and T r() are maps norm and trace from Fq2ei to Fqei . So there are qei + 1 roots for N orm(c0) = −1 and qei choices for ci for 1 ≤ ≤ k − 1. Clearly, the number of solutions of (3) is equal to (qei + 1)qei(k−1).
As for reciprocal pairs, note that a pair (hj (x), h∗j (x)) both of degree dj leads to counting dual pairs of codes (for the Euclidean inner product) of length 2 over Rk(dj ), that is to count the number of solutions of 1 + cdj cdj = 0, where (1, cdj ) and (1, cdj ) are the generators of Cj and Cj , respectively. If cdj ∈ Rk×(dj ), then cdj = − cd1j , there are |Rk×(dj )| = (qdj − 1)qdj (k−1) choices for (cdj , cdj ). If cdj ∈ Rk(dj )\Rk×(dj ), then cdj = ux1 + u2x2 + · · · + uk−1xk−1 ∈ u . In this case, 1 + cdj cdj = 0, which is
impossible. (2) The code C1 is an LCD code, by Lemma 3.1 (1), we can get 1 + r2 ∈ Rk×. Let r =
r0 +ur1 +· · ·+uk−1rk−1 ∈ Rk,then 1+r2 = 1+(r0 +ur1 +u2r2 +· · ·+uk−1rk−1)2 =
724
Cryptography and Communications (2019) 11:717–734
1 + r02 + 2r0r1u + (2r0r2 + r12)u2 + · · · + (r0rk−1 + r1rk−2 + · · · + rk−1r0)uk−1 ∈ Rk×. Hence, the number of r is equal to (q − 2)qk−1.
The code Ci is an LCD code, by Lemma 3.1 (2), we can get 1 + ηη¯ ∈ Rk×(2ei). Let η = η0 + uη1 + · · · + uk−1ηk−1,then 1 + ηη¯ = 1 + (η0 + uη1 + · · · + uk−1ηk−1)(η0qei + uη1qei + · · · + uk−1ηkq−ei1) = 1 + η0qei +1 + u(η0η1qei + η1η0qei ) + · · · + uk−1(η0ηkq−ei1 + η1ηkq−ei2 + · · · + ηk−1η0qei ) ∈ Rk×(2ei). Hence, the number of η is equal to (q2ei − (qei + 1))q2(k−1)ei .
Next, we count the number of LCD double circulant codes of length 2 over Rk(dj ) for the pairs hj (x) and h∗j (x) with deg(hj (x)) =deg(h∗j (x)) = dj . By Lemma 3.1 (3), we then get
Cj Cj ⊥ = {0}, ⇐⇒ 1 + η η ∈ R× .
Cj Cj ⊥ = {0}.
k(dj )
Without loss of generality, we discuss on the unit character of η as follows.
1) If η ∈ Rk×(dj ), then η ∈ − η1 +Rk×(dj ) and | −η1 +Rk×(dj )| = |Rk×(dj )| = q(k−1)dj (qdj −1). Hence, there are |Rk×(dj )|2 = q2(k−1)dj (qdj − 1)2 choices for (η , η ).
2) If η ∈ Rk(dj )\{Rk×(dj )∪{0}}, let η = η0 +uη1 +· · ·+uk−1ηk−1, then η = uη1+u2η2+ · · ·+uk−1ηk−1, where η 1 can’t be all zero, 1 ≤ 1 ≤ k−1, η 2 ∈ Fqdj , 0 ≤ 2 ≤ k−1. We then have 1+η η = 1+uη1η0 +u2(η1η1 +η2η0 )+· · ·+uk−1(η1ηk−2 +η2ηk−3 + · · · + ηk−1η0 ) ∈ Rk×(dj ). Thus, there are (q(k−1)dj − 1)qkdj choices for (η , η ).
3) If η = 0, then η ∈ Rk(dj ), thus there are qkdj choices for η .
Hence, the number of the last case about reciprocal pairs is q2(k−1)dj (qdj −1)2 +(q(k−1)dj − 1)qkdj +qkdj = q2kdj −q2(k−1)dj (qdj −1). The proof of the theorem is now completed.
3.2 Double negacirculant codes (λ = −1)
In this subsection, assume m is an even integer and gcd(m, q) = 1, where q is a prime power. We can cast the factorization of xm + 1 into distinct basic irreducible polynomials
over Rk as follows.
s
t
xm + 1 =
gi (x) hj (x)h∗j (x),
(4)
i=1
j =1
where ∈ Rk×, gi (x) = gi∗(x) with deg(gi(x)) = 2ei , 1 ≤ i ≤ s, and h∗j (x) is the reciprocal polynomial of hj (x) with deg(hj (x)) =deg(h∗j (x)) = dj , 1 ≤ j ≤ t. Using the same notations and argument as in Subsection 3.1, we can easily carry out the result as follows:
Rk [x ] xm + 1
s
Rk(2ei )
i=1
⎛
⎞
t
⊕ ⎝ (Rk(dj ) ⊕ Rk(dj ))⎠ ,
j =1
and ⎛ ⎞
s
t
C
Ci ⊕ ⎝ (Cj ⊕ Cj )⎠ .
i=1
j =1
Cryptography and Communications (2019) 11:717–734
725
Theorem 3.3 Let m denote a positive even integer, and q a prime power coprime with m.
s
t
The factorization of xm + 1 over Rk is of the form (4) with m = 2ei + 2 dj . Then
i=1
j =1
(1) the total number of self-dual double negacirculant codes over Rk is
s
t
(qei + 1)qei (k−1) (qdj − 1)qdj (k−1).
i=1
j =1
(2) the total number of LCD double negacirculant codes over Rk is
s
t
(q2ei − (qei + 1))q2(k−1)ei (q2kdj − q2(k−1)dj (qdj − 1)).
i=1
j =1
Proof This proof is similar to that of Theorem 3.2, so we omitted it here.
Now, we consider a special factorization of xm + 1, where m is a power of 2, q is an odd prime. According to [17, Theorem 1] and [2, Theorems 5.1,5.3], we know that xm + 1 can be factored into two (resp. four) basic irreducible polynomials, which are reciprocal of each other over Rk, by limiting the size of and U , because Fq is a subring of Rk. We can get the following lemma.
Lemma 3.4 Let m be a power of 2, q ≡ ±1(mod 4).
(1) If q = 22e ± 1, e is odd, then xm + 1 factors into two basic irreducible polynomials
over Rk as follows.
xm + 1 = h(x)h∗(x)
with deg(h(x)) =deg(h∗(x)) = m2 . In this case, the number of self-dual (resp. LCD) double negacirculant codes over Rk is
m
(q 2
−
1)q
m(k−1) 2
(r
esp.q
km
−
q
m(k−1)(q
m 2
− 1))).
(2) If q = 23e ± 1, e is odd, then xm + 1 factors into four basic irreducible polynomials
over Rk as follows.
xm + 1 = h1(x)h∗1(x)h2(x)h∗2(x)
(5)
with deg(h1(x)) =deg(h∗1(x)) =deg(h2(x)) =deg(h∗2(x)) = m4 . In this case, the
number of self-dual (resp. LCD) double negacirculant codes over Rk is
m
(q 4
−
1)2q
m(k−1) 2
(r
esp.(q
km 2
m(k−1) m
− q 2 (q 4
− 1))2).
3.3 Quasi-twisted codes of index two (λ = 1 + ωut)
In this subsection, we focus on the case (1 + ωut) = (1 + ωut)−1 = (1 − ωut). According to [19], xm − (1 + ωut) can be uniquely expressed as
s
t
xm − (1 + ωut) = ςg1(x) gi (x) hj (x)h∗j (x),
(6)
i=2
j =1
where m is an odd, then g1(x) = x − (1 + ωut), ς ∈ Rk×, gi (x) = gi∗(x) with deg(gi(x)) = 2ei, 2 ≤ i ≤ s, and h∗j (x) is the reciprocal polynomial of hj (x) with deg(hj (x)) =deg(h∗j (x)) = dj , 1 ≤ j ≤ t.
Minjia Shi, Liqin Qian, Patrick Sole
To cite this version:
Minjia Shi, Liqin Qian, Patrick Sole. On self-dual and LCD quasi-twisted codes of index two over a special chain ring. Cryptography and Communications - Discrete Structures, Boolean Functions and Sequences , Springer, 2019, 11, pp.717 - 734. 10.1007/s12095-018-0322-5. hal-02411619
HAL Id: hal-02411619 https://hal.archives-ouvertes.fr/hal-02411619
Submitted on 17 Dec 2019
HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.
L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.
Cryptography and Communications (2019) 11:717–734 https://doi.org/10.1007/s12095-018-0322-5
On self-dual and LCD quasi-twisted codes of index two over a special chain ring
Liqin Qian2 · Minjia Shi1,2 · Patrick Sole´ 3
Received: 26 April 2018 / Accepted: 25 July 2018 / Published online: 13 August 2018 © Springer Science+Business Media, LLC, part of Springer Nature 2018
Abstract Let q be a prime power, and let Fq denote the finite field of order q. Consider the chain ring Rk = Fq [u]/ uk with k ≥ 1 an integer. We study self-dual and LCD quasi-twisted codes of index two and twisting constant λ over Rk for the metric induced by the standard Gray map. Some special factorizations of xm − λ over Rk are studied. By random coding, we obtain four classes of asymptotically good self-dual λ-circulant codes and four classes of asymptotically good LCD λ-circulant codes over Rk.
Keywords Double circulant codes · Gray map · Self-dual codes · LCD codes · Quasi-twisted codes
Mathematics Subject Classification (2010) 94 B15 · 94 B25 · 05 E30
This research is supported by National Natural Science Foundation of China (61672036), Excellent Youth Foundation of Natural Science Foundation of Anhui Province (1808085J20), Technology Foundation for Selected Overseas Chinese Scholar, Ministry of Personnel of China (05015133) and Key projects of support program for outstanding young talents in Colleges and Universities (gxyqZD2016008).
Minjia Shi [email protected]
Liqin Qian qianliqin [email protected] Patrick Sole´ [email protected]
1 Key Laboratory of Intelligent Computing Signal Processing, Ministry of Education, Anhui University, No.3 Feixi Road, Hefei, Anhui, 230039, China
2 School of Mathematical Sciences, Anhui University, Hefei, Anhui, 230601, China 3 CNRS/LAGA, University of Paris 8, 93 526 Saint-Denis, France
718
Cryptography and Communications (2019) 11:717–734
1 Introduction
Self-dual codes are important for a number of practical and theoretical reasons, as witnessed by [1, 3, 12]. Another important class of codes defined by their duality properties is that of Linear codes with Complementary Duals (LCD), which were introduced by Massey in 1992 for information theoretic reasons (see [18]). They have found applications recently in Boolean masking [6, 7]. Massey [18] shows that LCD codes are asymptotically good. LCD codes are universal: for q > 3 there is an algorithm that turns any linear code into an equivalent LCD code [5]. Still, it is of interest to find direct methods of construction of LCD codes as in [4]. One such method is to use quasi-cyclic and quasi-twisted codes. In that direction, self-dual double circulant (resp. double negacirculant) codes over finite fields have been studied recently in [1, 3], from the viewpoint of enumeration and asymptotic performance. Some classes of quasi-twisted codes have been studied over finite chain rings in [19]. In [2], A. Alahmadi et al. have studied the linear complementary-dual multinegacirculant codes. Motivated by the techniques in [1–3, 8, 19, 20], we use the Chinese Remainder Theorem (CRT) approach to quasi-twisted codes as introduced in [11, 13, 14]. In particular, we study two classes of self-dual (resp. LCD) negacirculant codes of index 2 over Rk. Combining with [19], we study two families of factorizations of xm − λ over Rk with m an odd prime, gcd(m, q) = 1. When these special factorizations are thus enforced, we derive exact enumeration formulae, and obtain asymptotic lower bounds on the minimum Hamming distance of the Gray image of these codes.
The material is arranged as follows. In Section 2, we give some background materials on the ring Rk and study the case when the element −1 is a square in Rk. In Section 3, we derive the enumeration formulae of self-dual (resp. LCD) double circulant and double negacirculant codes of co-index m and we study the special factorizations of xm − λ with m an odd prime, and gcd(m, q) = 1. Then, we also obtain the enumeration formulae of self-dual (resp. LCD) double λ-circulant codes. In Section 4, we derive a modified Varshamov-Gilbert bound on the relative distance of the codes considered, building on exact enumeration results. Finally, Section 5 contains conclusions and open problems.
2 Preliminaries
2.1 The ring Rk = Fq [u]/ uk
Let q be a prime power, and let Fq denote the finite field of order q. Consider the local ring Rk = Fq [u]/ uk where uk = 0 with unique maximal ideal u . In double λ-circulant codes case, we will consider the chain ring Rk = Fq [u]/ uk when it contains a square root
of −1.
Theorem 2.1 If a0 + ua1 + · · · + uk−1ak−1 ∈ Rk = Fq [u]/ uk is a square root of −1 if and only if
(1) q is a power of 2, a02 = −1, a1 = a2 = · · · = a k−2 = 0, where a k , a k+2 , · · · , ak−1 ∈
2
2
2
Fq when k is even; a02 = −1, a1 = a2 = · · · = a k−1 = 0, a k+1 , a k+2 , · · · , ak−1 ∈ Fq ,
2
2
2
when k is odd; or
(2) q = pκ where p ≡ 1(mod 4) or q = p2κ where p ≡ 3(mod 4), a02 = −1, a1 = a2 = · · · = ak−1 = 0.
Cryptography and Communications (2019) 11:717–734
719
Proof Note that the condition is obviously sufficient. To prove its necessity, when q is a
power of 2, we have (a0 + a1u + · · · + ak−1uk−1)2 = a02 + a12u2 + · · · + ak2−1u2(k−1) =
−1,when k is even, a02 = −1, a1 = a2 = · · · = a k−2 = 0, a k , a k+2 , · · · , ak−1 ∈ Fq ; when
2
2
2
k is odd, a02 = −1, a1 = a2 = · · · = a k−1 = 0, a k+1 , a k+2 , · · · , ak−1 ∈ Fq . When q is a
2
2
2
power of an odd prime, we have (a0 + a1u + · · · + ak−1uk−1)2 = a02 + 2a0a1u + (2a0a2 +
a12)u2 + · · · + (a0ak−1 + a1ak−2 + · · · + ak−1a0)uk−1 = −1,where ai ∈ Fq , 0 ≤ i ≤ k − 1.
Then we get a02 = −1, a1 = a2 = · · · = ak−1 = 0. Thus a0 is a square root of −1 over Fq
if and only if q ≡ 1(mod 4).
2.2 Codes
A linear code C over Rk of length n is an Rk-submodule of Rkn. If x = (x1, x2, · · · , xn) and y = (y1, y2, · · · , yn) are two elements of Rkn, their standard (Euclidean) inner product is defined by
n
x, y = xi yi ,
i=1
and their Hermitian scalar inner product is defined by
n
x, y H = xi y¯i ,
i=1
where the operation is performed in Rk. For all z = z0 + uz1 + · · · + uk−1zk−1 ∈ Fq2Q + uFq2Q + · · · + uk−1Fq2Q , the conjugation of z over Fq2Q + uFq2Q + · · · + uk−1Fq2Q is
z = z0qQ + uz1qQ + · · · + uk−1zkq−Q1, where Q is a positive integer. The Euclidean (resp. Hermitian) dual code of C is denoted by C⊥ (resp. C⊥H ) and defined as C⊥ = {y ∈ Rkn | x, y = 0, ∀x ∈ C} (resp. C⊥H = {y ∈ Rkn | x, y H = 0, ∀x ∈ C}).
A linear code C of length n over Rk is called a self-dual code (resp. Hermitian selfdual code) if C = C⊥ (resp. C = C⊥H ). A linear code C of length n over Rk is called a linear code with complementary dual (LCD) if C C⊥ = {0} or C C⊥H = {0}.
A matrix A over Rk is said to be λ-circulant if its rows are obtained by successive λ-
shifts from the first row. In this paper, we consider double λ-circulant codes over Rk, that
is [2m, m] codes with generator matrices G = (I, A) with A an m × m λ-circulant matrix,
we can view such a code as an Rk-module in Rk2, generated by (1, h) with the first row of
A being the x-expansion of h in the ring
Rk [x] x m −λ
.
If C(m) is a family of codes with parameters [m, km, dm] over Fq , the rate ρ and relative
distance δ are defined as ρ = limm→s∞up kmm and δ = lmim→i∞nf dmm , respectively. A family of codes is good if ρδ > 0.
In number theory, Artin’s conjecture on primitive roots states that a given integer q which is neither a perfect square nor −1 is a primitive root modulo infinitely many primes [16]. This was proved conditionally under the Generalized Riemann Hypothesis (GRH) by Hoo-
ley [9]. Hence, we can get infinite families of double λ-circulant codes C(m) over Rk where the analysis is made for xm − 1 with a special factorization.
Recall the q-ary entropy function defined for 0 ≤ t˜ ≤ q−q 1 by
Hq (t˜) = 0, t˜logq (q − 1) − t˜logq (t˜) − (1 − t˜)logq (1 − t˜),
if t˜ = 0, if 0 < t˜ ≤ q−q 1 .
720
Cryptography and Communications (2019) 11:717–734
This quantity is instrumental in the estimation of the volume of high-dimensional Hamming
balls when the base field is Fq . The result we are using is that the volume of the Hamming ball of radius t˜m is asymptotically equivalent, up to subexponential terms, to qmHq(t˜), when 0 < t˜ < 1, and m goes to infinity [10, Lemma 2.10.3].
2.3 Gray map
Any integer z can be written uniquely in base p as z = p0(z) + pp1(z) + p2p2(z) + · · · , where 0 ≤ pi (z) ≤ p − 1, i = 0, 1, 2, . . .. The Gray map : R → Fppk−1 is defined as follows:
(a) = (b0, b1, b2, . . . , bpk−1−1),
where a = a0 + a1u + · · · + ak−1uk−1. Then for all 0 ≤ i ≤ pk−2 − 1, 0 ≤ τ ≤ p − 1,we
have
⎧
⎨ ak−1 + k−2 pl−1(i)al + τ a0,
bip+τ = ⎩
l=1
a1 + τ a0,
if k ≥ 3, if k = 2.
Note that, more generally, Gray maps have been defined at the level of finite chain rings
in [15, 23], linking codes over rings to codes over finite fields. For instance, when p =
k = 2, it is easy to check that the Gray map adopted in the trace codes of [21] is the
same as the Gray map defined here. As an additional example, when p = k = 3, write (a0 + a1u + a2u2) = (b0, b1, b2, · · · , b8). According to the definition above, we have
k−2
0 ≤ i ≤ 2, 0 ≤ τ ≤ 2 and pl−1(i)al = p0(i)a1 = ia1. Then we get
l=1
b0 = a2, b1 = a2 + a0, b2 = a2 + 2a0, b3 = a2 + a1, b4 = a2 + a1 + a0,
b5 = a2 + a1 + 2a0, b6 = a2 + 2a1, b7 = a2 + 2a1 + a0, b8 = a2 + 2a1 + 2a0.
It is easy to extend the Gray map from Rkm to Fppk−1m, and we also know from [22] that is injective and linear.
3 Algebraic structure of λ-circulant codes of index two
In this section, we study the exact enumeration of the double self-dual and LCD λ-circulant codes over Rk.
3.1 Double circulant codes (λ = 1)
In this subsection, we assume m is an odd integer and gcd(m, q) = 1. We can cast the factorization of xm − 1 into distinct basic irreducible polynomials over Rk = Fq [u]/ uk in
the form
s
t
xm − 1 = δ(x − 1) gi (x) hj (x)h∗j (x),
(1)
i=2
j =1
Cryptography and Communications (2019) 11:717–734
721
where δ is a unit in Rk, the polynomial gi(x) is self-reciprocal of degree 2ei for 2 ≤ i ≤ s, and h∗j (x) is the reciprocal polynomial of hj (x) with degree dj for 1 ≤ j ≤ t. By the
Chinese Remainder Theorem (CRT), we have
Rk [x ] xm − 1
⎛
⎞
Rk[x] ⊕
s
t
R [x]/ g (x) ⊕⎝
R [x]/ h (x) ⊕ R [x]/ h∗(x) ⎠
x−1
k
i
k
j
k
j
i=2
j =1
⎛
⎞
Fq [u, x] ⊕
s
Fq [u, x]
t
⊕⎝
Fq [u, x] ⊕ Fq [u, x] ⎠
uk, x − 1 i=2 uk, gi (x)
j=1 uk, hj (x)
uk
,
h
∗ j
(
x
)
⎛
s
t
Rk ⊕
(Fq2ei + uFq2ei + · · · + uk−1Fq2ei ) ⊕⎝
Fqdj + uFqdj + · · ·
i=2
j =1
⎞
+uk−1Fqdj ⊕ (Fqdj + uFqdj + · · · + uk−1Fqdj ) ⎠
:=Rk ⊕
s
Rk(2ei )
i=2
⎛
⎞
t
⊕⎝ (Rk(dj ) ⊕ Rk(dj ))⎠ .
j =1
Note that all of these rings are extensions of Rk. This decomposition naturally extends to
(
Rk [x] x m −1
)2
as
Rk[x] 2 xm − 1
Rk ⊕
s
Rk2(2ei )
i=2
⎛
t
⊕⎝
j =1
⎞ Rk2(dj ) ⊕ Rk2(dj ) ⎠ .
In particular, each linear code C of length 2 over
Rk [x] x m −1
can be decomposed as the “CRT
sum”
⎛
⎞
s
t
C C1 ⊕
Ci ⊕ ⎝ (Cj ⊕ Cj )⎠ ,
i=2
j =1
where C1 is a linear code over Rk of length 2, Ci is a linear code over Rk(2ei) of length 2 for each 2 ≤ i ≤ s, and Cj and Cj are linear codes over Rk(dj ) of length 2 for each 1 ≤ j ≤ t, which are called the constituents of C.
Lemma 3.1 Keep the same notations as above, then
(1) C1 is LCD if and only if 1 + r2 ∈ Rk× with C1 = (1, r) ; (2) Ci is LCD if and only if 1 + ηη¯ ∈ Rk×(2ei) with Ci = (1, η) ; (3) Cj ⊕ Cj are LCD if and only if 1 + η η ∈ Rk×(dj ) with Cj = (1, η ) and Cj =
(1, η ) .
Proof (1) “ =⇒ ” If C1 is LCD, suppose 1 + r2 ∈ Rk×, then 1 + r2 ∈ u . We have uk−1(1 + r2) = 0,i.e., uk−1(1, r), (1, r) = 0,then uk−1(1, r) ∈ C1⊥,which implies uk−1(1, r) ∈ C1 ∩ C1⊥, a contradiction.
722
Cryptography and Communications (2019) 11:717–734
“ ⇐= ” If 1 + r2 ∈ Rk×, assume C1 is not LCD, then C1 ∩ C1⊥ = {0}. Hence, there exists r ∈ Rk× such that r (1, r) ∈ C1 ∩ C1⊥, then r (1, r), (1, r) = r (1 + r2) = 0,since 1 + r2 ∈ Rk×, then r = 0, a contradiction. (2) “ =⇒ ” If Ci is LCD, suppose 1 + ηη¯ ∈ Rk×(2ei), then 1 + ηη¯ ∈ u . We have uk−1(1 + ηη¯) = 0,i.e., uk−1(1, η), (1, η) H = 0,then uk−1(1, η) ∈ Ci⊥H ,which implies uk−1(1, η) ∈ Ci ∩ Ci⊥H , a contradiction.
“ ⇐= ” If 1 + ηη¯ ∈ Rk×(2ei), assume Ci is not LCD, then Ci ∩ Ci⊥H = {0}. If η ∈ Rk×(2ei),then Ci⊥H = (1, − η1¯ ) ,there exist k1, k2 ∈ Rk×(2ei) such that k1(1, η) = k2(1, − η1¯ ),i.e., k1(1 + ηη¯) = 0. And 1 + ηη¯ ∈ Rk×(2ei), then k1 = 0, a contradiction. If η ∈ u ,we can let η = ua1 + u2a2 + · · · + uk−1ak−1, ai ∈ Fq2ei , 0 ≤ i ≤ k − 1,then the generator matrix of Ci⊥H is of the form
−(ua¯1 + u2a¯2 + · · · + uk−1a¯k−1) 1
0
uk−1k3 ,
where k3 ∈ Fq2ei . Thus, there exist k4, k5, k6 ∈ Rk×(2ei) such that k4(1, ua1 + u2a2 + · · · + uk−1ak−1) = k5(−(ua¯1 + u2a¯2 + · · · + uk−1a¯k−1), 1) + k6(0, uk−1k3),we then obtain
k4 = −(ua¯1 + u2a¯2 + · · · + uk−1a¯k−1)k5,
(ua1 + u2a2 + · · · + uk−1ak−1)k4 = k5 + uk−1k3k6,
(2)
by (2), we get k4 ∈ Rk×(2ei),but −(ua¯1 + u2a¯2 + · · · + uk−1a¯k−1)k5 ∈ u , a contradiction. (3) “ =⇒ ” If Cj ⊕ Cj is LCD, assume 1 + η η ∈ Rk×(dj ), then 1 + η η ∈ u . We have uk−1(1 + η η ) = 0,i.e., uk−1(1, η ), (1, η ) = 0,then uk−1(1, η ) ∈ Cj ⊥ (or uk−1(1, η ) ∈ Cj⊥), which implies uk−1(1, η ) ∈ Cj ∩ Cj ⊥ (or uk−1(1, η ) ∈ Cj ∩ Cj⊥), a contradiction.
“ ⇐= ” If 1 + η η ∈ Rk×(dj ), assume Cj ⊕ Cj is not LCD, then
Cj ∩ Cj ⊥ = {0}, Cj ∩ Cj⊥ = {0}.
If Cj ∩ Cj ⊥ = {0}, then there exists k ∈ Rk×(dj ) such that k (1, η ) ∈ Cj ∩ Cj ⊥,i.e., k (1, η ), (1, η ) = k (1 + η η ) = 0, a contradiction.
Theorem 3.2 Let m denote a positive odd integer, and q a prime coprime with m. If xm − 1
s
can be factored into irreducible polynomials over Rk as in (1), where m = 1 + 2ei +
i=2 t
2 dj . Then
j =1
(1) the total number of self-dual double circulant codes over Rk is
s
t
B (qei + 1)qei (k−1) (qdj − 1)qdj (k−1), where
i=2
j =1
1)
when
q
is
a
power
of
2,
B
=
2q
k 2
,
k
is
even,
or
B
=
2q
k−1 2
,
k
is
odd;
Cryptography and Communications (2019) 11:717–734
723
2) when q is a power of odd prime, B = 2.
(2) the total number of LCD double circulant codes over Rk is
s
t
(q − 2)qk−1 (q2ei − (qei + 1))q2(k−1)ei (q2kdj − q2(k−1)dj (qdj − 1)).
i=2
j =1
Proof (1) We can count the number of self-dual double circulant codes by counting their
constituent codes.
Let (1, r) be the generator of the self-dual code C1 over Rk. By Theorem 2.1, when
k
k−1
q is a power of 2, the number of r is equal to 2q 2 , where k is even (2q 2 ,where k is
odd); when q is a power of odd prime, the number of choices for r is equal to 2.
Let (1, cei ) be the generators of Hermitian self-dual codes Ci over Rk(2ei), 2 ≤ i ≤ s, then (1, cei ), (1, cei ) H = 1 + cei cei = 0. Let cei = c0 + uc1 + · · · + uk−1ck−1, where c ∈ Fq2ei , 0 ≤ ≤ k − 1, we then have
⎧ qei
⎪⎪⎪⎪⎪⎪ cc0cc0qei
= −1, + c cqei
= 0,
⎪⎪⎪⎪⎪⎨ c00c12qeei + c11c01qeei + c2c0qeei = 0, e
c0c3q i + c1c2q i + c2c1q i + c3c0q i = 0,
(3)
⎪⎪⎪⎪⎪ c0c4qei + c1c3qei + c2c2qei + c3c1qei + c4c0qei = 0,
⎪⎪⎪⎪⎪ ...
⎪⎩ qei
q ei
q ei
c0ck−1 + c1ck−2 + · · · + ck−1c0 = 0.
⎧
⎪⎪⎪⎪⎪
N orm(c0 T r(c cqei
) = −1, ) = 0,
⎪⎪⎪⎪⎪
T
r
0
(c
1
cq
ei
)
+
N
or
m(c
) = 0,
⎪⎪⎪⎪⎨ T r(c00c23qqeeii )+T r(c1c2qqee1ii ) = 0, )+T r(c c )+Norm(c ) = 0,
⇐⇒
⎪⎪⎪
T .
r (c0 c4
13
2
⎪⎪ .
⎪⎪⎪⎪⎪⎪
. T
r
(c
cq ei
)+T r(c
cq ei
)+· · ·+T r(c
c ) = 0, when k is even, or
⎪⎪⎪⎩ T r(c00ckkq−−ei11)+T r(c11ckkq−−ei22)+· · ·+T r(c kk−−223 c kk2+1 )+N orm(c k−1 ) = 0, when k is odd,
2
2
2
where the N orm() and T r() are maps norm and trace from Fq2ei to Fqei . So there are qei + 1 roots for N orm(c0) = −1 and qei choices for ci for 1 ≤ ≤ k − 1. Clearly, the number of solutions of (3) is equal to (qei + 1)qei(k−1).
As for reciprocal pairs, note that a pair (hj (x), h∗j (x)) both of degree dj leads to counting dual pairs of codes (for the Euclidean inner product) of length 2 over Rk(dj ), that is to count the number of solutions of 1 + cdj cdj = 0, where (1, cdj ) and (1, cdj ) are the generators of Cj and Cj , respectively. If cdj ∈ Rk×(dj ), then cdj = − cd1j , there are |Rk×(dj )| = (qdj − 1)qdj (k−1) choices for (cdj , cdj ). If cdj ∈ Rk(dj )\Rk×(dj ), then cdj = ux1 + u2x2 + · · · + uk−1xk−1 ∈ u . In this case, 1 + cdj cdj = 0, which is
impossible. (2) The code C1 is an LCD code, by Lemma 3.1 (1), we can get 1 + r2 ∈ Rk×. Let r =
r0 +ur1 +· · ·+uk−1rk−1 ∈ Rk,then 1+r2 = 1+(r0 +ur1 +u2r2 +· · ·+uk−1rk−1)2 =
724
Cryptography and Communications (2019) 11:717–734
1 + r02 + 2r0r1u + (2r0r2 + r12)u2 + · · · + (r0rk−1 + r1rk−2 + · · · + rk−1r0)uk−1 ∈ Rk×. Hence, the number of r is equal to (q − 2)qk−1.
The code Ci is an LCD code, by Lemma 3.1 (2), we can get 1 + ηη¯ ∈ Rk×(2ei). Let η = η0 + uη1 + · · · + uk−1ηk−1,then 1 + ηη¯ = 1 + (η0 + uη1 + · · · + uk−1ηk−1)(η0qei + uη1qei + · · · + uk−1ηkq−ei1) = 1 + η0qei +1 + u(η0η1qei + η1η0qei ) + · · · + uk−1(η0ηkq−ei1 + η1ηkq−ei2 + · · · + ηk−1η0qei ) ∈ Rk×(2ei). Hence, the number of η is equal to (q2ei − (qei + 1))q2(k−1)ei .
Next, we count the number of LCD double circulant codes of length 2 over Rk(dj ) for the pairs hj (x) and h∗j (x) with deg(hj (x)) =deg(h∗j (x)) = dj . By Lemma 3.1 (3), we then get
Cj Cj ⊥ = {0}, ⇐⇒ 1 + η η ∈ R× .
Cj Cj ⊥ = {0}.
k(dj )
Without loss of generality, we discuss on the unit character of η as follows.
1) If η ∈ Rk×(dj ), then η ∈ − η1 +Rk×(dj ) and | −η1 +Rk×(dj )| = |Rk×(dj )| = q(k−1)dj (qdj −1). Hence, there are |Rk×(dj )|2 = q2(k−1)dj (qdj − 1)2 choices for (η , η ).
2) If η ∈ Rk(dj )\{Rk×(dj )∪{0}}, let η = η0 +uη1 +· · ·+uk−1ηk−1, then η = uη1+u2η2+ · · ·+uk−1ηk−1, where η 1 can’t be all zero, 1 ≤ 1 ≤ k−1, η 2 ∈ Fqdj , 0 ≤ 2 ≤ k−1. We then have 1+η η = 1+uη1η0 +u2(η1η1 +η2η0 )+· · ·+uk−1(η1ηk−2 +η2ηk−3 + · · · + ηk−1η0 ) ∈ Rk×(dj ). Thus, there are (q(k−1)dj − 1)qkdj choices for (η , η ).
3) If η = 0, then η ∈ Rk(dj ), thus there are qkdj choices for η .
Hence, the number of the last case about reciprocal pairs is q2(k−1)dj (qdj −1)2 +(q(k−1)dj − 1)qkdj +qkdj = q2kdj −q2(k−1)dj (qdj −1). The proof of the theorem is now completed.
3.2 Double negacirculant codes (λ = −1)
In this subsection, assume m is an even integer and gcd(m, q) = 1, where q is a prime power. We can cast the factorization of xm + 1 into distinct basic irreducible polynomials
over Rk as follows.
s
t
xm + 1 =
gi (x) hj (x)h∗j (x),
(4)
i=1
j =1
where ∈ Rk×, gi (x) = gi∗(x) with deg(gi(x)) = 2ei , 1 ≤ i ≤ s, and h∗j (x) is the reciprocal polynomial of hj (x) with deg(hj (x)) =deg(h∗j (x)) = dj , 1 ≤ j ≤ t. Using the same notations and argument as in Subsection 3.1, we can easily carry out the result as follows:
Rk [x ] xm + 1
s
Rk(2ei )
i=1
⎛
⎞
t
⊕ ⎝ (Rk(dj ) ⊕ Rk(dj ))⎠ ,
j =1
and ⎛ ⎞
s
t
C
Ci ⊕ ⎝ (Cj ⊕ Cj )⎠ .
i=1
j =1
Cryptography and Communications (2019) 11:717–734
725
Theorem 3.3 Let m denote a positive even integer, and q a prime power coprime with m.
s
t
The factorization of xm + 1 over Rk is of the form (4) with m = 2ei + 2 dj . Then
i=1
j =1
(1) the total number of self-dual double negacirculant codes over Rk is
s
t
(qei + 1)qei (k−1) (qdj − 1)qdj (k−1).
i=1
j =1
(2) the total number of LCD double negacirculant codes over Rk is
s
t
(q2ei − (qei + 1))q2(k−1)ei (q2kdj − q2(k−1)dj (qdj − 1)).
i=1
j =1
Proof This proof is similar to that of Theorem 3.2, so we omitted it here.
Now, we consider a special factorization of xm + 1, where m is a power of 2, q is an odd prime. According to [17, Theorem 1] and [2, Theorems 5.1,5.3], we know that xm + 1 can be factored into two (resp. four) basic irreducible polynomials, which are reciprocal of each other over Rk, by limiting the size of and U , because Fq is a subring of Rk. We can get the following lemma.
Lemma 3.4 Let m be a power of 2, q ≡ ±1(mod 4).
(1) If q = 22e ± 1, e is odd, then xm + 1 factors into two basic irreducible polynomials
over Rk as follows.
xm + 1 = h(x)h∗(x)
with deg(h(x)) =deg(h∗(x)) = m2 . In this case, the number of self-dual (resp. LCD) double negacirculant codes over Rk is
m
(q 2
−
1)q
m(k−1) 2
(r
esp.q
km
−
q
m(k−1)(q
m 2
− 1))).
(2) If q = 23e ± 1, e is odd, then xm + 1 factors into four basic irreducible polynomials
over Rk as follows.
xm + 1 = h1(x)h∗1(x)h2(x)h∗2(x)
(5)
with deg(h1(x)) =deg(h∗1(x)) =deg(h2(x)) =deg(h∗2(x)) = m4 . In this case, the
number of self-dual (resp. LCD) double negacirculant codes over Rk is
m
(q 4
−
1)2q
m(k−1) 2
(r
esp.(q
km 2
m(k−1) m
− q 2 (q 4
− 1))2).
3.3 Quasi-twisted codes of index two (λ = 1 + ωut)
In this subsection, we focus on the case (1 + ωut) = (1 + ωut)−1 = (1 − ωut). According to [19], xm − (1 + ωut) can be uniquely expressed as
s
t
xm − (1 + ωut) = ςg1(x) gi (x) hj (x)h∗j (x),
(6)
i=2
j =1
where m is an odd, then g1(x) = x − (1 + ωut), ς ∈ Rk×, gi (x) = gi∗(x) with deg(gi(x)) = 2ei, 2 ≤ i ≤ s, and h∗j (x) is the reciprocal polynomial of hj (x) with deg(hj (x)) =deg(h∗j (x)) = dj , 1 ≤ j ≤ t.