Counting rotation symmetric functions using Polya’s theorem

Homogeneous rotation symmetric (invariant under cyclic permutation of the variables) Boolean functions have been extensively studied in recent years due to their applications in cryptography. In this paper we give an explicit formula for the number of homogeneous rotation symmetric functions over the finite field GF(pm)GF(pm) using Polya’s enumeration theorem, which completely solves the open problem proposed by Yuan Li in 20082008. This result simplifies the proof and the nonexplicit counting formula given by Shaojing Fu et al. over the field GF(p)GF(p). This paper also gives an explicit count for nn-variable balanced rotation symmetric Boolean functions with n=pqn=pq, where pp and qq are distinct primes. Previous work only gave an explicit count for the case where nn is prime and lower bounds for the case where nn is a prime power.