  Primitive polynomials over finite fields are crucial for various domains of
computer science, including classical pseudo-random number generation, coding
theory and post-quantum cryptography. Nevertheless, the pursuit of an efficient
classical algorithm for generating random primitive polynomials over finite
fields remains an ongoing challenge. In this paper, we show how to solve this
problem efficiently through hybrid quantum-classical algorithms, and designs of
the specific quantum circuits to implement them are also presented. Our
research paves the way for the rapid and real-time generation of random
primitive polynomials in diverse quantum communication and computation
applications.
