  In a 2006 paper, Damg{\aa}rd and Frandsen designed a faster version of the
Quadratic Frobenius Test. This test assumes the Extended Riemann Hypothesis in
order to find small nonresidues, which allow construction of quadratic
extensions with faster arithmetic. In this paper, I describe a version of the
test using small nonresidues, without assuming any unproven hypothesis.
