For the original size parameter s>=2, set lambda=ceil(log2 s) and e=4lambda. Enumerate the 2^e monic binary polynomials of degree e; for each, test division by every monic polynomial of degree one through floor(e/2). A reducible polynomial has a factor in that range. Finite-field theory guarantees an irreducible polynomial of every positive degree, so this search terminates. Since 2^e=O(s^4), even this exhaustive search uses polynomial time in s. Its 2^e binary coordinate vectors supply at least s^4 distinct residue-field elements. This is a deterministic existence construction, not a practical recommendation for large fields.