Since f (x) divides x e ’ 1 it follows that ( f ) ‚ corresponding d1 »1 sequences from (g) and the

(x e ’ 1), the set of sequences where st+e = st , d2 »2 sequences from (h). This gives d1 »1 d2 »2 dis-

tinct sequences all of period lcm(»1 , »2 ). Formally

i.e., of period dividing e. Hence, all sequences gen-

we can write this as [d1 (»1 )][d2 (»2 )] = [d(»)] where

erated by f (x) has period dividing e. Let the se-

quence {st } correspond to the polynomial φ(x). If d = d1 d2 gcd(»1 , »2 ) and » = lcm(»1 , »2 ).

gcd( f (x), φ(x)) = 1 then as a consequence of the

identity (x µ ’ 1)φ(x) = σ (x) f (x), it follows that {st } EXAMPLE 3. Let f (x) = x 3 + x + 1 and f2 (x) =

1

x 4 + x 3 + x 2 + x + 1. The cycle structure of ( f )

has smallest period e, since in this case f (x) must 1

divide x µ ’ 1 and thus µ ≥ e which implies that can be written [1(1) + 1(7)], and similarly for ( f )

1

µ = e. as [1(1) + 3(5)]. Combining the cycle structure as

described above, gives the cycle structure [1(1) +

In particular, when f (x) is an irreducible poly-

1(7) + 3(5) + 3(35)].

nomial of period e, then all the nonzero sequences

in ( f ) have period e. For example the polynomial

f (x) = x 4 + x 3 + x 2 + x + 1 in Example 1 is irre- The discussion above shows that the period of

ducible and divides x 5 + 1 and has period 5, and all sequences in ( f ) is completely determined

therefore all nonzero sequences in ( f ) have pe- from the periods of the divisors of f (x). This way of

riod 5. controlling the periods is one of the main reasons

To determine the cycle structure of ( f ) for an for using linear recursions as building blocks in

arbitrary polynomial f (x) that can be factored as stream ciphers.

f (x) = The sequence {st } can be expressed in terms of

fi (x)ki , fi (x) irreducible, one ¬rst needs to

determine the cycle structure of ( fiki ) and then the zeros of its characteristic polynomial f (x) of

the cycle structure for (gh) when gcd(g,h) = 1. degree n. In the case when the zeros of f (x) are

simple, which is the case when the sequence has

odd period, then {st } has a unique expansion in the

Cycle structure of „¦( f r)

form

Let f (x) be an irreducible polynomial of period e.

n

Let k be de¬ned such that 2k < r ¤ 2k+1 . Then

st = ai ±it

( f r )\ ( f ) contains

i=1

n2 j n2 j’1

’2

2 for some constants ai and where ±i , 1 ¤ i ¤ n are

sequences of period e2 for j = 1, 2, . . . , k and the zeros of f (x).

j

The main problem with linear recursions in

k

2nr ’ 2n2 cryptography is that it is easy to reconstruct a

sequence {st } generated by a characteristic poly-

sequences of period e2k+1 .

nomial f (x) of degree n from the knowledge of 2n

consecutive bits in {st }, since this gives a system

EXAMPLE 2. Let f (x) = x 3 + x + 1 be the charac-

of n equations for determining the unknown coef-

teristic polynomial with e = 7, that generates an

¬cients of f (x). The Berlekamp“Massey algorithm

m-sequence. The number of sequences of each pe-

is an ef¬cient method for ¬nding f (x) in this way.

riod in ( f 3 ) is therefore

Several methods exist to increase the linear span,

Number 1 7 56 448 i.e, the smallest degree of the linear recursion that

Period 1 7 14 28 generates the sequence. We just mention a few

(gh) when gcd(g, h) = 1. simple ones obtained by multiplying sequences.

Cycle structure of

Let {ut } and {vt } be two sequences of odd pe-

riod. Then, ut = ai ±it where ±i , 1 ¤ i ¤ n, are

In this case it can be shown that each sequence

the zeros of the characteristic polynomial of {ut }

{st } in (gh) can be written uniquely

and vt = b jβ t where β j, 1 ¤ j ¤ m, are the zeros

{st } = {ut } + {vt } j

of the characteristic polynomial of {vt }. Then the

where {ut } ∈ (g) and {vt } ∈ (h). Further, the pe- sequence {wt } = {ut vt } can be written as

riod of the sum {ut } + {vt } is equal to the least com-

wt = ai b j(±i β j)t .

mon multiple of the period of the two sequences,

i.e.,

This shows that {wt } is generated by the polyno-

per (st ) = lcm( per (ut ), per (vt )). mial with the, at most, nm different zeros ±i β j for

Serpent 563

1 ¤ i ¤ n, 1 ¤ j ¤ n. If gcd( per (ut ), per (vt )) = 1, In Code-Division Multiple-Access (CDMA) appli-

then it can be shown that per (wt ) = per (ut ) per (vt ). cations it is desirable to have a family of sequences

However, the number of zeros and ones in se- with certain properties. To facilitate synchroniza-

quence {wt } will in general not be balanced even if tion, it is desirable that all the out-of-phase auto-

this is the case for {ut } and {vt }. This follows since correlation values (i = j, „ = 0) are small. To min-

wt = 1 if and only if ut = vt = 1, and thus only 1/4 imize the interference due to the other users in

of the elements in {wt } will be 1™s when {ut } and a multiple access situation, the cross-correlation

{vt } are balanced. values (i = j) must also be kept small. For this

Often one considers sequences of the form reason the family of sequences should be designed

to minimize

wt = st+„1 st+„2 . . . st+„k ,

Cmax = max{|Ci, j| : 1 ¤ i, j ¤ M,

where st is an m-sequence. A closer study of the ze-

and either i = j or „ = 0}.

ros of the characteristic polynomial of {wt } shows

k

that the linear span is at most i=1 n and fre- For practical applications in communication

i

quently the equality holds. systems one needs a family F of sequences of pe-

Every Boolean function in n variables, f (x1 , riod e, such that the number of users M = |F| is

x2 , . . . , xn ), can be written uniquely as the sum large and simultaneously Cmax is small. Also in

stream ciphers it is of importance that the gen-

n n n

f (x1 , x2 , . . . , xn ) = u0 + ui xi + ui j xi x j erated sequences have good auto-correlation and

i=1 i=1 j=1 cross-correlation properties.

+ · · · + u12...n x1 x2 · · · xn

Tor Helleseth

with binary coef¬cients (see algebraic normal form

in Boolean functions).

References

One can determine the linear span ob-

tained by combining n different m-sequences

[1] Golomb, S.W. (1982). Shift Register Sequences.

{at }, {bt }, . . . , {ct } with characteristic polynomials

Aegean Park Press, Laguna Hills, CA.

of pair-wise relative prime degrees e1 , e2 , . . . , en [2] Helleseth, T. and P.V. Kumar (1999). “Pseudonoise

using a Boolean combining function. From the sequences.” The Mobile Communications Hand-

Boolean function f (x1 , x2 , . . . , xn ) we construct book, ed. J.D. Gibson. Chapter 8. CRC/IEEE Press,

a sequence wt = f (at , bt , . . . , ct ). Then the lin- Boca Raton, FL/Piscataway, NJ.

ear span of the combined sequence is equal to [3] Helleseth, T. and P.V. Kumar (1998). “Sequences

f (e1 , e2 , . . . , en ), evaluated over the integers. with low correlation.” Handbook of Coding The-

ory, eds. V.S. Pless and W.C. Huffman. Chapter 21.

It is important in applications of sequences in

Elsevier, Amsterdam.

communication systems as well as in stream ci-

[4] Selmer, E.S. (1966). Linear Recurrence Relations

pher systems to generate sequences with good

over Finite Fields. Lecture Notes, Department of

auto- and cross-correlation properties.

Mathematics, University of Bergen, Norway.

Let {u(t)} and {v(t)} be two binary sequences of

[5] Zierler, N. (1959). “Linear recurring sequences.” J.

period e. The cross-correlation of the sequences Soc. Indust. Appl. Math., 7, 31“48.

{u(t)} and {v(t)} at shift „ is de¬ned as

e’1

(’1)ut+„ ’vt

Cu,v („ ) =

SERPENT

t=0

where the sum t + „ is computed modulo e. In the

Serpent is a 128-bit block cipher designed by

case when the two sequences are the same, we de-

note this by the auto-correlation at shift „ . Anderson et al. and ¬rst published in 1998 [1].

Later that year the cipher was slightly modi¬ed [2]

For synchronization purposes one prefers se-