Factoring polynomials over arbitrary finite fields

T. Lange, A. Winterhof

    Research output: Contribution to journalArticleAcademicpeer-review

    2 Citations (Scopus)


    We analyse an extension of Shoup's (Inform. Process. Lett. 33 (1990) 261–267) deterministic algorithm for factoring polynomials over finite prime fields to arbitrary finite fields. In particular, we prove the existence of a deterministic algorithm which completely factors all monic polynomials of degree n over Fq, q odd, except possibly O(n2 log2 q/q) polynomials, using O(n2+ log2q) arithmetical operations in Fq.
    Original languageEnglish
    Pages (from-to)301-308
    JournalTheoretical Computer Science
    Issue number1-2
    Publication statusPublished - 2000


    Dive into the research topics of 'Factoring polynomials over arbitrary finite fields'. Together they form a unique fingerprint.

    Cite this