A note on the factorization method of Niederreiter

In this paper, we explicitly obtain the coefficient matrix arising from a linearization of Niederreiter's factorization algorithm and analyze the complexity of setting it up. It turns out that its setup cost is linear both in the degree of a polynomial to be factored and in the size of the base field.