This paper presents a graph-based approach to designing arithmetic circuits over Galois fields (GFs) based on a polynomial ring (PR) representation, which is a redundant representation for GF arithmetic. The proposed method extends a graph-based circuit description, called a Galois-field arithmetic circuit graph (GF-ACG), which was originally proposed for no redundant GF arithmetic. First, the extension of a GF-ACG is applied to the design and verification of the PR-based GFarithmetic circuits. Then the efficiency of the proposed method is demonstrated using the design and verification of PR-based GF multipliers. In addition, GF(28) inversion circuits with differentGF representations are designed and evaluated in order to confirm the significance of the PR representation.