Available as a preprint.

We present an algorithm that, for every fixed degree n ≥ 3, will enumerate all degree-n places of the projective line over a finite field k up to the natural action of PGL₂(k) using O(log q) space and Õ(q^n–3) time, where q=#k. Since there are Θ(q^n–3) orbits of PGL₂(k) acting on the set of degree-n places, the algorithm is quasilinear in the size of its output. The algorithm is probabilistic unless we assume the extended Riemann hypothesis, because its complexity depends on that of polynomial factorization: for odd n, it involves factoring Θ(q^n–3) polynomials over k of degree up to 1 + ((n–1)/2)ⁿ.

For composite degrees n, earlier work of the author gives an algorithm for enumerating PGL₂(k) orbit representatives for degree-n places of P¹ over k that runs in time Õ(q^n–3) independent of the extended Riemann hypothesis, but that uses O(q^n–3) space.

We also present an algorithm for enumerating orbit representatives for the action of PGL₂(k) on the degree-n effective divisors of P¹ over finite fields k. The two algorithms depend on one another; our method of enumerating orbits of places of odd degree n depends on enumerating orbits of effective divisors of degree (n+1)/2.