Generation of large primitive polynomial over a Galois field has been a topic of intense research over the years. The problem of finding a primitive polynomial over a Galois field of a large degree is computationaly expensive and there is no deterministic algorithm for the same. In this paper we present an new recursive algorithm based on cellular automata for generation of very large primitive polynomial over finite fields. The motivation for cellular automata based construction comes into play as it has an excellent regular structure and efficient hardware representation. At the end we give an application of this new construction in a RS-encoded MPSK Modulation in Rayleigh fading channel. But the general construction given here can be extended to any area like cryptography, coding theory etc. having application of sufficiently large Galois field.