Linear Legendre pseudorandom functions were introduced in 1988 by Damgård, and higher degree generalizations were introduced by Russell and Shparlinski in 2004. To the best of our knowledge, there exists no efficient hardware circuit that accelerates the computation of the Legendre PRF in hardware. In this work, we try to address the issue of constructing a hardware accelerator for this task. We show that the most challenging part of constructing such a circuit is computing a sub-circuit that computes the modular reduction \(p\bmod a\) , when both operands a, p are variable. We propose two ideas for solving this problem. The first uses a number from the equivalence class \(a \bmod p\) which is easier to compute than the modular reduction itself. We show that this circuit also computes the Legendre symbol correctly, but takes few additional clock cycles to do so. The second uses a sequential circuit for constructing modular reduction, for which we can additionally upper bound the number of clock cycles it takes to finish the computation. We verify our algorithm by synthesizing both circuits using three different standard cell libraries.