2009/07/28 by Gábor Ivanyos, Marek Karpiński, Nitin Saxena · 1 citation
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #graph theory and CDMA systems #Finite Group Theory Research #Mathematics #Generalization #Permutation (music) #Factoring #Polynomial #Discrete mathematics #Time complexity #Finite field #Factorization of polynomials #Prime (order theory) #Degree (music) #Constant (computer programming) #Combinatorics #Matrix polynomial #Computer science
paper · doi:10.1145/1576702.1576730
openalex publication_date 2009/07/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
In this work we relate the deterministic complexity of factoring polynomials (over finite fields) to certain combinatorial objects we call m-schemes. We extend the known conditional deterministic subexponential time polynomial factoring algorithm for finite fields to get an underlying m-scheme. We demonstrate how the properties of m-schemes relate to improvements in the deterministic complexity of factoring polynomials over finite fields assuming the generalized Riemann Hypothesis (GRH). In particular, we give the first deterministic polynomial time algorithm (assuming GRH) to find a nontrivial factor of a polynomial of prime degree n where (n-1) is a smooth number.