11institutetext:  Key Laboratory of Mathematics Mechanization, Academy of
Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China
22institutetext: School of Mathematical Sciences, University of Chinese
Academy of Sciences, Beijing, China
22email<EMAIL_ADDRESS>22email<EMAIL_ADDRESS>33institutetext:
Normandie Univ, UNICAEN, CNRS, LMNO, 14000 Caen, France 33email:
<EMAIL_ADDRESS>
# Generalized Implicit Factorization Problem

Yansong Feng 1122 Abderrahmane Nitaj ${}^{(\textrm{{\char 0\relax}})}$ 33
Yanbin Pan ${}^{(\textrm{{\char 0\relax}})}$ 1122

###### Abstract

The Implicit Factorization Problem (IFP) was first introduced by May and
Ritzenhofen at PKC’09, which concerns the factorization of two RSA moduli
$N_{1}=p_{1}q_{1}$ and $N_{2}=p_{2}q_{2}$, where $p_{1}$ and $p_{2}$ share a
certain consecutive number of least significant bits. Since its introduction,
many different variants of IFP have been considered, such as the cases where
$p_{1}$ and $p_{2}$ share most significant bits or middle bits at the same
positions. In this paper, we consider a more generalized case of IFP, in which
the shared consecutive bits can be located at any positions in each prime, not
necessarily required to be located at the same positions as before. We propose
a lattice-based algorithm to solve this problem under specific conditions, and
also provide some experimental results to verify our analysis.

###### Keywords:

Implicit Factorization Problem Lattice LLL algorithm Coppersmith’s algorithm.

##  1 Introduction

In 1977, Rivest, Shamir, and Adleman proposed the famous RSA encryption scheme
[18], whose security is based on the hardness of factoring large integers. RSA
is now a very popular scheme with many applications in industry for
information security protection. Therefore, its security has been widely
analyzed. Although it seems infeasible to break RSA with large modulus
entirely with a classical computer now, there still exist many vulnerable RSA
instances. For instance, small public key [7, 8] or small secret key [4] can
lead to some attacks against RSA. In addition, side-channel attacks pose a
great threat to RSA [2, 5, 6], targeting the decryption device to obtain more
information about the private key.

It is well known that additional information on the private keys or the prime
factors can help attack the RSA scheme efficiently. In 1997, Coppersmith [8,
14] proposed an attack that can factor the RSA modulus $N=pq$ in polynomial
time if at least half of the most (or least) significant bits of $p$ are
given. In 2013, by using Coppersmith’s method, Bernstein et al. [3] showed
that an attacker can efficiently factor 184 distinct RSA keys generated by
government-issued smart cards.

At PKC 2009, May and Ritzenhofen [15] introduced the Implicit Factorization
Problem (IFP). It concerns the question of factoring two $n$-bit RSA moduli
$N_{1}=p_{1}q_{1}$ and $N_{2}=p_{2}q_{2}$, given the implicit information that
$p_{1}$ and $p_{2}$ share $\gamma n$ of their consecutive least significant
bits, while $q_{1}$ and $q_{2}$ are $\alpha n$-bit. Using a two-dimensional
lattice, May and Ritzenhofen obtained a heuristic result that this implicit
information is sufficient to factor $N_{1}$ and $N_{2}$ with a lattice-based
algorithm, provided that $\gamma n>2\alpha n+2$.

In a follow-up work at PKC 2010, Faugère et al. [9] generalized the Implicit
Factorization Problem to the case where the most significant bits (MSBs) or
the middle bits of $p_{1}$ and $p_{2}$ are shared. Specifically, they
established the bound of $\gamma n>2\alpha n+2$ for the case where the MSBs
are shared, using a two-dimensional lattice. For the case where the middle
bits of $p_{1}$ and $p_{2}$ are shared, Faugère et al. obtained a heuristic
result that $q_{1}$ and $q_{2}$ could be found from a three-dimensional
lattice if $\gamma n>4\alpha n+6$.

In 2011, Sarkar and Maitra [21] further expanded the Implicit Factorization
Problem by revealing the relations between the Approximate Common Divisor
Problem (ACDP) and the Implicit Factorization Problem, and presented the bound
of $\gamma>2\alpha-\alpha^{2}$ for the following three cases.

  1. 1.

the primes $p_{1}$, $p_{2}$ share an amount of the least significant bits
(LSBs);

  2. 2.

the primes $p_{1}$, $p_{2}$ share an amount of most significant bits (MSBs);

  3. 3.

the primes $p_{1}$, $p_{2}$ share both an amount of least significant bits and
an amount of most significant bits.

In 2016, Lu et al. [13] presented a novel algorithm and improved the bounds to
$\gamma>2\alpha-2\alpha^{2}$ for all the above three cases of the Implicit
Factorization Problem. In 2015, Peng et al. [17] revisited the Implicit
Factorization Problem with shared middle bits and improved the bound of
Faugère et al. [9] up to $\gamma>4\alpha-3\alpha^{2}$. The bound was further
enhanced by Wang et al. [22] in 2018 up to
$\gamma>4\alpha-4\alpha\sqrt{\alpha}$.

It is worth noting that in the previous cases, the shared bits are located at
the same position for the primes $p_{1}$ and $p_{2}$.

In this paper, we present a more generalized case of the Implicit
Factorization Problem that allows for arbitrary consecutive shared locations,
rather than requiring them to be identical in the primes, as in previous
research. More precisely, we propose the Generalized Implicit Factorization
Problem (GIFP), which concerns the factorization of two $n$-bit RSA moduli
$N_{1}=p_{1}q_{1}$ and $N_{2}=p_{2}q_{2}$ when $p_{1}$ and $p_{2}$ share
$\gamma n$ consecutive bits, where the shared bits are not necessarily
required to be located at the same positions. See Fig. 1 for an example, where
the starting positions for the shared bits in $p_{1}$ and $p_{2}$ may be
different.

((a))

((b))

Figure 1: Shared bits $M$ for $p_{1}$ and $p_{2}$

We transform the GIFP into the Approximate Common Divisor Problem and then,
employ Coppersmith’s method with some optimization strategy, we propose a
polynomial time algorithm to solve it when $\gamma>4\alpha(1-\sqrt{\alpha})$.

In Table 1, we present a comparison of our new bound on $\gamma$ with the
known former bounds obtained by various methods to solve the Implicit
Factorization Problem.

| LSBs | MSBs | both LSBs-MSBs | Middle bits | General
---|---|---|---|---|---
May, Ritzenhofen [15] | $2\alpha$ | - | - | - | -
Faugère, et al. [9] | $2\alpha$ | - | - | $4\alpha$ | -
Sarkar, Maitra [21] | $2\alpha-\alpha^{2}$ | $2\alpha-\alpha^{2}$ | $2\alpha-\alpha^{2}$ | - | -
Lu, et al. [13] | $2\alpha-2\alpha^{2}$ | $2\alpha-2\alpha^{2}$ | $2\alpha-2\alpha^{2}$ | - | -
Peng, et al.[17] | - | - | - | $4\alpha-3\alpha^{2}$ | -
Wang, et al.[22] | - | - | - | $4\alpha(1-\sqrt{\alpha})$ | -
This work | - | - | - | - | $4\alpha(1-\sqrt{\alpha})$
Table 1: Asymptotic lower bound of $\gamma$ in the Implicit Factorization
Problem for $n$-bit $N_{1}=p_{1}q_{2}$ and $N_{2}=p_{2}q_{2}$ where the number
of shared bits is $\gamma n$, $q_{1}$ and $q_{2}$ are $\alpha n$-bit.

It can be seen in Table 1 that the bounds for the Implicit Factorization
Problem for sharing middle bits are inferior to those of other variants. This
is because the unshared bits in the Implicit Factorization Problem for LSBs or
MSBs or both LSBs and MSBs are continuous, and only one variable is necessary
to represent the unshared bits while at least two variables are needed to
represent the unshared bits in the Implicit Factorization Problem sharing
middle bits or GIFP. In addition, our bound for GIFP is identical to the
variant of IFP sharing the middle bits located in the same position. However,
it is obvious that the GIFP relaxes the constraints for the positions of the
shared bits.

Therefore, with the same bound for the number of shared bits as in the IFP
sharing middle bits at the same position, we show that the Implicit
Factorization Problem can still be solved efficiently when the positions for
the sharing bits are located differently.

There are still open problems, and the most important one is: can we improve
our bound $4\alpha\left(1-\sqrt{\alpha}\right)$ for GIFP to
$2\alpha-2\alpha^{2}$ or even better? A positive answer seems not easy since
the bound for GIFP directly yields a bound for any known variant of IFP.
Improving the bound for GIFP to the one better than
$4\alpha\left(1-\sqrt{\alpha}\right)$ means that we can improve the bound for
the variant of IFP sharing the middle bits located in the same position, and
improving the bound for GIFP to the one better than $2\alpha-2\alpha^{2}$
means that we can improve the bound for any known variant of IFP.

####  1.0.1 Roadmap

Our paper is structured as follows. Section 2 presents some required
background for our approaches. In Section 3, we present our analysis of the
Generalized Implicit Factorization Problem, which constitutes our main result.
Section 4 details the experimental results used to validate our analysis.
Finally, we provide a brief conclusion in Section 5. The source code is
available at:

https://github.com/fffmath/gifp.

##  2 Notations and Preliminaries

####  2.0.1 Notations

Let $\mathbb{Z}$ denote the ring of integers, i.e., the set of all integers.
We use lowercase bold letters (e.g., $\mathbf{v}$) for vectors and uppercase
bold letters (e.g., $\mathbf{A}$) for matrices. The notation $\binom{n}{m}$
represents the number of ways to select $m$ items out of $n$ items, which is
defined as $\frac{n!}{m!(n-m)!}$. If $m>n$, we set $\binom{n}{m}=0$.

###  2.1 Lattices, SVP, and LLL

Let $m\geq 2$ be an integer. A lattice is a discrete additive subgroup of
$\mathbb{R}^{m}$. A more explicit definition is presented as follows.

######  Definition 1 (Lattice)

Let $\mathbf{v_{1}},\mathbf{v_{2}},\dots,\mathbf{v_{n}}\in\mathbb{R}^{m}$ be
$n$ linearly independent vectors with $n\leq m$. The lattice $\mathcal{L}$
spanned by
$\left\\{\mathbf{v_{1}},\mathbf{v_{2}},\dots,\mathbf{v_{n}}\right\\}$ is the
set of all integer linear combinations of
$\left\\{\mathbf{v_{1}},\mathbf{v_{2}},\dots,\mathbf{v_{n}}\right\\}$, i.e.,

$\mathcal{L}=\left\\{\mathbf{v}\in\mathbb{R}^{m}\ |\
\mathbf{v}=\sum_{i=1}^{n}a_{i}\mathbf{v_{i}},a_{i}\in\mathbb{Z}\right\\}.$

The integer $n$ denotes the rank of the lattice $\mathcal{L}$, while $m$
represents its dimension. The lattice $\mathcal{L}$ is said to be full rank if
$n=m$. We use the matrix $\mathbf{B}\in\mathbb{R}^{n\times m}$, where each
vector $\mathbf{v_{i}}$ contributes a row to $\mathbf{B}$. The determinant of
$\mathcal{L}$ is defined as
$\det(\mathcal{L})=\sqrt{\det\left(\mathbf{B}\mathbf{B}^{t}\right)}$, where
$\mathbf{B}^{t}$ is the transpose of $\mathbf{B}$. If $\mathcal{L}$ is full
rank, this reduces to
$\det(\mathcal{L})=\left|\det\left(\mathbf{B}\right)\right|$.

The Shortest Vector Problem (SVP) is one of the famous computational problems
in lattices.

######  Definition 2 (Shortest Vector Problem (SVP))

Given a lattice $\mathcal{L}$, the Shortest Vector Problem (SVP) asks to find
a non-zero lattice vector $\mathbf{v}\in\mathcal{L}$ of minimum Euclidean
norm, i.e., find $\mathbf{v}\in\mathcal{L}\backslash\\{\mathbf{0}\\}$ such
that $\|\mathbf{v}\|\leq\|\mathbf{w}\|$ for all non-zero
$\mathbf{w}\in\mathcal{L}$.

Although SVP is NP-hard under randomized reductions [1], there exist
algorithms that can find a relatively short vector, instead of the exactly
shortest vector, in polynomial time, such as the famous LLL algorithm proposed
by Lenstra, Lenstra, and Lovasz [12] in 1982. The following result is useful
for our analysis[14].

######  Theorem 2.1 (LLL Algorithm)

Given an $n$-dimensional lattice $\mathcal{L}$, we can find an LLL-reduced
basis $\left\\{\mathbf{v_{1}},\mathbf{v_{2}},\dots,\mathbf{v_{n}}\right\\}$ of
$\mathcal{L}$ in polynomial time, which satisfies

$\|\mathbf{v_{i}}\|\leq
2^{\frac{n(n-1)}{4(n+1-i)}}\det(\mathcal{L})^{\frac{1}{n+1-i}},\quad\text{for}\quad
i=1,\dots,n.$

Theorem 2.1 presents the upper bounds for the norm of the $i$-th vector in the
LLL-basis using the determinant of the lattice.

###  2.2 Coppersmith’s method

In 1996, Coppersmith [8, 14] proposed a lattice-based method for finding small
solutions of univariate modular polynomial equations modulo a positive integer
$M$, and another lattice-based method for finding the small roots of bivariate
polynomial equations. The methods are based on finding short vectors in a
lattice. We briefly sketch the idea below. More details can be found in [14].

Let $M$ be a positive integer, and $f(x_{1},\dots,x_{k})$ be a polynomial with
integer coefficients. Suppose we want to find a small solution
$(y_{1},\dots,y_{k})$ of the modular equation $f(x_{1},\dots,x_{k})\equiv
0\allowbreak\mkern 8.0mu({\operator@font mod}\mkern 6.0muM)$ with the bounds
$y_{i}<X_{i}$ for $i=1,\ldots,k$.

The first step is to construct a set $G$ of $k$-variate polynomial equations
such that, for each $g_{i}\in G$ with $i=1,\ldots,k$, we have
$g_{i}(y_{1},\dots,y_{k})\equiv 0\allowbreak\mkern 8.0mu({\operator@font
mod}\mkern 6.0muM)$. Then we use the coefficient vectors of
$g_{i}(x_{1}X_{1},\dots,x_{k}X_{k})$, $i=1,\ldots,k$, to construct a
$k$-dimensional lattice $\mathcal{L}$. Applying the LLL algorithm to
$\mathcal{L}$, we get a new set $H$ of $k$ polynomial equations
$h_{i}(x_{1},\dots,x_{k})$, $i=1,\ldots,k$, with integer coefficients such
that $h_{i}(y_{1},\dots,y_{k})\equiv 0\allowbreak\mkern 8.0mu({\operator@font
mod}\mkern 6.0muM)$. The following result shows that one can get
$h_{i}(y_{1},\dots,y_{k})=0$ over the integers in some cases, where for
$h(x_{1},\dots,x_{k})=\sum_{i_{1}\ldots i_{k}}a_{i_{1}\ldots
i_{k}}x_{1}^{i_{1}}\cdots x_{1}^{i_{k}}$, the Euclidean norm is defined by
$\left\|h(x_{1},\dots,x_{k})\right\|=\sqrt{\sum_{i_{1}\ldots
i_{k}}a_{i_{1}\ldots i_{k}}^{2}}$.

######  Theorem 2.2 (Howgrave-Graham [11])

Let $h(x_{1},\dots,x_{k})\in\mathbb{Z}[x_{1},\ldots,x_{k}]$ be a polynomial
with at most $\omega$ monomials. Let $M$ be a positive integer. If there exist
$k$ integers $(y_{1},\dots,y_{k})$ satisfying the following two conditions:

  1. 1.

$h(y_{1},\dots,y_{k})\equiv 0\allowbreak\mkern 8.0mu({\operator@font
mod}\mkern 6.0muM)$, and there exist $k$ positive integers $X_{1},\dots,X_{k}$
such that $\left|y_{1}\right|\leq X_{1},\ldots,\left|y_{k}\right|\leq X_{k}$,

  2. 2.

$\left\|h(x_{1}X_{1},\dots,x_{k}X_{k})\right\|<\frac{M}{\sqrt{\omega}}$,

then $h(y_{1},\dots,y_{k})=0$ holds over the integers.

From Theorem 2.1, we can obtain the vectors
$\mathbf{v_{1}},\mathbf{v_{2}},\dots,\mathbf{v_{k}}$ in the LLL reduced basis
of $\mathcal{L}$. This yields $k$ integer polynomials
$h_{1}(x_{1},\dots,x_{k})$, $\dots$, $h_{k}(x_{1},\dots,x_{k})$, all of which
share the desired solution $(y_{1},\dots,y_{k})$, that is
$h_{i}(y_{1},\dots,y_{k})\equiv 0\allowbreak\mkern 8.0mu({\operator@font
mod}\mkern 6.0muM)$ for $i=1,\ldots,k$.

To combine Theorem 2.1 and Theorem 2.2, for $i=k$, we set

$2^{\frac{n(n-1)}{4(n+1-i)}}\det(\mathcal{L})^{\frac{1}{n+1-i}}<\frac{M}{\sqrt{\dim(\mathcal{L})}}.$

Ultimately, the attainment of the desired root hinges upon effectively
resolving the system of integer polynomials using either the resultant method
or the Gröbner basis approach. However, in order for a Gröbner basis
computation to find the common root, the following heuristic assumption needs
to hold.

###### Assumption 1

The $k$ polynomials $h_{i}(x_{1},\cdots,x_{k})$, $i=1,\cdots,k$, that are
derived from the reduced basis of the lattice in the Coppersmith method are
algebraically independent. Equivalently, the common root of the polynomials
$h_{i}(x_{1},\cdots,x_{k})$ can be found by computing the resultant or
computing the Gröbner basis.

Assumption 1 is often used in connection with Coppersmith’s method in the
multivariate scenario [4, 14, 21, 13, 22]. Since our attack in Section 3
relies on Assumption 1, it is heuristic. However, our experiments in Section 4
justify the validity of our attack and show that Assumption 1 perfectly holds
true.

##  3 Generalized Implicit Factorization Problem

This section presents our analysis of the Generalized Implicit Factorization
Problem (GIFP) in which $p_{1}$ and $p_{2}$ share an amount of consecutive
bits at different positions.

###  3.1 Description of GIFP

This section proposes the Generalized Implicit Factorization Problem (GIFP),
which concerns the factorization of two $n$-bit RSA moduli, $N_{1}=p_{1}q_{1}$
and $N_{2}=p_{2}q_{2}$, under the implicit hint that the primes $p_{1}$ and
$p_{2}$ share a specific number, $\gamma n$, of consecutive bits.

In contrast to previous studies [9, 13, 15, 19, 20, 22], where the shared bits
were assumed to be located at the same positions in $p_{1}$ and $p_{2}$, the
proposed GIFP considers a more general case where the shared bits can be
situated at arbitrary positions.

######  Definition 3 (GIFP($n,\alpha,\gamma$))

Given two $n$-bit RSA moduli $N_{1}=p_{1}q_{1}$ and $N_{2}=p_{2}q_{2}$, where
$q_{1}$ and $q_{2}$ are $\alpha n$-bit, assume that $p_{1}$ and $p_{2}$ share
$\gamma n$ consecutive bits, where the shared bits may be located in different
positions of $p_{1}$ and $p_{2}$. The Generalized Implicit Factorization
Problem (GIFP) asks to factor $N_{1}$ and $N_{2}$.

The introduction of GIFP expands the scope of the Implicit Factorization
Problem and presents a more realistic and challenging scenario that can arise
in practical applications. In real-world settings, it is more probable to
encounter situations where the shared location of bits differs between primes.
Therefore, it is essential to develop algorithms and analysis that can handle
such cases where the shared bits are situated at different positions. By
considering the Generalized Implicit Factorization Problem (GIFP), we need to
avoid situations where the system that creates RSA keys lack entropy.

###  3.2 Algorithm for GIFP

We will show our analysis of the GIFP in this subsection. The main idea is
also to relate the Approximate Common Divisor Problem (ACDP) to the Implicit
Factorization Problem.

###### Theorem 3.1

Under Assumption 1, GIFP($n,\alpha,\gamma$) can be solved in polynomial time
when

$\gamma>4\alpha\left(1-\sqrt{\alpha}\right),$

provided that $\alpha+\gamma\leq 1$.

###### Proof

Without loss of generality, we can assume that the starting and ending
positions of the shared bits are known. When these positions are unknown, we
can simply traverse the possible starting positions of the shared bits, which
will just scale the time complexity for the case that we know the position by
a factor $\mathcal{O}(n^{2})$.

Hence, we suppose that $p_{1}$ shares $\gamma n$-bits from the $\beta_{1}n$-th
bit to $(\beta_{1}+\gamma)n$-th bit, and $p_{2}$ shares bits from
$\beta_{2}n$-th bit to $(\beta_{2}+\gamma)n$-th bit, where $\beta_{1}$ and
$\beta_{2}$ are known with $\beta_{1}\leq\beta_{2}$ (see Fig. 1 ). Then we can
write

$p_{1}=x_{1}+M_{0}2^{\beta_{1}n}+x_{2}2^{(\beta_{1}+\gamma)n},\quad
p_{2}=x_{3}+M_{0}2^{\beta_{2}n}+x_{4}2^{(\beta_{2}+\gamma)n},$

with $M_{0}<2^{\gamma n}$, $x_{1}<2^{\beta_{1}n}$,
$x_{2}<2^{(\beta-\beta_{1})n}$, $x_{3}<2^{\beta_{2}n}$,
$x_{4}<2^{(\beta-\beta_{2})n}$ where $\beta=1-\alpha-\gamma$. From this, we
deduce

$\displaystyle 2^{(\beta_{2}-\beta_{1})n}p_{1}$
$\displaystyle=x_{1}2^{(\beta_{2}-\beta_{1})n}+M_{0}2^{\beta_{2}n}+x_{2}2^{(\beta_{2}+\gamma)n}$
$\displaystyle=x_{1}2^{(\beta_{2}-\beta_{1})n}+(p_{2}-x_{3}-x_{4}2^{(\beta_{2}+\gamma)n})+x_{2}2^{(\beta_{2}+\gamma)n}$
$\displaystyle=p_{2}+(x_{1}2^{(\beta_{2}-\beta_{1})n}-x_{3})+(x_{2}-x_{4})2^{(\beta_{2}+\gamma)n}.$

Then, multiplying by $q_{2}$, we get

$N_{2}+(x_{1}2^{(\beta_{2}-\beta_{1})n}-x_{3})q_{2}+(x_{2}-x_{4})q_{2}2^{(\beta_{2}+\gamma)n}=2^{(\beta_{2}-\beta_{1})n}p_{1}q_{2}.$

Next, we define the polynomial

$f(x,y,z)=xz+2^{(\beta_{2}+\gamma)n}yz+N_{2},$

which shows that $(x_{1}2^{(\beta_{2}-\beta_{1})n}-x_{3},x_{2}-x_{4},q_{2})$
is a solutions of

$f(x,y,z)\equiv 0\allowbreak\mkern 8.0mu({\operator@font mod}\mkern
6.0mu2^{(\beta_{2}-\beta_{1})n}p_{1}).$

Let $m$ and $t$ be integers to be optimized later with $0\leq t\leq m$. To
apply Coppersmith’s method, we consider a family of polynomials
$g_{i,j}(x,y,z)$ for $0\leq i\leq m$ and $0\leq j\leq m-i$:

$g_{i,j}(x,y,z)=(yz)^{j}f(x,y,z)^{i}\left(2^{(\beta_{2}-\beta_{1})n}\right)^{m-i}N_{1}^{\max(t-i,0)}.$

These polynomials satisfy

$\displaystyle g_{i,j}$
$\displaystyle\left(x_{1}2^{(\beta_{2}-\beta_{1})n}-x_{3},x_{2}-x_{4},q_{2}\right)$
$\displaystyle=$ $\displaystyle\
(x_{2}-x_{4})^{j}q_{2}^{j}\left(2^{(\beta_{2}-\beta_{1})n}p_{1}q_{2}\right)^{i}\left(2^{(\beta_{2}-\beta_{1})n}\right)^{m-i}N_{1}^{\max(t-i,0)}$
$\displaystyle=$ $\displaystyle\
(x_{2}-x_{4})^{j}q_{2}^{j+i}q_{1}^{\max(t-i,0)}\left(2^{(\beta_{2}-\beta_{1})n}\right)^{m}p_{1}^{\max(t-i,0)+i}$
$\displaystyle\equiv$ $\displaystyle\ 0\allowbreak\mkern
8.0mu\left({\operator@font mod}\mkern
6.0mu\left(2^{(\beta_{2}-\beta_{1})n}\right)^{m}p_{1}^{t}\right).$

On the other hand, we have

$\displaystyle\left|x_{1}2^{(\beta_{2}-\beta_{1})n}-x_{3}\right|$
$\displaystyle\leq\max\left(x_{1}2^{(\beta_{2}-\beta_{1})n},x_{3}\right)$
$\displaystyle\leq\max\left(2^{\beta_{1}n}2^{(\beta_{2}-\beta_{1})n},2^{\beta_{1}n}\right)$
$\displaystyle=2^{\beta_{2}n},$

and

$|x_{2}-x_{4}|\leq\max(x_{2},x_{4})=2^{(\beta-\beta_{1})n}.$

Also, we have $q_{2}=2^{\alpha n}$. We then set

$X=2^{\beta_{2}n},\ Y=2^{(\beta-\beta_{1})n},\ Z=2^{\alpha n}.$

To reduce the determinant of the lattice, we introduce a new variable $w$ for
$p_{2}$, and multiply the polynomials $g_{i,j}(x,y,z)$ by a power $w^{s}$ for
some $s$ that will be optimized later. Similar to $t$, we also require $0\leq
s\leq m$

Note that we can replace $zw$ in $g_{i,j}(x,y,z)w^{s}$ by $N_{2}$. We want to
eliminate this multiple. Since $\gcd(N_{2},2N_{1})=1$, there exists an inverse
of $N_{2}$, denoted as $N_{2}^{-1}$, such that $N_{2}N_{2}^{-1}\equiv
1\allowbreak\mkern 8.0mu\left({\operator@font mod}\mkern
6.0mu\left(2^{(\beta_{2}-\beta_{1})n}\right)^{m}N_{1}^{t}\right)$. We then
eliminate $(zw)^{\min(s,i+j)}$ from the original polynomial by multiplying it
by $N_{2}^{-\min(s,i+j)}\allowbreak\mkern 8.0mu\left({\operator@font
mod}\mkern 6.0mu\left(2^{(\beta_{2}-\beta_{1})n}\right)^{m}N_{1}^{t}\right)$,
while ensuring that the resulting polynomial evaluation is still a multiple of
$\left(2^{(\beta_{2}-\beta_{1})n}\right)^{m}p_{1}^{t}$. By selecting the
appropriate parameter $s$, we aim to reduce the determinant of the lattice. To
this end, we consider a new family of polynomials $G_{i,j}(x,y,z,w)$ for
$0\leq i\leq m$ and $0\leq j\leq m-i$:

$G_{i,j}(x,y,z,w)=(yz)^{j}w^{s}f(x,y,z)^{i}\left(2^{(\beta_{2}-\beta_{1})n}\right)^{m-i}N_{1}^{\max(t-i,0)}N_{2}^{-\min(s,i+j)},$

where $N_{2}^{-\min(s,i+j)}$ is computed modulo
$\left(2^{(\beta_{2}-\beta_{1})n}\right)^{m}N_{1}^{t}$, and each term $zw$ is
replaced by $N_{2}$. For example, suppose $s\geq 1$, then

$G_{0,1}(x,y,z,w)=yw^{s-1}N_{2}\left(2^{(\beta_{2}-\beta_{1})n}\right)^{m}N_{1}^{t}N_{2}^{-1}.$

Next, consider the lattice $\mathcal{L}$ spanned by the matrix $\mathbf{B}$
whose rows are the coefficients of the polynomials $G_{i,j}(Xx,Yy,Zz,Ww)$
where, for $0\leq i\leq m$, $0\leq j\leq m-i$, The rows are ordered following
the rule that $G_{i,j}\prec G_{i^{\prime},j^{\prime}}$ if $i<i^{\prime}$ or if
$i=i^{\prime}$ and $j<j^{\prime}$. The columns are ordered following the
monomials so that $x^{i}y^{j}z^{i+j-\min(s,i+j)}w^{s-\min(s,i+j)}\prec
x^{i^{\prime}}y^{j^{\prime}}z^{i^{\prime}+j^{\prime}-\min(s,i^{\prime}+j^{\prime})}w^{s-\min(s,i^{\prime}+j^{\prime})}$
if $i<i^{\prime}$ or if $i=i^{\prime}$ and $j<j^{\prime}$. Table 2 presents a
matrix $\mathbf{B}$ with $m=3$, $s=2$, $t=2$ where $\ast$ represents a nonzero
term.

$\displaystyle\tiny{\begin{array}[]{||c||c|c|c|c|c|c|c|c|c|c||}\hline\cr
G_{i,j}&w^{2}&yw&y^{2}&y^{3}z&xw&xy&xy^{2}z&x^{2}&x^{2}yz&x^{3}z\\\
\hline\cr\hline\cr G_{0,0}&W^{2}M^{3}N_{1}^{2}&0&0&0&0&0&0&0&0&0\\\
G_{0,1}&0&YWM^{3}N_{1}^{2}&0&0&0&0&0&0&0&0\\\
G_{0,2}&0&0&Y^{2}M^{3}N_{1}^{2}&0&0&0&0&0&0&0\\\
G_{0,3}&0&0&0&Y^{3}ZM^{3}N_{1}^{2}&0&0&0&0&0&0\\\
G_{1,0}&\ast&\ast&0&0&XWM^{2}N_{1}&0&0&0&0&0\\\
G_{1,1}&0&\ast&\ast&0&0&XYM^{2}N_{1}&0&0&0&0\\\
G_{1,2}&0&0&\ast&\ast&0&0&XY^{2}ZM^{2}N_{1}&0&0&0\\\
G_{2,0}&\ast&\ast&\ast&0&\ast&\ast&0&X^{2}M&0&0\\\
G_{2,1}&0&\ast&\ast&\ast&0&\ast&\ast&0&X^{2}YZM&0\\\
G_{3,0}&\ast&\ast&\ast&\ast&\ast&\ast&\ast&\ast&\ast&X^{3}Z\\\
\hline\cr\end{array}}$ Table 2: The matrix of the lattice with $m=3$, $s=2$,
$t=2$ and $M=2^{(\beta_{2}-\beta_{1})n}$.

By construction, the square matrix $B$ is left triangular. Hence, the
dimension of the lattice is

$\omega=\sum_{i=0}^{m}\sum_{j=0}^{m-i}1=\sum_{i=0}^{m}(m-i+1)=\frac{1}{2}(m+1)(m+2)$

and its determinant is

$\det(B)=\det(\mathcal{L})=X^{e_{X}}Y^{e_{Y}}Z^{e_{Z}}W^{e_{W}}2^{(\beta_{2}-\beta_{1})ne_{M}}N_{1}^{e_{N}},$

with

$\displaystyle e_{X}$
$\displaystyle=\sum_{i=0}^{m}\sum_{j=0}^{m-i}i=\frac{1}{6}m(m+1)(m+2),$
$\displaystyle e_{Y}$
$\displaystyle=\sum_{i=0}^{m}\sum_{j=0}^{m-i}j=\frac{1}{6}m(m+1)(m+2),$
$\displaystyle e_{Z}$
$\displaystyle=\sum_{i=0}^{m}\sum_{j=0}^{m-i}(i+j-\min(s,i+j))$
$\displaystyle=\frac{1}{3}m(m+1)(m+2)+\frac{1}{6}s(s+1)(s+2)-\frac{1}{2}s(m+1)(m+2),$
$\displaystyle e_{W}$
$\displaystyle=\sum_{i=0}^{m}\sum_{j=0}^{m-i}(s-\min(s,i+j))=\frac{1}{6}s(s+1)(s+2),$
$\displaystyle e_{N}$
$\displaystyle=\sum_{i=0}^{t}\sum_{j=0}^{m-i}(t-i)=\frac{1}{6}t(t+1)(3m-t+4),$
$\displaystyle e_{M}$
$\displaystyle=\sum_{i=0}^{m}\sum_{j=0}^{m-i}(m-i)=\frac{1}{3}m(m+1)(m+2).$

The former results are detailed in Appendix 0.A. To combine Theorem 2.1 and
Theorem 2.2, we set

$2^{\frac{\omega(\omega-1)}{4(\omega+1-i)}}\det(\mathcal{L})^{\frac{1}{\omega+1-i}}<\frac{\left(2^{(\beta_{2}-\beta_{1})n}\right)^{m}p_{1}^{t}}{\sqrt{\omega}},$

with $i=2$. Then

$\det(\mathcal{L})<\frac{1}{2^{\frac{\omega-1}{4}}\sqrt{\omega}}\left(2^{(\beta_{2}-\beta_{1})n}\right)^{\omega
m}p_{1}^{t\omega},$

and

$\displaystyle
X^{e_{X}}Y^{e_{Y}}Z^{e_{Z}}W^{e_{W}}2^{(\beta_{2}-\beta_{1})ne_{M}}N_{1}^{e_{N}}<\frac{1}{2^{\frac{\omega-1}{4}}\sqrt{\omega}}\left(2^{(\beta_{2}-\beta_{1})n}\right)^{\omega
m}p_{1}^{t\omega}.$ (2)

Next, we set $s=\sigma m$ with $0\leq\sigma\leq 1$, $t=\tau m$ with
$0\leq\tau\leq 1$, and we use $N\approx 2^{n}$, $p_{1}\approx
2^{(1-\alpha)n}$, $X=2^{\beta_{2}n}$, $Y=2^{(\beta-\beta_{1})n}$, $Z=2^{\alpha
n}$, $W=2^{(1-\alpha)n}$ and the most significant parts of $e_{X}$, $e_{Y}$,
$e_{Z}$, $e_{W}$, $e_{N}$, $e_{M}$ as

$\displaystyle e_{X}$ $\displaystyle=\frac{1}{6}m^{3}+o\left(m^{3}\right),$
$\displaystyle e_{Y}$ $\displaystyle=\frac{1}{6}m^{3}+o\left(m^{3}\right),$
$\displaystyle e_{Z}$
$\displaystyle=\frac{1}{3}m^{3}+\frac{1}{6}\sigma^{3}m^{3}-\frac{1}{2}\sigma
m^{3}+o\left(m^{3}\right),$ $\displaystyle e_{W}$
$\displaystyle=\frac{1}{6}\sigma^{3}m^{3}+o\left(m^{3}\right),$ $\displaystyle
e_{N}$ $\displaystyle=\frac{1}{6}\tau^{2}(3-\tau)m^{3}+o\left(m^{3}\right),$
$\displaystyle e_{M}$ $\displaystyle=\frac{1}{3}m^{3}+o\left(m^{3}\right).$

Similarly, we use

$m\omega=\frac{1}{2}m^{3}+o\left(m^{3}\right).$

Then, after taking logarithms, dividing by $nm^{3}$, and neglecting the very
small terms, i.e., $o\left(m^{3}\right)$, the inequality (2) implies

$\displaystyle\frac{1}{6}\beta_{2}+\frac{1}{6}(\beta-\beta_{1})+\alpha(\frac{1}{3}+\frac{1}{6}\sigma^{3}-\frac{1}{2}\sigma)+\frac{1}{6}\sigma^{3}(1-\alpha)+\frac{1}{3}(\beta_{2}-\beta_{1})+\frac{1}{6}\tau^{2}(3-\tau)$
$\displaystyle<\ \frac{1}{2}(\beta_{2}-\beta_{1})+\frac{1}{2}(1-\alpha)\tau.$

Using $\beta=1-\alpha-\gamma$, the former inequality is equivalent to

$\tau^{2}(3-\tau)-3(1-\alpha)\tau+\sigma^{3}-3\alpha\sigma+1-\gamma+\alpha<0.$

The left side is optimized for $\tau_{0}=1-\sqrt{\alpha}$ and
$\sigma_{0}=\sqrt{\alpha}$, which gives

$3\alpha-2\alpha\sqrt{\alpha}-1-2\alpha\sqrt{\alpha}+1+\alpha-\gamma<0,$

and finally

$\gamma>4\alpha\left(1-\sqrt{\alpha}\right).$

By Assumption 1, we can get
$(x_{0},y_{0},z_{0})=(x_{1}2^{(\beta_{2}-\beta_{1})n}-x_{3},x_{2}-x_{4},q_{2})$,
so we have $q_{2}=z_{0}$, and we calculate

$p_{2}=\frac{N_{2}}{q_{2}}.$

Next, we have

$2^{(\beta_{2}-\beta_{1})n}p_{1}=p_{2}+(x_{1}2^{(\beta_{2}-\beta_{1})n}-x_{3})+(x_{2}-x_{4})2^{(\beta_{2}+\gamma)n}=p_{2}+y_{0}+z_{0}2^{(\beta_{2}+\gamma)n}.$

Therefore, we can calculate $p_{1}$ and $q_{1}=\frac{N_{1}}{p_{1}}$. This
terminates the proof.∎

##  4 Experimental Results

We provide some experiments to verify Assumption 1 and the correctness of our
analysis. We provide an efficient open source implementation of our algorithm
for identifying ideal lattices in SageMath. The source code is available at:
https://github.com/fffmath/gifp.

The experiments were run on a computer configured with AMD Ryzen 5 2500U with
Radeon Vega Mobile Gfx (2.00 GHz). We selected the parameter $n=\log(N)$ using
gradients, validated our theory starting from small-scale experiments, and
continually increased the scale of our experiments. The results are presented
in Table 3:

n | $\alpha n$ | $\beta n$ | $\beta_{1}n$ | $\beta_{2}n$ | $\gamma n$ | $m$ | $\dim(\mathcal{L})$ | Time for LLL(s) | Time for Gröbner Basis(s)
---|---|---|---|---|---|---|---|---|---
200 | 20 | 40 | 20 | 30 | 140 | 6 | 28 | 1.8620 | 0.0033
500 | 50 | 100 | 50 | 75 | 350 | 6 | 28 | 3.1158 | 0.0043
500 | 50 | 150 | 50 | 75 | 300 | 6 | 28 | 4.23898 | 0.0048
1000 | 100 | 200 | 100 | 150 | 700 | 6 | 28 | 8.2277 | 0.0147
Table 3: Some experimental results for the GIFP.

As can be seen from Table 3, we chose various values of $n$, $\alpha n$,
$\beta n$, $\beta_{1}n$, $\beta_{2}n$ and $\gamma n$ to investigate the
behavior of our proposed algorithm. For each set of parameters, we recorded
the time taken by the LLL algorithm and Gröbner basis algorithm to solve the
Generalized Integer Factorization Problem (GIFP).

It is important to note that our paper introduces a new variable, ’w’, to
eliminate some ’z’. Introducing multiple variables may intuitively make it
more challenging to satisfy Assumption 1. However, in practice, it is not
necessary to satisfy Assumption 1 to find the desired ’p’ and ’q’.

For example, we usually yield $yz-C=0$ for some constant $C$. Then we can
calculate $z_{0}$ by $z_{0}=q_{2}=\gcd(y_{0}z_{0},N_{2})=\gcd(C,N_{2})$.

At the same time, if we abandon the introduction of ’w’, the corresponding
bound changes from $\gamma>4a(1-\sqrt{\alpha})$ to
$\gamma>2a(2-\sqrt{\alpha})$. Even with only three variables in this case, we
can still find ’p’ and ’q’ without satisfying Assumption 1.

As the size of the problem increases, the computation time for LLL and Gröbner
basis algorithms also increases. Nevertheless, our algorithm’s time complexity
grows moderately compared to the problem size. Therefore, we can conclude that
our algorithm is suitable for practical applications in the Generalized
Integer Factorization Problem (GIFP).

Besides the Generalized Implicit Factoring Problem, we also conducted
experiments on a special case, called the least-most significant bits case
(LMSBs). This case is characterized by $\beta_{1}=0$ and $\beta_{2}=\beta$.
The results of these experiments are outlined below.

n | $\alpha n$ | $\beta n$ | $\gamma n$ | $m$ | $\dim(\mathcal{L})$ | Time for LLL(s) | Time for Gröbner Basis(s)
---|---|---|---|---|---|---|---
256 | 25 | 75 | 156 | 5 | 21 | 1.3068 | 0.0029
256 | 25 | 75 | 156 | 5 | 21 | 1.2325 | 0.0023
256 | 25 | 75 | 156 | 6 | 21 | 1.2931 | 0.0023
512 | 50 | 150 | 212 | 6 | 28 | 2.0612 | 0.0028
512 | 50 | 150 | 212 | 6 | 28 | 2.4889 | 0.0086
512 | 50 | 150 | 212 | 6 | 28 | 2.0193 | 0.0022
Table 4: Some experimental results for the LMSBs case.

##  5 Conclusion and Open Problem

In this paper, we considered the Generalized Implicit Factoring Problem
(GIFP), where the shared bits are not necessarily required to be located at
the same positions. We proposed a lattice-based algorithm that can efficiently
factor two RSA moduli, $N_{1}=p_{1}q_{1}$ and $N_{2}=p_{2}q_{2}$, in
polynomial time, when the primes share a sufficient number of bits.

Our analysis shows that if $p_{1}$ and $p_{2}$ share $\gamma
n>4\alpha\left(1-\sqrt{\alpha}\right)n$ consecutive bits, not necessarily at
the same positions, then $N_{1}$ and $N_{2}$ can be factored in polynomial
time. However, this bound is valid when $p_{i}$ and $q_{i}$, $i=1,2$, are not
assumed to have the same bit length, i.e., $N_{1}$ and $N_{2}$ are unbalanced
moduli [16].

So our work raises an open question on improving the bound
$4\alpha\left(1-\sqrt{\alpha}\right)$, which would lead to better bounds for
specific cases such as sharing some middle bits. It is known that the unshared
bits in the Most Significant Bits (MSBs) or the Least Significant Bits (LSBs)
are continuous, and only one variable is required when using variables to
represent the unshared bits. This makes the MSBs or LSBs case easier to solve
than the generalized case and achieves a better bound of
$2\alpha\left(1-\alpha\right)$. However, the bound of the MSBs is not linear
with the bound of the GIFP, which is unnatural. We hope that the gap between
the bounds of the MSBs or LSBs and the GIFP case can be reduced.

## Acknowledgement

The authors would like to thank the reviewers of SAC 2023 for their helpful
comments and suggestions. Yansong Feng and Yanbin Pan were supported in part
by National Key Research and Development Project (No. 2018YFA0704705),
National Natural Science Foundation of China (No. 62032009, 12226006) and
Innovation Program for Quantum Science and Technology under Grant
2021ZD0302902.

## References

  * [1] Ajtai, M.: The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract). In: Symposium on the Theory of Computing (1998)
  * [2] Bauer, A., Jaulmes, É., Lomné, V., Prouff, E., Roche, T.: Side-channel attack against RSA key generation algorithms. In: Batina, L., Robshaw, M. (eds.) Cryptographic Hardware and Embedded Systems - CHES 2014 \- 16th International Workshop, Busan, South Korea, September 23-26, 2014. Proceedings. Lecture Notes in Computer Science, vol. 8731, pp. 223–241. Springer (2014). https://doi.org/10.1007/978-3-662-44709-3_13, https://doi.org/10.1007/978-3-662-44709-3_13
  * [3] Bernstein, D.J., Chang, Y., Cheng, C., Chou, L., Heninger, N., Lange, T., van Someren, N.: Factoring RSA keys from certified smart cards: Coppersmith in the wild. In: Sako, K., Sarkar, P. (eds.) Advances in Cryptology - ASIACRYPT 2013 - 19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, December 1-5, 2013, Proceedings, Part II. Lecture Notes in Computer Science, vol. 8270, pp. 341–360. Springer (2013). https://doi.org/10.1007/978-3-642-42045-0_18, https://doi.org/10.1007/978-3-642-42045-0_18
  * [4] Boneh, D., Durfee, G.: Cryptanalysis of RSA with private key _d_ less than _N_ ${}^{\mbox{0.292}}$. In: Stern, J. (ed.) Advances in Cryptology - EUROCRYPT ’99, International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, May 2-6, 1999, Proceeding. Lecture Notes in Computer Science, vol. 1592, pp. 1–11. Springer (1999). https://doi.org/10.1007/3-540-48910-X_1, https://doi.org/10.1007/3-540-48910-X_1
  * [5] Brumley, D., Boneh, D.: Remote timing attacks are practical. In: Proceedings of the 12th USENIX Security Symposium, Washington, D.C., USA, August 4-8, 2003\. USENIX Association (2003), https://www.usenix.org/conference/12th-usenix-security-symposium/remote-timing-attacks-are-practical
  * [6] Carmon, E., Seifert, J., Wool, A.: Photonic side channel attacks against RSA. In: 2017 IEEE International Symposium on Hardware Oriented Security and Trust, HOST 2017, McLean, VA, USA, May 1-5, 2017. pp. 74–78. IEEE Computer Society (2017). https://doi.org/10.1109/HST.2017.7951801, https://doi.org/10.1109/HST.2017.7951801
  * [7] Coppersmith, D.: Finding a small root of a univariate modular equation. In: Maurer, U.M. (ed.) Advances in Cryptology - EUROCRYPT ’96, International Conference on the Theory and Application of Cryptographic Techniques, Saragossa, Spain, May 12-16, 1996, Proceeding. Lecture Notes in Computer Science, vol. 1070, pp. 155–165. Springer (1996). https://doi.org/10.1007/3-540-68339-9_14, https://doi.org/10.1007/3-540-68339-9_14
  * [8] Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptol. 10(4), 233–260 (1997). https://doi.org/10.1007/s001459900030, https://doi.org/10.1007/s001459900030
  * [9] Faugère, J., Marinier, R., Renault, G.: Implicit factoring with shared most significant and middle bits. In: Nguyen, P.Q., Pointcheval, D. (eds.) Public Key Cryptography - PKC 2010, 13th International Conference on Practice and Theory in Public Key Cryptography, Paris, France, May 26-28, 2010\. Proceedings. Lecture Notes in Computer Science, vol. 6056, pp. 70–87. Springer (2010). https://doi.org/10.1007/978-3-642-13013-7_5, https://doi.org/10.1007/978-3-642-13013-7_5
  * [10] Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley Longman Publishing Co., Inc., USA, 2nd edn. (1994)
  * [11] Howgrave-Graham, N.: Finding small roots of univariate modular equations revisited. In: IMA International Conference on Cryptography and Coding. pp. 131–142. Springer (1997)
  * [12] Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261, 515–534 (1982)
  * [13] Lu, Y., Peng, L., Zhang, R., Hu, L., Lin, D.: Towards optimal bounds for implicit factorization problem. In: International Conference on Selected Areas in Cryptography. pp. 462–476. Springer (2016)
  * [14] May, A.: New RSA vulnerabilities using lattice reduction methods. Ph.D. thesis, University of Paderborn (2003), http://ubdata.uni-paderborn.de/ediss/17/2003/may/disserta.pdf
  * [15] May, A., Ritzenhofen, M.: Implicit factoring: On polynomial time factoring given only an implicit hint. In: Jarecki, S., Tsudik, G. (eds.) Public Key Cryptography - PKC 2009, 12th International Conference on Practice and Theory in Public Key Cryptography, Irvine, CA, USA, March 18-20, 2009. Proceedings. Lecture Notes in Computer Science, vol. 5443, pp. 1–14. Springer (2009). https://doi.org/10.1007/978-3-642-00468-1_1, https://doi.org/10.1007/978-3-642-00468-1_1
  * [16] Nitaj, A., Ariffin, M.R.K.: Implicit factorization of unbalanced RSA moduli. IACR Cryptol. ePrint Arch. p. 548 (2014), http://eprint.iacr.org/2014/548
  * [17] Peng, L., Hu, L., Lu, Y., Huang, Z., Xu, J.: Implicit factorization of RSA moduli revisited (short paper). In: Tanaka, K., Suga, Y. (eds.) Advances in Information and Computer Security - 10th International Workshop on Security, IWSEC 2015, Nara, Japan, August 26-28, 2015, Proceedings. Lecture Notes in Computer Science, vol. 9241, pp. 67–76. Springer (2015). https://doi.org/10.1007/978-3-319-22425-1_5, https://doi.org/10.1007/978-3-319-22425-1_5
  * [18] Rivest, R.L., Shamir, A., Adleman, L.M.: Cryptographic communications system and method (Sep 20 1983), uS Patent 4,405,829
  * [19] Sarkar, S., Maitra, S.: Further results on implicit factoring in polynomial time. Adv. Math. Commun. 3(2), 205–217 (2009). https://doi.org/10.3934/amc.2009.3.205, https://doi.org/10.3934/amc.2009.3.205
  * [20] Sarkar, S., Maitra, S.: Some applications of lattice based root finding techniques. Adv. Math. Commun. 4(4), 519–531 (2010). https://doi.org/10.3934/amc.2010.4.519, https://doi.org/10.3934/amc.2010.4.519
  * [21] Sarkar, S., Maitra, S.: Approximate integer common divisor problem relates to implicit factorization. IEEE Trans. Inf. Theory 57(6), 4002–4013 (2011). https://doi.org/10.1109/TIT.2011.2137270, https://doi.org/10.1109/TIT.2011.2137270
  * [22] Wang, S., Qu, L., Li, C., Fu, S.: A better bound for implicit factorization problem with shared middle bits. Sci. China Inf. Sci. 61(3), 032109:1–032109:10 (2018). https://doi.org/10.1007/s11432-017-9176-5, https://doi.org/10.1007/s11432-017-9176-5

##  Appendix 0.A Details of calculations in Section 3.2

In this appendix, we present the details of calculations for the quantities
$e_{X}$, $e_{Y}$, $e_{Z}$, $e_{W}$, $e_{N}$, and $e_{M}$ used in Section 3.2.
We begin by a lemma that will be easily proven by induction. This lemma is
well-known and can be found in many textbooks and references on combinatorics
and discrete mathematics, such as Table 174 on page 174 in [10].

###### Lemma 1

The equation $\sum_{i=0}^{n}\binom{i}{2}=\binom{n+1}{3}$ holds for any integer
$n$.

Moving on, we provide the calculations for $e_{X}$ as:

$\displaystyle e_{X}$
$\displaystyle=\sum_{i=0}^{m}\sum_{j=0}^{m-i}j=\sum_{i=0}^{m}\binom{m-i+1}{2}=\sum_{i=0}^{m}\binom{i+1}{2}$
$\displaystyle=\binom{m+2}{3}=\frac{1}{6}m(m+1)(m+2).$

The calculation of $e_{Y}$ is the same as $e_{X}$.

Next, we provide the calculation for $e_{Z}$:

$\displaystyle e_{Z}$
$\displaystyle=\sum_{i=0}^{m}\sum_{j=0}^{m-i}(i+j-\min(s,i+j))$
$\displaystyle=\sum_{i=0}^{m}\sum_{j=0}^{m-i}\max\\{i+j-s,0\\}$
$\displaystyle=\sum_{t=s+1}^{m}\sum_{j=0}^{t}(t-s)\quad\text{(Let
}t=i+j\text{)}$ $\displaystyle=\sum_{t=s+1}^{m}(t-s)(t+1)$
$\displaystyle=\sum_{t=0}^{m}(t-s)(t+1)-\sum_{t=0}^{s}(t-s)(t+1)$
$\displaystyle=\sum_{t=0}^{m}t(t+1)-\sum_{t=0}^{m}s(t+1)-\sum_{t=0}^{s}t(t+1)+\sum_{t=0}^{s}s(t+1)$
$\displaystyle=2\sum_{t=0}^{m}\binom{t+1}{2}-s\sum_{t=0}^{m}(t+1)-2\sum_{t=0}^{s}\binom{t+1}{2}+s\sum_{t=0}^{s}(t+1)$
$\displaystyle=2\binom{m+2}{3}-s\binom{m+2}{2}+\frac{1}{6}\binom{s+2}{3}$
$\displaystyle=\frac{1}{3}m(m+1)(m+2)+\frac{1}{6}s(s+1)(s+2)-\frac{1}{2}s(m+1)(m+2).$

Then, we provide the calculation for $e_{W}$:

$\displaystyle e_{W}$
$\displaystyle=\sum_{i=0}^{m}\sum_{j=0}^{m-i}(s-\min(s,i+j))$
$\displaystyle=\sum_{i=0}^{s}\sum_{j=0}^{s-i}(s-i-j)$
$\displaystyle=\sum_{i=0}^{s}\sum_{j=0}^{s-i}s-\sum_{i=0}^{s}\sum_{j=0}^{s-i}i-\sum_{i=0}^{s}\sum_{j=0}^{s-i}j$
$\displaystyle=\frac{1}{2}s(s+1)(s+2)-\frac{1}{6}s(s+1)(s+2)-\frac{1}{6}s(s+1)(s+2)$
$\displaystyle=\frac{1}{6}s(s+1)(s+2).$

Furthermore, we provide the calculation for $e_{N}$:

$\displaystyle e_{N}$
$\displaystyle=\sum_{i=0}^{t}\sum_{j=0}^{m-i}(t-i)=\sum_{i=0}^{t}(t-i)(m-i+1)=\sum_{i=0}^{t}(t-i)(m+2-i-1)$
$\displaystyle=(m+2)\sum_{i=0}^{t}(t-i)-\sum_{i=0}^{t}(t-i)(i+1)=(m+2)\binom{t+1}{2}-\sum_{i=0}^{t}t(i+1)+\sum_{i=0}^{t}i(i+1)$
$\displaystyle=(m+2)\binom{t+1}{2}-t\binom{t+2}{2}+\sum_{i=0}^{t}2\binom{i+1}{2}=(m+2)\binom{t+1}{2}-t\binom{t+2}{2}+2\binom{t+2}{3}$
$\displaystyle=\frac{1}{6}t(t+1)(3m-t+4).$

Finally, we provide the calculation for $e_{M}$:

$\displaystyle e_{M}$
$\displaystyle=\sum_{i=0}^{m}\sum_{j=0}^{m-i}(m-i)=\sum_{i=0}^{m}(m-i+1)(m-i)=\sum_{i=0}^{m}2\binom{m-i+1}{2}$
$\displaystyle=\sum_{i=0}^{m}2\binom{i+1}{2}=2\binom{m+2}{3}=\frac{1}{3}m(m+1)(m+2).$


# An infinite family of antiprimitive cyclic codes supporting Steiner systems
$S(3,8,7^{m}+1)$ ††thanks: The research of C. Xiang was supported by the Basic
Research Project of Science and Technology Plan of Guangzhou city of China
under grant number 202102020888 and the National Natural Science Foundation of
China under grant number 12171162. The research of C. Tang was supported by
National Natural Science Foundation of China under grant number 11871058 and
China West Normal University (14E013, CXTD2014-4 and the Meritocracy Research
Funds).

Can Xiang , Chunming Tang and Qi Liu C. Xiang is with the College of
Mathematics and Informatics, South China Agricultural University, Guangzhou,
Guangdong 510642, China (email:cxiangcxiang@hotmail.com). C. Tang is with
School of Mathematics and Information, China West Normal University, Nanchong,
Sichuan 637002, China (email: tangchunmingmath@163.com).Q. Liu is with School
of Mathematics and Information, China West Normal University, Nanchong,
Sichuan 637002, China (email: liuqijichushuxue@163.com).

###### Abstract

Coding theory and combinatorial $t$-designs have close connections and
interesting interplay. One of the major approaches to the construction of
combinatorial t-designs is the employment of error-correcting codes. As we all
known, some $t$-designs have been constructed with this approach by using
certain linear codes in recent years. However, only a few infinite families of
cyclic codes holding an infinite family of $3$-designs are reported in the
literature. The objective of this paper is to study an infinite family of
cyclic codes and determine their parameters. By the parameters of these codes
and their dual, some infinite family of $3$-designs are presented and their
parameters are also explicitly determined. In particular, the complements of
the supports of the minimum weight codewords in the studied cyclic code form a
Steiner system. Furthermore, we show that the infinite family of cyclic codes
admit $3$-transitive automorphism groups.

###### Index Terms:

Linear codes, cyclic codes, combinatorial designs, automorphism groups,
Steiner system

##  I Introduction

Let ${\mathrm{GF}}(q)$ be a finite field with $q$ elements, where $q=p^{m}$
with $m$ being a positive integer and $p$ being an prime number. An
$[v,\,k,\,d]$ linear code ${\mathcal{C}}$ over ${\mathrm{GF}}(q)$ is a
$k$-dimensional subspace of ${\mathrm{GF}}(q)^{v}$ with minimum (Hamming)
distance $d$. An $[v,\,k,\,d]$ linear code ${\mathcal{C}}$ is said to be
cyclic if $(c_{0},c_{1},\cdots,c_{v-1})\in{\mathcal{C}}$ implies
$(c_{v-1},c_{0},c_{1},\cdots,c_{v-2})\in{\mathcal{C}}$.

Let ${\mathcal{C}}$ be an $[v,k,d]$ cyclic code over ${\mathrm{GF}}(q)$. If
$v=q^{m}-1$ (resp. $v=q^{m}+1$), the cyclic code ${\mathcal{C}}$ is called
primitive (resp. antiprimitive). If we identify a vector
$(c_{0},c_{1},\cdots,c_{v-1})\in{\mathrm{GF}}(q)^{v}$ with the following
polynomial

$\sum_{i=0}^{v-1}c_{i}x^{i}\in{\mathrm{GF}}(q)[x]/(x^{v}-1),$

then any cyclic code ${\mathcal{C}}$ of length $v$ over ${\mathrm{GF}}(q)$ is
an ideal of the quotient ring ${\mathrm{GF}}(q)[x]/(x^{v}-1)$. It is notice
that the ring ${\mathrm{GF}}(q)[x]/(x^{v}-1)$ is a principal ideal ring. Thus,
for any cyclic code ${\mathcal{C}}$ of length $v$ over ${\mathrm{GF}}(q)$,
there exists an unique monic divisor $g(x)$ of $x^{v}-1$ of the smallest
degree such that ${\mathcal{C}}=\langle g(x)\rangle$ . This polynomial $g(x)$
is called the generator polynomial, and $h(x)=(x^{v}-1)/g(x)$ is called the
check polynomial of ${\mathcal{C}}$. It is obvious that $k=v-deg(g(x))$ and
$\\{g(x),xg(x),\cdots,x^{k-1}g(x)\\}$ is a basis of ${\mathcal{C}}$. It is
well known that a cyclic code is a special linear code. Although the error
correcting capability of cyclic codes may not be as good as some other linear
codes in general, cyclic codes have wide applications in storage and
communication systems as they have efficient encoding and decoding algorithms
[1, 2, 3]. Thus, cyclic codes have been attracted much attention in coding
theory and a lot of progress has been made (see, for example, [4, 5, 6, 8, 9,
26, 27]).

It is known that linear codes and $t$-designs are closely related. A
$t$-design can be induced to a linear code (see, for example, [12, 13]).
Meanwhile, a linear code ${\mathcal{C}}$ may induce a $t$-design under certain
conditions. As far as we know, a lot of $2$-designs and $3$-designs have been
constructed from some special linear codes (see, for example, [10, 14, 15, 19,
21]). Recently, an infinity family of linear codes holding $4$-designs was
settled by Tang and Ding in [23]. It remains open if there is an infinite
family of linear codes holding $5$-designs. In fact, only a few infinite
families of cyclic codes holding an infinite family of $3$-designs are
reported in the literature. Motivated by this fact, we will consider a class
of cyclic codes

$\displaystyle{\mathcal{C}}_{m}=\\{({\mathrm{Tr}}(au^{4}+bu^{3}))_{u\in
U_{q+1}}:a,b\in{\mathrm{GF}}(q^{2})\\}$ (1)

over ${\mathrm{GF}}(q)$ and its dual, where $q=7^{m}$ with $m\geq 2$ being a
integer, ${\mathrm{Tr}}$ is the trace function from ${\mathrm{GF}}(q^{2})$ to
${\mathrm{GF}}(q)$ and $U_{q+1}$ is the set of all $(q+1)$-th roots of unity
in ${\mathrm{GF}}(q^{2})$, and prove that these codes hold $3$-designs.
Specifically, the cyclic code ${\mathcal{C}}_{m}$ and its dual
${\mathcal{C}}_{m}^{\perp}$ admit $3$-transitive automorphism groups and the
complement of the supports of the minimum weight codewords in
${\mathcal{C}}_{m}$ forms a steiner system $S(3,8,7^{m}+1)$.

The remainder of this paper is arranged as follows. Section II introduces some
notation and basics of linear codes and combinatorial $t$-designs. Section III
determines the parameters of the cyclic code ${\mathcal{C}}_{m}$ and its dual,
and induces some infinite families of $3$-designs. Section IV concludes this
paper.

##  II Preliminaries

As a special linear code, cyclic codes have all properties of linear codes. In
order to study cyclic codes in this paper, we need briefly introduce some
known results on linear codes and combinatorial t-designs in this section,
which will be used later. For convenience, we begin this section by fixing the
following notations unless otherwise stated in this paper.

  * •

$p$ is a prime and $q=p^{m}$ with $m$ being a positive integer.

  * •

${\mathrm{GF}}(q)$ is a finite field with $q$ elements and
${\mathrm{GF}}(q)^{*}={\mathrm{GF}}(q)\setminus\\{0\\}$.

  * •

${\mathrm{Tr}}$ is the trace function from ${\mathrm{GF}}(q^{2})$ to
${\mathrm{GF}}(q)$.

  * •

$U_{q+1}$ is the set of all $(q+1)$-th roots of unity in
${\mathrm{GF}}(q^{2})$.

  * •

$\binom{S}{k}$ is defined as the set consisting of all $k$-subsets of the set
$S$ if $S$ is a set, and the binomial coefficient otherwise.

  * •

${\mathrm{PGL}}(2,q)$ is defined as the group of invertible $2\times 2$
matrices with entries in ${\mathrm{GF}}(q)$, modulo the scalar matrices
$\begin{bmatrix}a&0\\\ 0&a\end{bmatrix}$, where $a\in{\mathrm{GF}}(q)^{*}$.

###  II-A Weight enumerators of linear codes

Let ${\mathcal{C}}$ be a $[v,\,k,\,d]$ linear code over ${\mathrm{GF}}(q)$.
Let $A_{i}$ denote the number of codewords with Hamming weight $i$ in a code
${\mathcal{C}}$ for all $0\leq i\leq v$. The weight enumerator of
${\mathcal{C}}$ is defined by

$1+A_{1}z+A_{2}z^{2}+\cdots+A_{v}z^{v}.$

The sequence $(1,A_{1},\ldots,A_{v})$ is called the weight distribution of
${\mathcal{C}}$. A code ${\mathcal{C}}$ is said to be a $t$-weight code if the
number of nonzero $A_{i}$ in the sequence $(A_{1},A_{2},\cdots,A_{v})$ is
equal to $t$. A code ${\mathcal{C}}$ is said to be optimal if its parameters
meet certain bounds on linear codes. Denote the dual of ${\mathcal{C}}$ by
${\mathcal{C}}^{\perp}$ , the minimum distance of ${\mathcal{C}}^{\perp}$ by
$d^{\perp}$ and the weight distribution of ${\mathcal{C}}^{\perp}$ by
$(A_{0}^{\perp},A_{1}^{\perp},\cdots,A_{v}^{\perp})$. In order to determine
the weight enumerator of ${\mathcal{C}}$, we will need the _Pless power
moments_ [20]. The first four Pless power moments identities are given by

$\displaystyle\sum_{i=0}^{\nu}A_{i}=q^{k},$
$\displaystyle\sum_{i=0}^{\nu}i\cdot A_{i}=q^{k-1}(qv-v-A_{1}^{\perp}),$
$\displaystyle\sum_{i=0}^{\nu}i^{2}\cdot
A_{i}=q^{k-2}\left[(q-1)v(qv-v+1)-(2qv-q-2v+2)A_{1}^{\perp}+2A_{2}^{\perp}\right],$
$\displaystyle\sum_{i=0}^{\nu}i^{3}\cdot
A_{i}=q^{k-3}((q-1)v(q^{2}v^{2}-2qv^{2}+3qv-q+v^{2}-3v+2)$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
-(3q^{2}v^{2}-3q^{2}v-6qv^{2}+12qv+q^{2}-6q+3v^{2}-9v+6)A_{1}^{\perp}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ +6(qv-
q-v+2)A_{2}^{\perp}-6A_{3}^{\perp}).$ (2)

###  II-B Automorphism groups of linear codes

Let ${\mathcal{C}}$ be a $[v,\,k,\,d]$ linear code over ${\mathrm{GF}}(q)$. We
denote the set of coordinate positions of codewords of ${\mathcal{C}}$ by
${\mathcal{P}}$. Then every codeword ${\mathbf{c}}$ of ${\mathcal{C}}$ can be
written as ${\mathbf{c}}=(c_{x})_{x\in{\mathcal{P}}}$. The set of coordinate
permutations $g$ that map a code ${\mathcal{C}}$ to itself forms a group,
i.e.,

$\displaystyle\\{g|\leavevmode\nobreak\
g(c_{x})_{x\in{\mathcal{P}}}=(c_{g^{-1}(x)})_{x\in{\mathcal{P}}}\in{\mathcal{C}}\text{
for all }(c_{x})_{x\in{\mathcal{P}}}\in{\mathcal{C}}\\}$

which called the permutation automorphism group of ${\mathcal{C}}$ and denoted
by $\mathrm{PAut}({\mathcal{C}})$ . We denote the symmetric group on the set
${\mathcal{P}}$ by $\mathrm{Sym}({\mathcal{P}})$. It is clear that
$\mathrm{PAut}({\mathcal{C}})$ is the subgroup of
$\mathrm{Sym}({\mathcal{P}})$ which keeps its invariance of the code $C$.
Define a subgroup of
$({\mathrm{GF}}(q)^{*})^{v}\rtimes\mathrm{Sym}({\mathcal{P}})$ as follows:

$\displaystyle\\{\left((a_{x})_{x\in{\mathcal{P}}};g\right)|\leavevmode\nobreak\
\left((a_{x})_{x\in{\mathcal{P}}};g\right)(c_{x})_{x\in{\mathcal{P}}}=(a_{x}c_{g^{-1}(x)})_{x\in{\mathcal{P}}}\in{\mathcal{C}}\text{
for all }(c_{x})_{x\in{\mathcal{P}}}\in{\mathcal{C}}\\}$ (3)

where $\left((a_{x})_{x\in{\mathcal{P}}};g\right)$ is a map which maps the
code ${\mathcal{C}}$ to itself. This subgroup is called the monomial
automorphism group of ${\mathcal{C}}$ and denoted by
$\mathrm{MAut}({\mathcal{C}})$. Let $\mathrm{Gal}({\mathrm{GF}}(q))$ be the
Galois group of ${\mathrm{GF}}(q)$ over its prime field. Then the automorphism
group $\mathrm{Aut}({\mathcal{C}})$ of ${\mathcal{C}}$ is the subgroup of
$({\mathrm{GF}}(q)^{*})^{v}\rtimes\left(\mathrm{Sym}({\mathcal{P}})\times\mathrm{Gal}({\mathrm{GF}}(q))\right)$
as follows:

$\displaystyle\\{\left((a_{x})_{x\in{\mathcal{P}}};g,\gamma\right)|:\leavevmode\nobreak\
\left((a_{x})_{x\in{\mathcal{P}}};g,\gamma\right)(c_{x})_{x\in{\mathcal{P}}}=(a_{x}\gamma(c_{g^{-1}(x)}))_{x\in{\mathcal{P}}}\in{\mathcal{C}}\text{
for all }(c_{x})_{x\in{\mathcal{P}}}\in{\mathcal{C}}\\}$

where $\left((a_{x})_{x\in{\mathcal{P}}};g,\gamma\right)$ is a map which maps
the code ${\mathcal{C}}$ to itself. It is notice that
$\mathrm{PAut}({\mathcal{C}})\subseteq\mathrm{MAut}({\mathcal{C}})\subseteq\mathrm{Aut}({\mathcal{C}})$.
When $q$ is a prime,
$\mathrm{MAut}({\mathcal{C}})=\mathrm{Aut}({\mathcal{C}})$. Specifically,
$\mathrm{PAut}({\mathcal{C}})=\mathrm{MAut}({\mathcal{C}})=\mathrm{Aut}({\mathcal{C}})$
if ${\mathcal{C}}$ is binary code.

We say that ${\mathrm{Aut}}({\mathcal{C}})$ is $t$-homogeneous (resp.
$t$-transitive) if for every pair of $t$-element sets of coordinates (resp.
$t$-element ordered sets of coordinates), there is an element
$\left((a_{x})_{x\in{\mathcal{P}}};g,\gamma\right)\in{\mathrm{Aut}}({\mathcal{C}})$
such that its permutation part $g$ sends the first set to the second set.

###  II-C Combinatorial t-designs and some related results

Let $k$, $t$ and $v$ be positive integers with $1\leq t\leq k\leq v$. Let
${\mathcal{P}}$ be a set with $v$ elements and ${\mathcal{B}}$ be a set of
some $k$-subsets of ${\mathcal{P}}$. ${\mathcal{B}}$ is called the point set
and ${\mathcal{P}}$ is called the block set in general. The incidence
structure ${\mathbb{D}}=({\mathcal{P}},{\mathcal{B}})$ is called a
$t$-$(v,k,\lambda)$ design (or $t$-design) if every $t$-subset of
${\mathcal{P}}$ is contained in exactly $\lambda$ blocks of ${\mathcal{B}}$.
Let $\binom{{\mathcal{P}}}{k}$ denote the set consisting of all $k$-subsets of
the point set ${\mathcal{P}}$. Then the incidence structure
$({\mathcal{P}},\binom{{\mathcal{P}}}{k})$ is a $k$-$(v,k,1)$ design and is
called a _complete design_. The special incidence structure
$({\mathcal{P}},\emptyset)$ is called a $t$-$(v,k,0)$ trivial design for all
$t$ and $k$ . A combinatorial $t$-design is said to be simple if its block set
${\mathcal{B}}$ does not have a repeated block. When $t\geq 2$ and
$\lambda=1$, a $t$-$(v,k,\lambda)$ design is called a Steiner system and
denoted by $S(t,k,v)$. The parameters of a combinatorial $t$-$(v,k,\lambda)$
design must satisfy the following equation:

$\displaystyle b=\lambda\frac{\binom{v}{t}}{\binom{k}{t}}$ (4)

where $b$ is the cardinality of ${\mathcal{B}}$.

Linear codes and $t$-designs are closely related. A $t$-design
$\mathbb{D}=(\mathcal{P},\mathcal{B})$ can be used to construct a linear code
over GF($q$) for any $q$ as follows. Let
$\mathcal{P}=\\{q_{1},\dots,q_{\nu}\\}$,
${\mathcal{B}}=\\{B_{1},\dots,B_{b}\\}$. The incidence matrix
$M_{{\mathbb{D}}}:=[m_{ij}]$ of the design
${\mathbb{D}}=(\mathcal{P},\mathcal{B})$ is a $b\times v$ binary matrix whose
entry $m_{ij}=1$ if the point $q_{j}$ is on the block $B_{i}$ and $m_{ij}=0$
otherwise. The incidence matrix $M_{{\mathbb{D}}}$ can be viewed as a matrix
over ${\mathrm{GF}}(q)$ for any $q$. The _linear code_
$\mathsf{C}_{q}(\mathbb{D})$ over the prime field $\mathrm{GF}(q)$ of the
design $\mathbb{D}$ is defined to be the linear subspace of
${\mathrm{GF}}(q)^{v}$ spanned by the row vectors of the incidence matrix
$M_{{\mathbb{D}}}$. Linear codes $\mathsf{C}_{q}(\mathbb{D})$ of designs
$\mathbb{D}$ have been extensively investigated (see, for example, [13, 16,
17, 18]).

On the other hand, a linear code ${\mathcal{C}}$ may produce a $t$-design
which is formed by supports of codewords of a fixed Hamming weight in
${\mathcal{C}}$. Let $\mathcal{P}(\mathcal{C})=\\{0,1,2,\dots,\nu-1\\}$ be the
set of the coordinates of codewords in $\mathcal{C}$, where $\nu$ is the
length of the code $\mathcal{C}$. For a codeword
$\mathbf{c}=(c_{0},c_{1},\dots,c_{\nu-1})$ in $\mathcal{C}$, the _support_ of
$\mathbf{c}$ is defined by

$\displaystyle\mathrm{Supp}(\mathbf{c})=\\{i:c_{i}\neq
0,i\in\mathcal{P}(\mathcal{C})\\}.$

Let $\mathcal{B}_{w}(\mathcal{C})$ denote the set
$\\{\\{\mathrm{Supp}(\mathbf{c}):wt(\mathbf{c})=w\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ \mathbf{c}\in\mathcal{C}\\}\\}$, where
$\\{\\{\\}\\}$ is the multiset notation. For some special code $\mathcal{C}$,
the incidence structure
$\left(\mathcal{P}(\mathcal{C}),\mathcal{B}_{w}(\mathcal{C})\right)$ could be
a $t$-$(v,w,\lambda)$ design for some positive integer $t$ and $\lambda$. If
$\left(\mathcal{P}(\mathcal{C}),\mathcal{B}_{w}(\mathcal{C})\right)$ is a
$t$-design for all $w$ with $0\leq w\leq\nu$, we say that the code
$\mathcal{C}$ _supports $t$-designs_. By definition, such design
$\left(\mathcal{P}(\mathcal{C}),\mathcal{B}_{w}(\mathcal{C})\right)$ could
have some repeated blocks, or could be simple, or may be trivial. In this way,
many $t$-designs have been constructed from linear codes (see, for example,
[10, 10, 14, 15, 19, 21, 23]). A major way to construct combinatorial
$t$-designs with linear codes over finite fields is the use of linear codes
with $t$-transitive or $t$-homogeneous automorphism groups (see [10, Theorem
4.18]) and some combinatorial $t$-designs (see, for example, [7]) were
obtained by this way. Very recently, Liu et al.[28] obtained some
$3$-transitive automorphism groups from a class of BCH codes and derived some
combinatorial $3$-designs with this way. Another major way to construct
$t$-designs with linear codes is the use of the Assmus-Mattson Theorem (AM
Theorem for short) in [10, Theorem 4.14] and the generalized version of the AM
Theorem in [22], which was recently employed to construct a number of
$t$-designs (see, for example, [10, 24, 25]). The following theorem is a
generalized version of the AM Theorem, which was developed in [22] and will be
needed in this paper.

######  Theorem 1.

[22] Let $\mathcal{C}$ be a linear code over the finite field $\mathrm{GF}(q)$
with length $\nu$ and minimum distance $d$. Let $\mathcal{C}^{\perp}$ denote
the dual of $\mathcal{C}$ with minimum distance $d^{\perp}$. Let $s$ and $t$
be two positive integers such that $t<\min\\{d,d^{\perp}\\}$. Let $S$ be a
$s$-subset of the set $\\{d,d+1,d+2,\ldots,\nu-t\\}$. Suppose that
$\left(\mathcal{P}(\mathcal{C}),\mathcal{B}_{\ell}(\mathcal{C})\right)$ and
$\left(\mathcal{P}(\mathcal{C}^{\perp}),\mathcal{B}_{\ell^{\perp}}(\mathcal{C}^{\perp})\right)$
are $t$-designs for $\ell\in\\{d,d+1,d+2,\ldots,\nu-t\\}\setminus S$ and
$0\leq\ell^{\perp}\leq s+t-1$, respectively. Then the incidence structures
$\left(\mathcal{P}(\mathcal{C}),\mathcal{B}_{k}(\mathcal{C})\right)$ and
$\left(\mathcal{P}(\mathcal{C}^{\perp}),\mathcal{B}_{k}(\mathcal{C}^{\perp})\right)$
are $t$-designs for any $t\leq k\leq\nu$, and particularly,

  * •

the incidence structure
$\left(\mathcal{P}(\mathcal{C}),\mathcal{B}_{k}(\mathcal{C})\right)$ is a
simple $t$-design for all integers $k$ with $d\leq k\leq w$, where $w$ is
defined to be the largest integer such that $w\leq\nu$ and

$w-\left\lfloor\frac{w+q-2}{q-1}\right\rfloor<d;$

  * •

and the incidence structure
$\left(\mathcal{P}(\mathcal{C}^{\perp}),\mathcal{B}_{k}(\mathcal{C}^{\perp})\right)$
is a simple $t$-design for all integers $k$ with $d\leq k\leq w^{\perp}$,
where $w^{\perp}$ is defined to be the largest integer such that
$w^{\perp}\leq\nu$ and

$w^{\perp}-\left\lfloor\frac{w^{\perp}+q-2}{q-1}\right\rfloor<d^{\perp}.$

##  III An infinite family of cyclic codes supporting $3$-designs

In this section, our task is to establish the parameters of the cyclic code
${\mathcal{C}}_{m}$ defined by (1) and its dual, and prove that these codes
hold $3$-designs and satisfy $3$-transitive automorphism groups. To this end,
we shall prove a few more auxiliary results before proving the main results
(see Theorems 6, 8 and 14) of this paper.

###  III-A Some auxiliary results

In order to determine the minimum distance of the dual code
${\mathcal{C}}_{m}^{\perp}$ of ${\mathcal{C}}_{m}$, we need the results in the
following three lemmas.

######  Lemma 2.

Let symbols and notation be the same as before. Let $m\geq 2$ be a positive
integer and $q=7^{m}$. For any $\\{x,y,z\\}\in\binom{U_{q+1}}{3}$, we have the
following results.

  1. 1.

$x+y-2z\neq 0$;

  2. 2.

$x+2y-3z\neq 0$;

  3. 3.

$x+3y-4z\neq 0$;

  4. 4.

$x+4y-5z\neq 0$;

  5. 5.

$x+5y-6z\neq 0$;.

###### Proof.

We only give the proof of the first conclusion. The proofs of the other four
conclusions are similar to that of the first conclusion and thus omitted.

Assume that $x+y-2z=0$, then

$(x+y-2z)^{q}=\frac{1}{x}+\frac{1}{y}-\frac{2}{z}=\frac{1}{x}+\frac{1}{y}-\frac{4}{2z}=0.$

It follows from $x+y=2z$ that

$\frac{1}{x}+\frac{1}{y}-\frac{4}{x+y}=0,$

which means that $(x-y)^{2}=0$. This is contrary to our assumption that
$x,y,z$ are pairwise distinct. Thus, $x+y-2z\neq 0$. This completes the proof.
∎

######  Lemma 3.

Let symbols and notation be the same as before. Let $q=7^{m}$ with $m\geq 2$
being a positive integer and $\\{x,y,z\\}\in\binom{U_{q+1}}{3}$. Define

$\displaystyle\bar{M}(x,y,z)=\left[\begin{array}[]{lll}1&1&1\\\ x&y&z\\\
x^{7}&y^{7}&z^{7}\end{array}\right].$ (8)

Then

$|\bar{M}(x,y,z)|=(x-y)(x-z)(y-z)(x+y-2z)(x+2y-3z)(x+3y-4z)(x+4y-5z)(x+5y-6z)\neq
0.$

###### Proof.

The conclusion follows from Lemma 2. ∎

######  Lemma 4.

Let $m\geq 2$ be a positive integer, $q=7^{m}$ and
$(x,y,z,w)\in{\mathrm{GF}}(q^{2})^{4}$. Define

$\displaystyle M(x,y,z,w)=\left[\begin{array}[]{llll}1&1&1&1\\\ x&y&z&w\\\
x^{7}&y^{7}&z^{7}&w^{7}\\\ x^{8}&y^{8}&z^{8}&w^{8}\end{array}\right].$ (13)

Then we have the following results.

  1. 1.

$|M(x,y,z,w)|=(x-y)(x-z)(x-w)(y-z)(y-w)(z-w)\cdot\prod_{i=1}^{5}(xy+zw+i(xz+wy)+(6-i)(xw+yz))$.

  2. 2.

For any $\\{x,y,z\\}\in\binom{U_{q+1}}{3}$, there exists five pairwise
distinct $w\in U_{q+1}\setminus\\{x,y,z\\}$ such that $|M(x,y,z,w)|=0$, i.e.,
$\prod_{i=1}^{5}(xy+zw+i(xz+wy)+(6-i)(xw+yz))=0$.

###### Proof.

1) It is easy to prove the first conclusion and we omit its proof.

2) By definitions and Lemma 2, $z+iy+(6-i)x\neq 0$ for any
$i\in\\{1,2,3,4,5\\}$. Denote

$w_{i}=\frac{(i-6)yz-xy-ixz}{z+iy+(6-i)x}$

, where $i\in\\{1,2,3,4,5\\}$. Note that

$w_{i}^{q}=\frac{(i-6)y^{q}z^{q}-x^{q}y^{q}-ix^{q}z^{q}}{z^{q}+iy^{q}+(6-i)x^{q}}=\frac{((i-6)y^{q}z^{q}-x^{q}y^{q}-ix^{q}z^{q})\cdot
xyz}{(z^{q}+iy^{q}+(6-i)x^{q}))\cdot xyz}=1/w_{i}.$

Thus, $w_{i}^{q+1}=1$. This means that $w_{i}\in U_{q+1}$ for any
$i\in\\{1,2,3,4,5\\}$.

Since $\\{x,y,z\\}\in\binom{U_{q+1}}{3}$, from $|M(x,y,z,w)|=0$ and the first
conclusion 1) we have

$\prod_{i=1}^{5}(xy+zw+i(xz+wy)+(6-i)(xw+yz))=0.$

This means that $w=w_{i}$ with $i\in\\{1,2,3,4,5\\}$.

Next we will prove that $w_{i}\neq x,y,z$ for each $i\in\\{1,2,3,4,5\\}$.

Let $i\in\\{1,2,3,4,5\\}$. Suppose that $w_{i}=x$, then

$\frac{(i-6)yz-xy-ixz}{z+iy+(6-i)x}=x,$

which yields

$(i-6)x^{2}-(i+1)(y+z)x+(i-6)yz=0,$

which is the same as

$(i-6)(x-y)(x-z)=0.$

This means that $x=y$ or $x=z$, which is contrary to our assumption that
$x,y,z$ are pairwise distinct in $U_{q+1}$. Thus, $w_{i}\neq x$. Due to
symmetry, $w_{i}\neq y$ and $w_{i}\neq z$. Therefore, $w_{i}\neq x,y,z$ for
each $i\in\\{1,2,3,4,5\\}$.

We now prove that $w_{i}\neq w_{j}$ when $i\neq j$ and
$i,j\in\\{1,2,3,4,5\\}$.

Let $i,j\in\\{1,2,3,4,5\\}$ and $i\neq j$. Suppose that $w_{i}=w_{j}$, then

$\frac{(i-6)yz-xy-ixz}{z+iy+(6-i)x}=\frac{(j-6)yz-xy-jxz}{z+jy+(6-j)x},$

which yields

$(i-j)(x-y)(x-z)(y-z)=0.$

It then follows from $i\neq j$ that $x=y$ or $x=z$ or $y=z$, which is contrary
to our assumption that $x,y,z$ are pairwise distinct in $U_{q+1}$. Thus,
$w_{1},w_{2},w_{3},w_{4},w_{5}$ are pairwise distinct. This completes the
proof. ∎

The following result plays an important role in calculating the weight
distributions of the cyclic code ${\mathcal{C}}_{m}$, which is described in
the next lemma.

######  Lemma 5.

Let symbols and notation be the same as before. Let $m\geq 2$ be a positive
integer, $q=7^{m}$, $(a,b)\in{\mathrm{GF}}(q^{2})^{2}\setminus\\{(0,0)\\}$ and
$f(u)={\mathrm{Tr}}(au^{4}+bu^{3})$. Define

$Zero(f)=\\{u\in U_{q+1}:f(u)=0\\}.$

Then $\\#Zero(f)\leq 8$. In particular, $\\#Zero(f)=8$ if $\\#Zero(f)\geq 3$.

###### Proof.

Recall that ${\mathrm{Tr}}$ is the trace function from ${\mathrm{GF}}(q^{2})$
to ${\mathrm{GF}}(q)$. By definition, then

$f(u)={\mathrm{Tr}}(au^{4}+bu^{3})=\frac{1}{u^{4}}(au^{8}+bu^{7}+b^{q}u+a^{q})$

if $u\in U_{q+1}$. Thus, $\\#Zero(f)\leq 8$ and

$Zero(f)=\\{u\in U_{q+1}:au^{8}+bu^{7}+b^{q}u+a^{q}=0\\}.$

If $\\#Zero(f)\geq 3$, we assume that $\\{1,-1,u_{0}\\}\subseteq Zero(f)$.
Then $f(1)=f(-1)=f(u_{0})=0$, which yields

$\displaystyle\left\\{\begin{array}[]{l}a^{q}=-a\\\ b^{q}=-b\\\
au_{0}^{8}+bu_{0}^{7}-bu_{0}-a=0.\end{array}\right.$ (17)

Denote $g(u)=au^{8}+bu^{7}+b^{q}u+a^{q}$. Assume that $a\neq 0$ and denote
$c=b/a$. By the first two equations in (17), we have $c^{q}=(b/a)^{q}=c$ and

$g(u)=a(u^{8}+\frac{b}{a}u^{7}-\frac{b}{a}u-1)=a(u^{8}+cu^{7}-cu-1).$

Denote

$h(u)=u^{8}+cu^{7}-cu-1.$

Then it is not hard to verify that $u^{q}$ and $u^{-1}$ are also the roots of
$h(u)=0$ if $u$ is a root of $h(u)=0$. Thus, $1$, $-1$, $u_{0}$ and
$u_{0}^{-1}=u_{0}^{q}$ are also the roots of $h(u)=0$. Further, from the third
equation in (17), we have

$c=\frac{u_{0}^{8}-1}{u_{0}^{7}-u_{0}}.$

Thus,

$h(u)=u^{8}+\frac{u_{0}^{8}-1}{u_{0}^{7}-u_{0}}\cdot
u^{7}-\frac{u_{0}^{8}-1}{u_{0}^{7}-u_{0}}\cdot u-1.$

If $h(u)=0$, then

$(u_{0}^{7}-u^{0})(u^{8}-1)-(u_{0}^{8}-1)(u^{7}-u)=0$

which is the same as

$\displaystyle\begin{array}[]{ccc}(u_{0}^{2}-1)(u^{2}-1)(u-u_{0})(u_{0}u-1)&\cdot(u_{0}u+5u+2u_{0}-1)&\nobreak\leavevmode\hfil\\\
\nobreak\leavevmode\hfil&\cdot(u_{0}u+4u+3u_{0}-1)&\nobreak\leavevmode\hfil\\\
\nobreak\leavevmode\hfil&\cdot(u_{0}u+3u+4u_{0}-1)&\nobreak\leavevmode\hfil\\\
\nobreak\leavevmode\hfil&\cdot(u_{0}u+2u+5u_{0}-1)&=0.\end{array}$

This means that $h(u)=0$ has eight roots as follows:

$\displaystyle 1,\leavevmode\nobreak\ -1,\leavevmode\nobreak\
u_{0},\leavevmode\nobreak\ u_{0}^{-1},\leavevmode\nobreak\
u_{1},\leavevmode\nobreak\ u_{2},\leavevmode\nobreak\
u_{3},\leavevmode\nobreak\ u_{4},$ (19)

where

$\displaystyle\left\\{\begin{array}[]{l}u_{1}=\frac{-2u_{0}+1}{u_{0}-2}\\\
u_{2}=\frac{-3u_{0}+1}{u_{0}-3}\\\ u_{3}=\frac{-4u_{0}+1}{u_{0}-4}\\\
u_{4}=\frac{-5u_{0}+1}{u_{0}-5}.\end{array}\right.$ (24)

Note that it is not hard to verify that $u_{3}=u_{1}^{-1}$, $u_{4}=u_{2}^{-1}$
and $u_{i}^{q}=1/u_{i}$ for any $i\in\\{1,2,3,4\\}$, which means that
$u_{i}^{q+1}=1$, i.e., $u_{i}\in U_{q+1}$ for any $i\in\\{1,2,3,4\\}$. Thus,
the eight roots given by (19) are in $U_{q+1}$. Moreover, these eight roots in
(19) are pairwise distinct. Suppose that $u_{1}=u_{0}$, then we have
$u_{0}^{2}=1$. This means that $u_{0}=1$ or $u_{0}=-1$, which is contrary to
our assumption that $1,-1,u_{0}$ are pairwise distinct in $U_{q+1}$. Thus,
$u_{1}\neq u_{0}$. By similar discussions, it is easily obtain that all
elements in (19) are pairwise distinct. This completes the proof. ∎

###  III-B The parameters of cyclic codes

In this subsection, we will determine the parameters of the cyclic code
${\mathcal{C}}_{m}$ and its dual ${\mathcal{C}}_{m}^{\perp}$, and prove that
these codes hold $3$-designs.

######  Theorem 6.

Let $q=7^{m}$ with $m\geq 2$ being a positive integer. Then the code
${\mathcal{C}}_{m}^{\perp}$ over ${\mathrm{GF}}(q)$ has the parameters
$[q+1,q-3,4]$. Furthermore, the minimum weight codewords in
${\mathcal{C}}_{m}^{\perp}$ support a $3$-$(q+1,4,5)$ design.

###### Proof.

It follows from definitions that the code ${\mathcal{C}}_{m}^{\perp}$ has
length $q+1$. Let $\alpha$ be a generator of the multiplicative group
${\mathrm{GF}}(q^{2})^{*}$ and define $\beta=\alpha^{q-1}$. Then $\beta\in
U_{q+1}$ is an $q+1$-th primitive root of unity in the field
${\mathrm{GF}}(q^{2})$. Let $g_{i}(x)$ denote the minimal polynomial of
$\beta^{i}$ over ${\mathrm{GF}}(q)$, where $i\in\\{3,4\\}$. Note that
$g_{i}(x)$ has only the roots $\beta^{i}$ and $\beta^{-i}$. We then deduce
that $g_{3}(x)$ and $g_{4}(x)$ are pairwise distinct irreducible polynomials
of degree 2\. By definition, the generator polynomial of
${\mathcal{C}}_{m}^{\perp}$ is $g_{3}(x)g_{4}(x)$ with degree 4. Thus,
${\mathcal{C}}_{m}^{\perp}$ has dimension $q+1-4=q-3$.

Let $U_{q+1}=\\{x_{1},x_{2},x_{3}...,x_{q+1}\\}$. Define

$\displaystyle
H=\left[\begin{array}[]{rrrrr}x_{1}^{-4}&x_{2}^{-4}&x_{3}^{-4}&\cdots&x_{q+1}^{-4}\\\\[5.69054pt]
x_{1}^{-3}&x_{2}^{-3}&x_{3}^{-3}&\cdots&x_{q+1}^{-3}\\\\[5.69054pt]
x_{1}^{\leavevmode\nobreak\ 3}&x_{2}^{\leavevmode\nobreak\
3}&x_{3}^{\leavevmode\nobreak\ 3}&\cdots&x_{q+1}^{\leavevmode\nobreak\
3}\\\\[5.69054pt] x_{1}^{\leavevmode\nobreak\ 4}&x_{2}^{\leavevmode\nobreak\
4}&x_{3}^{\leavevmode\nobreak\ 4}&\cdots&x_{q+1}^{\leavevmode\nobreak\
4}\end{array}\right].$ (29)

It is easily observed that

$\displaystyle{\mathcal{C}}_{m}^{\perp}=\\{{\mathbf{c}}\in{\mathrm{GF}}(q)^{q+1}:{\mathbf{c}}H^{T}={\mathbf{0}}\\}.$
(30)

By Lemma 8 and Equations (29) and (30), we have the minimum distance $d$ of
${\mathcal{C}}_{m}^{\perp}$ is at least $4$. Next we will prove that $d=4$.

Let $\\{x,y,z,w\\}\in\binom{U_{q+1}}{4}$. Without the loss of generality, we
assume that

$x=x_{i_{1}},\ y=x_{i_{2}},\ z=x_{i_{3}},\ w=x_{i_{4}},$

where $1\leq i_{1}<i_{2}<i_{3}<i_{4}\leq q+1$. Since $d\geq 4$, the rank of
the matrix $M(x,y,z,w)$ equals $3$, where $M(x,y,z,w)$ was defined by (13).
Let $(u_{i_{1}},u_{i_{2}},u_{i_{3}},u_{i_{4}})\in{\mathrm{GF}}(q)^{4}$ denote
a nonzero solution of

$\displaystyle\left[\begin{array}[]{llll}1&1&1&1\\\ x&y&z&w\\\
x^{7}&y^{7}&z^{7}&w^{7}\\\
x^{8}&y^{8}&z^{8}&w^{8}\end{array}\right]\left[\begin{array}[]{llll}u_{i_{1}}\\\
u_{i_{2}}\\\ u_{i_{3}}\\\ u_{i_{4}}\end{array}\right]={\mathbf{0}}.$

Since the rank of the matrix $M(x,y,z,w)$ is $3$, all these $u_{i_{j}}\neq 0$.
Define a vector
${\mathbf{c}}=(c_{0},c_{1},\ldots,c_{n})\in{\mathrm{GF}}(q)^{n+1}$, where
$c_{i_{j}}=u_{i_{j}}$ for $j\in\\{1,2,3,4\\}$ and $c_{h}=0$ for all
$h\in\\{0,1,\ldots,n\\}\setminus\\{i_{1},i_{2},i_{3},i_{4}\\}$. It is easily
observed that ${\mathbf{c}}$ is a codeword with Hamming weight $4$ in
${\mathcal{C}}_{m}^{\perp}$. The set
$\\{a{\mathbf{c}}:a\in{\mathrm{GF}}(q)^{*}\\}$ consists of all such codewords
of Hamming weight $4$ with nonzero coordinates in
$\\{i_{1},i_{2},i_{3},i_{4}\\}$. Hence, the code ${\mathcal{C}}_{m}^{\perp}$
has minimum distance $d=4$. Meanwhile, every codeword of Hamming weight $4$ in
${\mathcal{C}}_{m}^{\perp}$ with nonzero coordinates in
$\\{i_{1},i_{2},i_{3},i_{4}\\}$ must correspond to the set $\\{x,y,z,w\\}$.
Further, from $|M(x,y,z,w)|=0$ and Lemma 4, it follows that every codeword of
weight $4$ and its nonzero multiples in ${\mathcal{C}}_{m}^{\perp}$ correspond
to five such set $\\{x,y,z,w\\}$ . We then deduce that the codewords of weight
$4$ in ${\mathcal{C}}_{m}^{\perp}$ support a $3$-$(q+1,4,5)$ design. Thus, the
number of the codewords of weight $4$ in ${\mathcal{C}}_{m}^{\perp}$ is

$A_{4}^{\perp}=(q-1)\cdot\frac{\binom{q+1}{3}}{\binom{4}{3}}\cdot
5=\frac{5(q-1)^{2}q(q+1)}{24}.$

This completes the proof. ∎

######  Example 7.

Let $m=2$. Then the code ${\mathcal{C}}_{m}^{\perp}$ has the parameters
$[50,46,4]$. The number of the codewords of weight $4$ in
${\mathcal{C}}_{m}^{\perp}$ is $A_{4}^{\perp}=1176000$. The codewords of
weight $4$ in ${\mathcal{C}}_{m}^{\perp}$ support a $3$-$(50,4,5)$ design.

It is now time to determine the parameters of the cyclic code
${\mathcal{C}}_{m}$, which is described in the following theorem.

######  Theorem 8.

Let $q=7^{m}$ with $m\geq 2$ being a integer. Then we have the following
results.

  1. (I)

The code ${\mathcal{C}}_{m}$ over ${\mathrm{GF}}(q)$ has the parameters
$[q+1,4,q-7]$ and the weight enumerator

$\displaystyle
1+\frac{1}{336}(q-1)^{2}q(q+1)z^{q-7}+\frac{1}{12}(q-1)q(1+q)(7+5q)z^{q-1}+$
(32) $\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
\frac{1}{7}(q-1)(1+q)(7+(q-1)q)z^{q}+\frac{7}{16}(q-1)^{2}q(1+q)z^{q+1}.$

  2. (II)

The code ${\mathcal{C}}_{m}$ and its dual ${\mathcal{C}}_{m}^{\perp}$ support
$3$-designs. Furthermore, the codewords of weight $q-7$ in ${\mathcal{C}}_{m}$
hold a $3$-$(q+1,q-7,\lambda)$ design, where

$\lambda=\frac{(q-7)(q-8)(q-9)}{336}.$

The complement of this design is a $3$-$(q+1,8,1)$ design, i.e., Steiner
systems $S(3,8,q+1)$.

###### Proof.

(I) By definition, it is clear that the code ${\mathcal{C}}_{m}$ has length
$q+1$. By Theorem 6, the dual code ${\mathcal{C}}_{m}^{\perp}$ of
${\mathcal{C}}_{m}$ has dimension $q-3$. Thus, the dimension of the code
${\mathcal{C}}_{m}$ is 4.

Further, by definitions and Lemma 5, the minimum distance of
${\mathcal{C}}_{m}$ is $q-7$ and the code ${\mathcal{C}}_{m}$ has at most four
nonzero weights, i.e.,

$w_{1}=q-7,\leavevmode\nobreak\ w_{2}=q-1,\leavevmode\nobreak\
w_{3}=q,\leavevmode\nobreak\ w_{4}=q+1\leavevmode\nobreak\ .$

We now determine the number $A_{w_{i}}$ of the codewords with weight $w_{i}$
in ${\mathcal{C}}_{m}$. Since ${\mathcal{C}}_{m}^{\perp}$ has minimum distance
$d=4$, the first four Pless Power Moments lead to the following system of
equations:

$\displaystyle\left\\{\begin{array}[]{l}A_{w_{1}}+A_{w_{2}}+A_{w_{3}}+A_{w_{4}}=q^{4}-1\\\
w_{1}A_{w_{1}}+w_{2}A_{w_{2}}+w_{3}A_{w_{3}}+w_{4}A_{w_{4}}=q^{3}(q-1)n\\\
w_{1}^{2}A_{w_{1}}+w_{2}^{2}A_{w_{2}}+w_{3}^{2}A_{w_{3}}+w_{4}^{2}A_{w_{4}}=q^{2}(q-1)n(qn-n+1)\\\
w_{1}^{3}A_{w_{1}}+w_{2}^{3}A_{w_{2}}+w_{3}^{3}A_{w_{3}}+w_{4}^{3}A_{w_{4}}=q(q-1)n(q^{2}n^{2}-2qn^{2}+3qn-q+n^{2}-3n+2),\end{array}\right.$
(37)

where $n=q+1$. Solving the system of equations in (37) yields the weight
enumerator in (32).

(II) By the conclusions of (I) and Theorem 6, from Theorem 1 we get that both
${\mathcal{C}}_{m}$ and ${\mathcal{C}}_{m}^{\perp}$ hold $3$-designs. By (32),
the number of the codewords with weight $q-7$ in ${\mathcal{C}}_{m}$ is

$A_{q-7}=\frac{1}{336}(q-1)^{2}q(q+1).$

Since $q-7$ is the minimum weight of ${\mathcal{C}}_{m}$, the number of
supports of the codewords of weight $q-7$ is

$\displaystyle b=\frac{A_{q-7}}{q-1}=\frac{1}{336}(q-1)q(q+1).$ (38)

Then the values of $\lambda$ follow from Equations (38) and (4).

By definitions, the complement of the supports of the codewords with the
minimum weight $q-7$ in ${\mathcal{C}}_{m}$ holds a
$3$-$(q+1,8,\lambda^{\prime})$ and the number of this supports equals the
value of $b$ of (38). Then we deduce that $\lambda^{\prime}=1$ from

$b=\frac{1}{336}(q-1)q(q+1)=\lambda^{\prime}\cdot\frac{\binom{q+1}{3}}{\binom{8}{3}}.$

This means that the complement of the supports of the minimum weight codewords
in ${\mathcal{C}}_{m}$ forms a Steiner system $S(3,8,q+1)$. This completes the
proof.

∎

######  Example 9.

Let $m=2$. Then the code ${\mathcal{C}}_{2}$ has the parameters $[50,4,42]$
and weight enumerator

$1+16800z^{42}+2469600z^{48}+808800z^{49}+2469600z^{50},$

which is verified by a Magma program.

######  Example 10.

Let $m=3$. Then the code ${\mathcal{C}}_{3}$ has the parameters $[344,4,336]$
and weight enumerator

$1+41073858z^{336}+5790693384z^{342}+1971662832z^{343}+6037857126z^{344},$

which is verified by a Magma program.

###  III-C Automorphism groups of cyclic codes

In this subsection, we will show that the cyclic code ${\mathcal{C}}_{m}$ and
its dual ${\mathcal{C}}_{m}^{\perp}$ are invariant under group actions of
certain permutation groups which are $3$-transitive, i.e., the automorphism
groups of those code are $3$-transitive. To this end, we use the similar
method in Liu et al [28].

Define

$\displaystyle\mathrm{Stab}_{U_{q+1}}=\left\\{\left(\begin{array}[]{cc}\beta_{2}^{q}&\beta_{1}^{q}\\\
\beta_{1}&\
\beta_{2}\end{array}\right)\in\mathrm{PGL}(2,q^{2}):\leavevmode\nobreak\
\beta_{1},\beta_{2}\in{\mathrm{GF}}(q^{2}),\beta_{1}^{q+1}\neq\beta_{2}^{q+1}\right\\}.$
(41)

Then we have

$\displaystyle\mathrm{Stab}_{U_{q+1}}=\left(\begin{array}[]{cc}u_{0}&1\\\
1&u_{0}\end{array}\right){\mathrm{PGL}}(2,q)\left(\begin{array}[]{cc}u_{0}&1\\\
1&u_{0}\end{array}\right)^{-1}$ (46)

with $u_{0}\in U_{q+1}\setminus\\{\pm 1\\}$ and the following result which was
documented in [28, Proposition 5].

######  Lemma 11.

[28] Let symbols and notation be the same as before. Let $q=7^{m}$ with $m\geq
2$ being a positive integer. Then the setwise stabilizer of $U_{q+1}$ can be
expressed as $\mathrm{Stab}_{U_{q+1}}$ defined by (41). Moreover, the action
of $\mathrm{Stab}_{U_{q+1}}$ on $U_{q+1}$ is equivalent to the action of
${\mathrm{PGL}}(2,q)$ on the projective line ${\mathrm{PG}}(1,q)$ and
$\mathrm{Stab}_{U_{q+1}}$ is $3$-transitive.

Denote the set

$\displaystyle\begin{array}[]{c}\mathcal{SF}:=\left\\{{\mathrm{Tr}}\left(au^{4}+bu^{3}\right)\in{\mathrm{GF}}(q^{2})[u]/\langle
u^{q+1}-1\rangle:a,b\in{\mathrm{GF}}(q^{2})\right\\}\end{array}$ (48)

and the operator ${}^{\prime}\circ^{\prime}$ is defined by

$\displaystyle\begin{array}[]{c}(G\circ
f)(u):=(\beta_{1}u+\beta_{2})^{4(q+1)}f\left(\frac{\alpha_{1}u+\alpha_{2}}{\beta_{1}u+\beta_{2}}\right),\end{array}$
(50)

where $G=\left(\begin{array}[]{cc}\alpha_{1}&\alpha_{2}\\\ \beta_{1}&\
\beta_{2}\end{array}\right)^{-1}\in\mathrm{GL}(2,q^{2})$ and
$f\in\mathcal{PF}$.

Let $\bar{G}=\left(\begin{array}[]{cc}\beta_{2}^{q}&\beta_{1}^{q}\\\
\beta_{1}&\ \beta_{2}\end{array}\right)^{-1}\in\mathrm{GL}(2,q^{2})$ and
denote

$\displaystyle\mathrm{\overline{Stab}}_{U_{q+1}}=\left\\{\left(\begin{array}[]{cc}\beta_{2}^{q}&\beta_{1}^{q}\\\
\beta_{1}&\
\beta_{2}\end{array}\right)\in\mathrm{GL}(2,q^{2}):\leavevmode\nobreak\
\beta_{1},\beta_{2}\in{\mathrm{GF}}(q^{2}),\beta_{1}^{q+1}\neq\beta_{2}^{q+1}\right\\}.$
(53)

Next we will show that the linear space $\mathcal{PS}$ under the action of the
group $\mathrm{\overline{Stab}}_{U_{q+1}}$ is invariant. To this end, we need
the results in the following two lemmas.

######  Lemma 12.

Let $q=7^{m}$ with $m\geq 2$ being a positive integer. Let
$\bar{G}=\left(\begin{array}[]{cc}\beta_{2}^{q}&\beta_{1}^{q}\\\ \beta_{1}&\
\beta_{2}\end{array}\right)^{-1}\in\mathrm{GL}(2,q^{2})$ and
$f\in\mathcal{SF}$. Then $\bar{G}\circ f\in\mathcal{SF}$.

###### Proof.

Denote $f_{1}={\mathrm{Tr}}(au^{4})\in{\mathrm{GF}}(q^{2})[u]/\langle
u^{q+1}-1\rangle$ and
$f_{2}={\mathrm{Tr}}(bu^{3})\in{\mathrm{GF}}(q^{2})[u]/\langle
u^{q+1}-1\rangle$. We only need to prove $(\bar{G}\circ
f_{1})(u)\in\mathcal{SF}$ and $(\bar{G}\circ f_{2})(u)\in\mathcal{SF}$ for any
$(a,b)\in{\mathrm{GF}}(q^{2})^{2}$.

For any $a\in{\mathrm{GF}}(q^{2})$, from definitions we have

$\displaystyle\begin{array}[]{l}(\bar{G}\circ f_{1})(u)\\\
=(\beta_{1}u+\beta_{2})^{4(q+1)}f_{1}\left(\frac{\beta_{2}^{q}u+\beta_{1}^{q}}{\beta_{1}u+\beta_{2}}\right),\\\
={\mathrm{Tr}}\left(a\cdot(\beta_{1}u+\beta_{2})^{4q}(\beta_{1}u+\beta_{2})^{4}\cdot\frac{(\beta_{2}^{q}u+\beta_{1}^{q})^{4}}{(\beta_{1}u+\beta_{2})^{4}}\right)\\\
={\mathrm{Tr}}\left(a\cdot(\beta_{1}^{q}u^{-1}+\beta_{2}^{q})^{4}\cdot
u^{4}(\beta_{2}^{q}+\beta_{1}^{q}u^{-1})^{4}\right)\\\
={\mathrm{Tr}}\left(au^{4}\cdot(\beta_{1}^{q}u^{-1}+\beta_{2}^{q})^{8}\right)\end{array}$
(59)

Note that $7|\binom{8}{i}$ for any $i\in\\{2,3,4,5,6\\}$. Therefore, from the
Binomial Theorem we have

$\displaystyle u^{4}\cdot(\beta_{1}^{q}u^{-1}+\beta_{2}^{q})^{8}$
$\displaystyle=$
$\displaystyle\sum_{i=0}^{8}\binom{8}{i}\beta_{1}^{qi}\beta_{2}^{q(8-i)}u^{4-i},$
(60) $\displaystyle=$
$\displaystyle\beta_{2}^{8q}u^{4}+\beta_{2}^{7q}\beta_{1}^{q}u^{3}+\beta_{1}^{8q}u^{-4}+\beta_{2}^{q}\beta_{1}^{7q}u^{-3}$
$\displaystyle=$
$\displaystyle\beta_{2}^{8q}u^{4}+\beta_{2}^{7q}\beta_{1}^{q}u^{3}+(\beta_{1}^{8}u^{4})^{q}+(\beta_{2}\beta_{1}^{7}u^{3})^{q}$

Applying the above equation (60) to (59), we get

$\displaystyle\begin{array}[]{l}(\bar{G}\circ
f_{1})(u)={\mathrm{Tr}}\left(a(\beta_{2}^{8q}u^{4}+\beta_{2}^{7q}\beta_{1}^{q}u^{3})+a^{1/q}(\beta_{1}^{8}u^{4}+\beta_{2}\beta_{1}^{7}u^{3})\right)\in\mathcal{SF}.\end{array}$
(62)

Using the similar method on $f_{1}$ to $f_{2}$, we can easily obtain

$\displaystyle\begin{array}[]{l}(\bar{G}\circ
f_{2})(u)={\mathrm{Tr}}\left(b(\beta_{1}\beta_{2}^{7q}u^{4}+\beta_{2}^{7q+1}u^{3})+b^{1/q}(\beta_{1}^{7}\beta_{2}^{1/q}u^{4}+\beta_{1}^{q+7}u^{3})\right)\in\mathcal{SF}\end{array}$
(64)

for any $b\in{\mathrm{GF}}(q^{2})$. The desired conclusion then follows from
Equations (62) and (64). ∎

According to Lemma 12 and the definition of ${}^{\prime}\circ^{\prime}$ in
(50), we can easily obtain the following result and we omit its proof.

######  Lemma 13.

Let symbols and notation be the same as before. Let $q=7^{m}$ with $m\geq 2$
being a positive integer and $E$ be the $2\times 2$ identity matrix. For any
$\overline{G}_{1},\overline{G}_{2}\in\mathrm{\overline{Stab}}_{U_{q+1}}$ and
$f_{1},f_{2}\in\mathcal{SF}$, we have $\overline{G}_{1}\circ
f_{1}\in\mathcal{SF}$ , $E\circ f_{1}=f_{1}$ ,
$(\overline{G}_{1}\overline{G}_{2})\circ
f_{1}=\overline{G}_{1}\circ(\overline{G}_{2}\circ f_{1})$, and
$\overline{G}_{1}\circ(a^{\prime}f_{1}+b^{\prime}f_{2})=a^{\prime}\overline{G}_{1}\circ
f_{1}+b^{\prime}\overline{G}_{2}\circ f_{2}$ for all
$a^{\prime},b^{\prime}\in{\mathrm{GF}}(q)$.

Let ${\mathrm{GF}}(q)^{U_{q+1}}$ denote the vector space consisting of all
elements $(c_{u})_{u\in U_{q+1}}$, where $c_{u}\in{\mathrm{GF}}(q)$. The
action of the semidirect product
$\left({\mathrm{GF}}(q)^{*}\right)^{U_{q+1}}\rtimes\mathrm{Stab}_{U_{q+1}}$ on
${\mathrm{GF}}(q)^{U_{q+1}}$ is defined by

$\displaystyle\left((a_{u})_{u\in U_{q+1}};g\right)(c_{u})_{u\in
U_{q+1}}=(a_{u}c_{g^{-1}(u)})_{u\in U_{q+1}}.$

Then the multiplication in
$\left({\mathrm{GF}}(q)^{*}\right)^{U_{q+1}}\rtimes\mathrm{\overline{Stab}}_{U_{q+1}}$
is given by

$\displaystyle\left((a_{u})_{u\in U_{q+1}};g_{1}\right)\left((b_{u})_{u\in
U_{q+1}};g_{2}\right)=\left((c_{u})_{u\in U_{q+1}};g_{1}g_{2}\right),$

where $c_{u}=a_{u}b_{g_{1}^{-1}(u)}$.

The following theorem is one of the main result in this paper. It show that
the code ${\mathcal{C}}_{m}$ and its dual admit $3$-transitive automorphism
group.

######  Theorem 14.

Let $q=7^{m}$ with $m\geq 2$ being a positive integer. Define the subgroup
$G_{i}$ of
$\left({\mathrm{GF}}(q)^{*}\right)^{U_{q+1}}\rtimes\mathrm{Stab}_{U_{q+1}}$ by

$\displaystyle
G_{i}=\left\\{\left(\left((\beta_{1}u+\beta_{2})^{4i(q+1)}\right)_{u\in
U_{q+1}};\left(\begin{array}[]{cc}\beta_{2}^{q}&\beta_{1}^{q}\\\
\beta_{1}&\beta_{2}\end{array}\right)^{-1}\right):\beta_{1},\beta_{2}\in{\mathrm{GF}}(q^{2}),\beta_{1}^{q+1}\neq\beta_{2}^{q+1}\right\\},$

where $i\in\\{1,-1\\}$. Then we have the following results.

  1. 1.

$G_{1}$ is a subgroup of the monomial automorphism group
$\mathrm{MAut}({\mathcal{C}}_{m})$. Moreover, the automorphism group of
${\mathcal{C}}_{m}$ is $3$-transitive.

  2. 2.

$G_{-1}$ is a subgroup of the monomial automorphism group
$\mathrm{MAut}({\mathcal{C}}_{m}^{\perp})$ and the automorphism group of
${\mathcal{C}}_{m}$ is $3$-transitive.

###### Proof.

1) By the definitions in (1) and (48),

${\mathcal{C}}_{m}=\left\\{(f(u))_{u\in U_{q+1}}:f\in\mathcal{SF}\right\\}.$

Then the desired conclusion follows from definitions and Lemmas 13, 3 and 11.

2) The desired conclusion follows from the first conclusion of this theorem.

∎

##  IV Concluding remarks

In this paper, we investigated a class of cyclic codes ${\mathcal{C}}_{m}$
over ${\mathrm{GF}}(7^{m})$ and completely determined their parameters. The
results showed that the code ${\mathcal{C}}_{m}$ has four nonzero weights and
supports $3$-designs. Meanwhile, the dual code of ${\mathcal{C}}_{m}$ also
supports $3$-designs, and the automorphism group of the code
${\mathcal{C}}_{m}$ and its dual ${\mathcal{C}}_{m}^{\perp}$ are
$3$-transitive. Specifically, the complements of the supports of the minimum
weight codewords in ${\mathcal{C}}_{m}$ form a Steiner system
$S(3,8,7^{m}+1)$. Using the similar method of this paper and [28], we remark
that it may obtain some new cyclic codes admitting $3$-transitive automorphism
groups and determine their parameters by properly choosing the value of $q$
and the exponents of $u$ in (1).

## References

  * [1] R. T. Chien, “Cyclic decoding procedure for the Bose-Chaudhuri-Hocquenghem codes”, _IEEE Trans. Inform. Theory_ , vol. 10, no. 4, pp. 357–363, 1964.
  * [2] G. D. Forney, “On decoding BCH codes,” _IEEE Trans. Inform. Theory,_ vol. 11, no. 4, pp. 549–557, 1995.
  * [3] E. Prange, “Some cyclic error-correcting codes with simple decoding algorithms,” Air Force Cambridge Research Center-TN-58-156, Cambridge, Mass., April 1958.
  * [4] C. Ding, T. Helleseth, “Optimal Ternary Cyclic Codes From Monomials,” _IEEE Trans. Inform. Theory_ , vol. 59, no. 9, pp. 5898-5904, 2013.
  * [5] Z. Zhou, C. Ding, “Seven Classes of Three-Weight Cyclic Codes,” _IEEE Trans. Commun._ , vol. 61, no. 10, pp. 4120-4126, 2013.
  * [6] C. Li, C. Ding, S. Li, “LCD Cyclic Codes Over Finite Fields,” _IEEE Trans. Inform. Theory_ , vol. 63, no. 7, pp. 4344-4356, 2017.
  * [7] H. Liu, C. Ding, “Infinite families of 2-designs from GA1(q) actions,” ArXiv:1707.02003, 2017.
  * [8] C. Ding, “A sequence construction of cyclic codes over finite fields,” _Cryptogr. Commun._ , vol. 10, no. 2, pp. 319-341, 2018.
  * [9] Z. Zha, L. Hu, Y. Liu, X. Cao, “Further results on optimal ternary cyclic codes,” _Finite Fields Their Appl._ , vol.75, pp. 101898, 2021.
  * [10] C. Ding, _Designs from Linear Codes_. Singapore: World Scientific, 2018.
  * [11] C. Ding, C. Tang, “Infinite families of near MDS codes holding t-designs,” _IEEE Trans. Inform. Theory_ , vol. 66, no. 9, pp. 5419–5428, 2020.
  * [12] C.Ding, C. Tang, V.D. Tonchev, “Linear codes of 2-designs associated with subcodes of the ternary generalized Reed-Muller codes,” _Des. Codes Cryptogr._ , vol. 88, no. 4, pp. 625-641, 2020.
  * [13] C. Ding, C. Tang, “The linear codes of t-designs held in the Reed-Muller and Simplex codes,” arXiv:2008.09935, 2020.
  * [14] C. Ding, “Infinite families of 3-designs from a type of five-weight code,” _Des. Codes Cryptogr._ , vol. 86, no. 3, pp. 703–719, 2018.
  * [15] C. Ding, C. Li, “Infinite families of $2$-designs and $3$-designs from linear codes,” _Discrete Math._ , vol. 340, no. 10, pp. 2415–2431, 2017.
  * [16] C. Ding, _Codes from Difference Sets_. Singapore: World Scientific, 2015.
  * [17] V. D. Tonchev, “Codes and designs,” In Handbook of Coding Theory, vol. II, V. S. Pless and W. C. Huffman, eds., Elsevier, Amsterdam, pp. 1229–1268, 1998.
  * [18] V. D. Tonchev, “Codes,” In Handbook of Combinatorial Designs, 2nd edition, C. J. Colbourn and J. H. Dinitz, eds., CRC Press, New York, pp. 677–701, 2007.
  * [19] C. Ding, “An infinite family of Steiner systems from cyclic codes,” _Journal of Combinatorial Designs_ , vol. 26, pp. 127–144, 2018.
  * [20] W. C. Huffman, V. Pless, _Fundamentals of Error-Correcting Codes_. Cambridge: Cambridge University Press, 2003.
  * [21] C. Tang, C. Ding, M. Xiong, “Steiner systems $S(2,4,\frac{3^{m}-1}{2})$ and 2-designs from ternary linear codes of length $\frac{3^{m}-1}{2}$,” _Des. Codes Cryptogr._ , vol. 87, no. 12, pp. 2793–2811, 2019.
  * [22] C. Tang, C. Ding, M. Xiong, “Codes, differentially $\delta$-uniform functions, and $t$-designs,” _IEEE Trans. Inform. Theory_ , vol. 66, no. 6, pp. 3691–3703, 2020.
  * [23] C. Tang, C. Ding, “An infinite family of linear codes supporting $4$-designs,” _IEEE Trans. Inform. Theory_ , vol. 67, no. 1, pp. 244-254, 2021.
  * [24] X. Du, R. Wang, C. Tang, Q. Wang, “Infinite families of 2-designs from two classes of binary cyclic codes with three nonzeros”, arXiv:1903.08153, 2019.
  * [25] X. Du, R. Wang, C. Tang, Q. Wang, “Infinite families of 2-designs from two classes of linear codes”, arXiv:1903.07459, 2019.
  * [26] H. Yan, “A class of primitive BCH codes and their weight distribution.” _Appl. Algebra Eng. Commun. Comput._ vol. 29, no. 1, pp. 1–11, 2018.
  * [27] H. Yan, H. Liu, C. Li, et al., “Parameters of LCD BCH codes with two lengths”, _Adv. Math. Commun._ , vol. 12, no. 3, pp. 579-594, 2018.
  * [28] Q. Liu, C. Ding, S. Mesnager, C. Tang, V.D. Tonchev, “On infinite families of narrow-sense antiprimitive BCH codes admitting 3-transitive automorphism groups and their consequences”, arXiv:2109.09051, 2021.