Factoring polynomials over arbitrary finite fields

T. Lange, A. Winterhof

    Research output: Contribution to journalArticleAcademicpeer-review

    1 Citation (Scopus)

    Abstract

    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
    Volume234
    Issue number1-2
    DOIs
    Publication statusPublished - 2000

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

  • Cite this