Factoring polynomials over function fields

If K/k is a function field in one variable of positive characteristic, we describe a general algorithm to factor one-variable polynomials with coefficients in K. The algorithm is flexible enough to find factors subject to additional restrictions, e.g., to find all roots that belong to a given finite dimensional k-subspace of K, more efficiently. For bounded characteristic, it runs in polynomial time, relative to factorizations over the constant field k and also provides a deterministic polynomial time irreducibility test. We also discuss applications to places of reducible reduction, when k is a global field, and to list decoding of Reed-Solomon codes.