1 Introduction
The crosscorrelation of maximal length linear shift register sequences (or m-sequences) has been a research topic for more than 40 years. Traditionally, the crosscorrelation properties of binary m-sequences were mainly studied due to their applications in sequence designs. The crosscorrelation between m-sequences leads to several challenging and difficult problems and is closely related to exponential sums over finite fields. For example, the crosscorrelation between an m-sequence and its reverse sequence is equivalent to the classical mathematical notion of Kloosterman sums. Many important results have been obtained using a variety of methods on exponential sums but several open problems remain.
In the recent years, the study of binary bent functions, motivated by cryptography, has been an important research topic. Several classes of bent functions have been constructed using m-sequences and their correlation properties.
Anzeige
In 1985, binary bent functions were generalized to p-ary bent functions by Kumar et al. [23]. Generalized bent functions have received a lot of attention and several new p-ary bent functions are also closely related to the crosscorrelation of m-sequences. Study of p-ary bent functions also leads to connections and problems on Jacobsthal sums. This paper is based on an invited talk for the 70th birthday of Jacques Wolfmann and gives a rather short survey of some of these recent connections. We also include some of the contributions by Jacques Wolfmann on Kloosterman sums that have applications to the crosscorrelation of m-sequences and to the construction of bent functions.
2 Preliminaries
Let GF(p) be the finite field with p elements. The initial state (s
0, s
1, ..., s
n − 1) and the linear recursion of degree n over GF(p) defined by
generates a periodic sequence {s
t
}. The characteristic polynomial of the linear recursion is
Since n consecutive elements of the sequence determine the sequence completely, the maximal period for a recursion of degree n is p
n
− 1. In the case when f(x) ∈ GF(p)[x] is a primitive polynomial, the recursion is known to generate a maximal linear sequence (or an m-sequence) of period p
n
− 1.
$$ \sum\limits_{i=0}^n c_i s_{t+i} = 0, \; \; \mbox{ where } c_0,c_n \neq 0, $$
$$ f(x) = \sum\limits_{i=0}^n c_i x^i. $$
Some important and well-known properties of m-sequences are:
-
The m-sequence has period p n − 1, each nonzero element occurs p n − 1 times and the zero element occurs p n − 1 − 1 times.
-
For any m-sequence {s t } and \(\tau\neq 0 \pmod{p^n-1}\) it holds that {s t + τ − s t } is also an m-sequence.
Let {u
t
} and {v
t
} be two p-ary sequences of period ε. The crosscorrelation between the two sequences at shift τ, 0 ≤ τ < ε, is
where ω is a complex primitive p-th root of unity. If the two sequences are the same we use the term autocorrelation instead of crosscorrelation. A useful property for m-sequences is their optimal two-level autocorrelation, which is important for synchronization purposes in many communication systems.
$$ C_{u,v} = \sum\limits_{t=0}^{\varepsilon-1} \omega^{u_{t+\tau}-v_t} $$
Anzeige
Lemma 1
The autocorrelation function Cs,s(τ) of the m-sequence {s
t
} has the property,
$$ C_{s,s}(\tau)= \left\{\begin{array}{rll} p^n-1 & \mbox{ if } & \tau=0 \pmod{p^n - 1} \\ -1 & \mbox{ if } & \tau \neq 0 \pmod{p^n - 1}. \end{array}\right. $$
This result is an easy consequence of the balanced distribution of the elements in an m-sequence and that {s
t + τ − s
t
} is an m-sequence for \(\tau \neq 0 \pmod{p^n - 1}\).
Let Tr
n
be the trace function from GF(p
n
) to GF(p) defined by
The m-sequence {s
t
} can (after a suitable cyclic shift) be described simply by
where ξ is a zero of the characteristic polynomial f(x). The different shifts of the m-sequence are obtained by
where c = ξ
τ
∈ GF(p
n
)* = GF(p
n
) ∖ {0}. Two m-sequences {u
t
} and {v
t
} of the same period p
n
− 1 are related by a decimation d such that u
t
= v
dt + τ and \(\gcd(d,p^n-1)~=~1\).
$$ \mathrm{Tr}_n(x)=\sum\limits_{i=0}^{n-1} x^{p^i}. $$
$$ s_t=\mathrm{Tr}_n\left(\xi^t\right), $$
$$ \label{eq:shiftandadd} s_{t+\tau}=\mathrm{Tr}_n\left(c\xi^t\right), $$
The crosscorrelation between any two m-sequences of the same period ε = p
n
− 1 that differ by a decimation d can be described by the following exponential sum by using the trace function representation
where c = ξ
τ
. Determining the values and the number of occurrences of each value in the crosscorrelation function C
d
(τ) when τ runs through {0,1, ⋯ ,p
n
− 2} is equivalent to finding the distribution of this exponential sum for any c ≠ 0.
$$ \begin{array}{rll} \label{eq:Cd} C_d(\tau) &=& \sum\limits_{t=0}^{\varepsilon-1} \omega^{s_{t+\tau} - s_{dt}} \\ &=& \sum\limits_{t=0}^{\varepsilon-1} \omega^{\mathrm{Tr}_n(\xi^{t+\tau}-\xi^{dt})} \\ &=& \sum\limits_{x\in\mathrm{GF}(p^n)^*} \omega^{\mathrm{Tr}_n(cx-x^d)} \end{array} $$
The following result was stated for p = 2 by Golomb [8] without proof and first proved and generalized to any odd p by Helleseth [10].
Theorem 1
If \(d \not \in \{1,p,\cdots,p^{n-1}\}\), (i.e., when the two m-sequences are cyclically distinct), then C
d
(τ) is at least three-valued when τ = 0,1, ⋯ , p
n
− 2.
Therefore, the crosscorrelation between m-sequences takes on at least three values. For binary sequences of length 2
n
− 1, the following is a complete list of all decimations known to give three-valued crosscorrelation. It is a challenging and open problem to decide whether this list is complete.
Theorem 2
The crosscorrelation C
d
(τ) is three-valued and the complete correlation distribution is known for the following values of d:
The PhD thesis of 1972 by Niho [25] provided new ideas that lead to new decimations with four-valued crosscorrelation for the case n = 2k. The decimations considered were of the form
For such values of d Niho showed that the crosscorrelation is given by
where N
a
is the number of common solutions of the two equations
$$ d = s\left(2^k-1\right)+1. $$
$$ C_d(\tau) = -1 + (N_a-1)2^k $$
$$ x^{2s-1} +a x^s+a^{2^k} x^{s-1}+1 = 0\quad\mbox{and}\quad x^{2^k+1}=1. $$
For p = 2, several known classes of binary four-valued decimations of this form are given in the theorem below. The first two are due to Niho [25]. One should observe the second decimation that turns out to give interesting p-ary bent functions if p = 2 is replaced by a general p.
Theorem 3
Let e2(i) be the highest power of 2 dividing the integer i and assume n = 2k. The crosscorrelation C
d
(τ) is four-valued and the complete correlation distribution is known for the following values of d:
(iii)
There are also some sporadic cases known with more than four-valued crosscorrelation for which the distribution is known. One important case is when d = − 1. In this case, the crosscorrelation function C
− 1(τ) + 1 is the famous Kloosterman sum over GF(p
n
)
An astonishing results by Lachaud and Wolfmann [24] is that for p = 2, the Kloosterman sum (or equivalently C
− 1(τ) + 1) takes on all the integer values satisfying \(|K(a)|\leq 2\sqrt{2^n}\) with \(K(a)=0\pmod{4}\).
$$ K(a)=\sum\limits_{x\in\mathrm{GF}(p^n)}\omega^{\mathrm{Tr}_n(x+ax^{-1})}. $$
Two long standing conjectures from Helleseth [10] on the crosscorrelation are to show that (a) if n = 2
i
then the crosscorrelation is at least four-valued (recently proven in the binary case [20]) and (b) the crosscorrelation function always takes on − 1 as one of the values when \(p=1 \pmod{d-1}\).
3 Bent functions
Let f(x):GF(p
n
)↦GF(p) be a p-ary function. The Walsh transform coefficients of f(x) are defined for any y ∈ GF(p
n
) to be
Then ω
f(x) can be recovered from
The function f(x) is called a bent function if it holds for any y ∈ GF(p
n
) that
In the binary case, bent functions are functions that have maximal distance to all affine functions. Nonbinary bent functions were introduced in 1985 by Kumar et al. [23] and are sometimes referred to as generalized bent functions. A bent function f(x) is called regular if
for some f
*(y):GF(p
n
)↦GF(p). A bent function f(x) is said to be weakly regular if there exists a complex number u having unit magnitude such that
for all y ∈ GF(p
n
). The function f
* is also a (weakly) regular bent function and is called the dual of f. Weakly regular bent functions were shown to be useful for constructing certain combinatorial objects such as partial difference sets, strongly regular graphs and association schemes (see [2, 26, 27]). This justifies why the classes of (weakly) regular bent functions are of independent interest.
$$ S_f(y)=\sum\limits_{x\in\mathrm{GF}(p^n)}\omega^{f(x)-\mathrm{Tr}_n(yx)}. $$
$$ \omega^{f(x)}=\frac{1}{p^n} \sum\limits_{y\in\mathrm{GF}(p^n)}S_f(y)\omega^{\mathrm{Tr}_n(yx)}. $$
$$ |S_f(y)|^2 = p^n. $$
$$ p^{-\frac{n}{2}}S_f(y)=\omega^{f^*(y)} $$
$$ up^{-\frac{n}{2}}S_f(y)=\omega^{f^*(y)} $$
The following discussion will consider polynomial functions
with \(a_i,x\in\mathrm{GF}(p^n)\). An interesting problem is to find simple polynomials that give bent functions.
$$ f(x)=\mathrm{Tr}_n\left(\sum\limits_{i=0}^s a_i x^{d_i}\right) $$
3.1 Ternary monomial bent functions
A well-known construction by Dillon is known to give a binary bent function over GF(22k
) in the cases when the Kloosterman sum K(a) over GF(2
k
) takes on the value 0 for some a ∈ GF(2
k
). This was proved affirmatively by Lachaud and Wolfmann [24] as a consequence of the fact that the binary Kloosterman sum over GF(2
k
) takes on all values being equal zero modulo 4 in the range \(|K(a)|\leq 2\cdot\sqrt{2^k}\) and, therefore, zero is one of the values that always occurs in the Kloosterman sum. This construction was generalized by Helleseth and Kholosha [12] to p-ary bent functions in the following result.
Theorem 4
Let n = 2k and t be an arbitrary positive integer with \(\gcd(t,p^k+1)=1\) for an odd prime p. For any nonzero a ∈ GF(p
n
), define the following p-ary function mapping GF(p
n
) to GF(p)
Then for any b ∈ GF(p
n
)*, the corresponding Walsh transform coefficient of f(x) is equal toAssuming p
k
> 3, then f(x) is bent if and only if the following Kloosterman sum over GF(p
k
) satisfies \(K(a^{p^k+1})=0\). Moreover, if \(K(a^{p^k+1})=0\) then f(x) is a regular bent function.
$$ f(x)=\mathrm{Tr}_n\big(a x^{t(p^k-1)}\big). $$
$$ \begin{array}{rll} S_a(b)&=&K\left(a^{p^k+1}\right)+p^k\omega^{-\mathrm{Tr}_n(a^{p^k}b^{t(p^k-1)})}\quad\mbox{and}\\ S_a(0)&=&p^k-\left(p^k-1\right)K\left(a^{p^k+1}\right). \end{array} $$
Take p = 2, without loss of generality assume a ∈ GF(2
k
) and drop the requirement for 2
k
> 3. Then exactly the same result as in Theorem 4 holds in the binary case giving the above mentioned Dillon class of Boolean bent functions. The proof of the nonbinary version is more complicated than in the binary case even though the final results are quite similar.
For p = 3, we learned from Wolfmann [28] (private communication) that Katz has shown that 0 always occurs as a value in the ternary Kloosterman sum and thus the construction above leads to bent functions. For more details on the ternary Klosterman sum see Katz and Livné [21]. Recently, it was shown by Kononen et al. [22] that for any p > 3 the Kloosterman sum does not take on the value 0. Thus, the only cases where this construction leads to bent functions are the binary and ternary cases.
The following ternary bent function was first conjectured and proved in part by Helleseth and Kholosha [12]. The complete proof that this is a weakly regular bent functions with a particular form of the Walsh transform was given in [9, 17].
Theorem 5
Let n = 2k with k odd. Then the ternary function f(x) mapping GF(3
n
) to GF(3) and given byis a weakly regular bent function if \(a=\xi^{\frac{3^k+1}{4}}\) and ξ is a primitive element of GF(3
n
). Moreover, for any b ∈ GF(3
n
) the corresponding Walsh transform coefficient of f(x) is equal towhere \(\delta=\xi^{\frac{3^n-1}{4}}\).
$$ f(x)=\mathrm{Tr}_n\left(ax^{\frac{3^n-1}{4}+3^k+1}\right) $$
$$ S_f(b)=-3^k\omega_3^{\pm\mathrm{Tr}_k\left(\frac{b^{3^k+1}}{a(\delta+1)}\right)}, $$
An interesting not weakly regular bent function is the following function, for which we do not know whether it belongs to an infinite family. It would be important to construct infinite families of not weakly regular bent functions from monomials or other simple polynomials.
Fact 6
The ternary function f(x) mapping GF(36) to GF(3) and given bywhere ξ is a primitive element of GF(36), is bent and not weakly regular bent.
$$ f(x)=\mathrm{Tr}_6\left(\xi^7 x^{98}\right)\enspace, $$
3.2 Binomial bent functions
For p = 2, the Niho decimation d = 23k
− 22k
+ 2
k
+ 1 leads to 4-valued cross-correlation function between two binary m-sequences of period p
4k
− 1 [11, 25]. This is equivalent to case (ii) in Theorem 3. For p > 2 the decimation d = p
3k
− p
2k
+ p
k
+ 1 is interesting for another reason since it leads to an infinite family of bent functions [14].
Theorem 7
Let n = 4k. Then p-ary function f(x) mapping GF(p
n
) to GF(p) and given byis a weakly regular bent function. Moreover, for y ∈ GF(p
n
) the corresponding Walsh transform coefficient of f(x) is equal towhere x0 is a unique solution in GF(p
k
) of the equationIn particular, if y2 ∈ GF(p2k
) then \(x_0=-\mathrm{Tr}^{2k}_k\big(y^2\big)\). Also, every value − p2k
ω
i
with i = {1,...,p − 1} occurs p2k − 1(p2k
+ 1) times in the Walsh spectrum of f(x) and − p2k
occurs (p2k − 1 − 1)(p2k
+ 1) + 1 times.
$$ f(x)=\mathrm{Tr}_n\left(x^{p^{3k}+p^{2k}-p^k+1}+x^2\right) $$
$$ S_f(y)=-p^{2k}\omega^{\mathrm{Tr}_k(x_0)/4}, $$
$$ y^{p^{2k}+1}+\left(y^2+X\right)^{(p^{2k}+1)/2}+y^{p^k(p^{2k}+1)}+\left(y^2+X\right)^{p^k(p^{2k}+1)/2}=0. $$
The dual bent function is defined in the lemma and shows that even if a bent function has an easy description, in this case a simple binomial polynomial, the dual function, that involves defining x
0 from y, can be quite complicated.
Similarly to Fact 6, there is a special binomial polynomial that also leads to a not weakly regular bent function and where the same question remains open, namely to find an infinite family of such bent functions.
Fact 8
The ternary function f(x) mapping GF(34) to GF(3) and given bywhere ξ is a primitive element of GF(34), is bent and not weakly regular bent.
$$ f(x)=\mathrm{Tr}_4\left(ax^{22}+x^4\right)\quad\mbox{with}\quad a\in\left\{\pm\xi^{10},\xi^{30}\right\}, $$
All known univariate polynomials representing a p-ary bent function are listed in the tables below. For further details on quadratic bent functions the reader is referred to [12, 13]. Here ξ denotes a primitive element of GF(3
n
), r and wr refer to regular and weakly regular bent functions respectively. The first eight families in the table are monomials of the form \(\mathrm{Tr}_n(ax^d)\) while the last two are binomial bent functions in the form Tr
n
(F(x)).
n d or F(x) |
a
| deg | Remarks |
|---|---|---|---|
2 | a ≠ 0 | 2 | r, wr |
2k
p
k
+1 |
\(a + a^{p^{k}} \neq 0\)
| 2 | wr |
\(p^{j} + 1, \frac{n}{\mathrm{gcd}(n,j)}-\mathrm{odd}\)
| a ≠ 0 | 2 | r, wr |
p
j
+ 1 | Some condition on a
| 2 | r, wr |
\(\frac{3^{k} + 1}{2}, \mathrm{gcd}(k, n) = 1, k-\mathrm{odd}\)
| a ≠ 0 | k + 1 | r, wr |
2k t(3
k
- 1), gcd(t, 3
k
+ 1) = 1 |
\(K (a^{p^{k}+1}) = 0\)
| ternary r | |
2k \(\frac{3^{n} - 1}{4} + 3^{k} + 1\)
|
\( \xi \frac{3^{k} + 1}{4}\)
|
n
| ternary wr |
6 98 |
ξ
7
| 6 | ternary not wr |
4 ax
22 + x
4
|
\(\pm\xi^{10},\pm\xi^{30}\)
| 4 | ternary not wr |
\(4k\;\;\;\; x^{p^{3k}+p^{2k}-p^k+1}+x^2\)
| (p-1)k+2 | wr |
The following table gives further examples of ternary binomial bent functions of the form \(\mathrm{Tr}_n(a_1x^{d_1}+a_2 x^{d_2})\) obtained from a computer search. Cases excluded are quadratic binomial bent functions where exponents are of the form p
i
+ p
j
and bent functions of Dillon type where the two exponents are of the form t(p
n/2 − 1).
n
|
d
1
|
d
2
| Remarks |
|---|---|---|---|
3 | 8 | 14 | not wr |
6 | 14 | 70 | not wr |
6 | 14 | 98 | wr |
6 | 20 | 92 | not wr |
6 | 28 | 140 | wr |
8 | 20 | 100 | wr |
8 | 40 | 280 | wr |
8 | 88 | 136 | wr |
4 An exponential sum related to Jacobsthal sums
Since f(x) = x
d
+ x
2 is a bent function for d = p
3k
+ p
2k
− p
k
+ 1, a natural question is to consider the distribution of the more general exponential sum \(f(x)=\mathrm{Tr}_n(ax^d+bx^2)\) for any a,b ∈ GF(p
n
). Thus, we consider
This is equivalent to finding the complete weight distribution of the cyclic code with zeros ξ
2 and ξ
d
, where ξ is a primitive element of GF(p
n
).
$$ S_f(0)=\sum\limits_{x\in\mathrm{GF}(p^n)}\omega^{\mathrm{Tr}_n(a x^d + b x^2)}. $$
It turns out that this exponential sum leads to nice and surprising connections to Jacobsthal sums. Let η(x) be the quadratic character of GF(q). The Jacobsthal sum H
n
(a) of order n is
$$ H_n(a) = \sum\limits_{x\in\mathrm{GF}(q)}\eta(x^{n+1}+ax). $$
The next result from [15] gives relations between the exponential sum and the number of solutions of a special equation. The proof of this theorem uses some ideas by Niho [25]. If n is even, let U denote a cyclic subgroup of order p
n/2 + 1 of the multiplicative group of GF(p
n
) (generated by \(\xi^{p^{n/2}-1}\), where ξ is a primitive element of GF(p
n
)).
Theorem 9
Let n = 4k. For any a,b ∈ GF(p
n
), define the following p-ary function mapping GF(p
n
) to GF(p)
Then the Walsh transform coefficient of f(x) evaluated at point zero is equal towhere 2N(a,b) is the number of zeros in U of the polynomial
$$ f(x)=\mathrm{Tr}_n\left(ax^{p^{3k}+p^{2k}-p^k+1}+bx^2\right). $$
$$ S_f(0)=p^{2k}(2N(a,b)-1), $$
$$ \label{eq:L} L(X)=b^{p^{2k}}X+aX^{p^k}+bX^{p^{2k}}+a^{p^{2k}}X^{p^{3k}}. $$
(1)
Case 1
For most values of a,b ∈ GF(p
n
) when either \(a^{p^k(p^k+1)}\neq b^{p^k+1}\) or a
2 = b
d
with b ≠ 0, the exponential sum takes on just three values − p
2k
, p
2k
or 3p
2k
. Equivalently, the polynomial L(X) defined in (1) has none, two or four zeros in U, i.e., N(a,b) ∈ {0,1,2}.
Case 2
In the remaining cases, when \(a^{p^k(p^k+1)} = b^{p^k+1}\) with a
2 ≠ b
d
there are many more possible values for the exponential sum and N(a,b). Then a detailed study in [15] shows that
where g is any element in GF(p
2k
)* with \(g^{p^k-1}=-b^{p^{3k}}/a\), and that 2N(a,b) can be alternatively expressed as
and
$$ N(a,b) = \left|\left\{c\in\mathrm{GF}\left(p^k\right) \; | \; (cg)^2 - b^{p^{2k}+1} \; \mbox{ is a nonsquare in $\mathrm{GF}\left(p^{2k}\right)$ } \right\}\right|, $$
$$ 2 N(a,b) = p^k - \frac{H_{p^k+1} \left(-b^{p^k+1}/g^2\right)}{p^k+1} + 1 $$
$$ S_f(0) = p^{2k}\left( p^k - \frac{H_{p^k+1} \left(-b^{p^k+1}/g^2\right)}{p^k+1}\right). $$
In [15, Theorem 2] a new nontrivial upper bound on the Jacobsthal sum of order p
k
+ 1 was proved and this gives the following estimate:
$$ \left|N(a,b)-\frac{p^k+1}{2}\right|\leq p^{k/2}. $$
5 Conclusions
This survey has given some connections between the crosscorrelation of m-sequences, exponential sums and a brief overview of decimations that provide three- and four- valued crosscorrelation for binary sequences. Furthermore, relations to p-ary bent functions and Jacobsthal sums have been discussed. In particular, it was shown that the decimation by Niho d = 23k
+ 22k
− 2
k
+ 1 that led to four-valued crosscorrelation was closely related to an infinite family of p-ary bent functions defined by \(\mathrm{Tr}_{4k}(x^2 + x^d)\) where d = p
3k
+ p
2k
− p
k
+ 1 (i.e., d is obtained by replacing p = 2 by general p in the Niho decimation d). Finally, the values of the exponential sum \(\mathrm{Tr}_{4k}(ax^2+ bx^d)\) were shown to be closely related to Jacobsthal sums of order p
k
+ 1.
Open AccessThis is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Open Access This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.