On Equivalence Classes of Boolean Functions - Information Security and Cryptology-ICISC 2010 - page 316

Proof. Let the LFSR be represented by S jk 1 ,andwrite

M k 1 + i 1
j

b 0 ,M k 1 + i 2
j

b 0 ,...,M k 1 + i w
j

1 f = { b 0 } ,

where M j is the generator matrix of the register and 0 ≤ i 1 <i 2 < ... < i w ≤

q − 2. Clearly, g ∼ L f if and only if there exists a 0 ≤ k 2 ≤ q − 2 such that

M k 2 + i 1
j

b 0 ,M k 2 + i 2 b 0 ,...,M k 2 + i w 1 g = { b 0 } .

j j

If k 1 = k 2 ,then f = g if and only if there exists an 1 ≤ m ≤ w − 1 such that

k 2 + i s = k 1 + i s⊕m (mod q − 1) ,

for 1 ≤ s ≤ w ,where

m = s + m,

if s + m

≤ w,

s ⊕

s + m − w,

otherwise .

That is, for 1 ≤ s ≤ w ,

k 2 − k 1 = i s⊕m − i s (mod q − 1) . (1)

Let k 0 be the number satisfying the equations (1) such that

k 0 − k 1 =mi k { k − k 1 (mod q − 1) } ,

where k satisfy the equations (1). Then a number k 2 satisfies the equations (1)
if and only if k 0 −

1
k 0 −k 1

q−

k 1 | ( k 2 − k 1 (mod q − 1)). Therefore, there are exactly

such k 2 ,andeach k 2 corresponds to a function which is equal to f .Since

k 0 − k 1 = i m +1 − i 1 = i m +2 − i 2 = ... = i w − i w−m

= i 1 − i w−m +1 + q − 1= ... = i m − i w + q − 1 ,

we have w ( k 0 − k 1 )= m ( q − 1). Therefore, the number of g satisfying g ∼ L f is

w w

( w,q−

q − 1or q −

m ,where1

≤ m ≤ w − 1and

1) |

m , and the result follows.

w
( w,q− 1) |

Particularly, if ( q − 1 ,w )=1,then m implies m = w .Wehavethe

following two corollaries:

B n and

Corollary 1. Let f ∈ | 1 f | = w ,where 1 ≤ w<q − 1 and ( q − 1 ,w )=1 .

B n Then the number of g ∈ such that g ∼ L f is q − 1 .

B n and

Corollary 2. Let f ∈ | 1 f | = w ,where 1 ≤ w<q − 1 . Then there are

B n φ ( q − 1) /n − 1 classes of g ∈ such that g ∼ N f , and every class contains

w
m functions which are linear equivalent to each other, where m is a positive
divisor of w and

q −

w
( w,q− 1) |

m .