Factoring polynomials with rational coefficients
This paper describes a polynomial-time algorithm for the factorization of primitive polynomials \(f\in \mathbb Z[X]\) into irreducible factors. The number of bit operations used by the algorithm is \(O(n^{12} + n^9(\log \vert f\vert)^3)\), where \(n\) is the degree of \(f\) and \(\vert \sum_i a_iX^i \vert = (\sum_i a_i^2)^{1/2})\). The result can be generalized to algebraic number fields and to polynomials in several variables. One of the main ingredients of the algorithm is a new basis reduction algorithm for lattices in \(n\)-dimensional space. This basis reduction algorithm can be used to find short vectors in an \(n\)-dimensional lattice. The paper briefly mentions two applications of this algorithm in diophantine approximation. It is also of importance for problems from operations research and cryptography.
- A Remark on the Hensel Factorization Method
- A sublinear additive sieve for finding prime number
- An Inequality About Factors of Polynomials
- Approximate formulas for some functions of prime numbers
- Generalization of the Euclidean algorithm for real numbers to all dimensions higher than two
- scientific article; zbMATH DE number 3657869 (Why is no real title available?)
- scientific article; zbMATH DE number 3737757 (Why is no real title available?)
- scientific article; zbMATH DE number 3750146 (Why is no real title available?)
- scientific article; zbMATH DE number 3333393 (Why is no real title available?)
- Irreducible polynomials with integral coefficients have succinct certificates
- Lattices and factorization of polynomials
- On Hensel factorization. I
- Computing the Abel map
- Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits
- Sampling methods for shortest vectors, closest vectors and successive minima
- On asymptotic extrapolation
- The number of roots of a lacunary bivariate polynomial on a line
- Factoring polynomials over global fields
- On selecting a maximum volume sub-matrix of a matrix and related problems
- The hyperelliptic integrals and
- Improved nonlinear multiuser precoding using lattice reduction
- Factoring multivariate polynomials over finite fields
- Solvability by radicals is in polynomial time
- On Lovász' lattice reduction and the nearest lattice point problem
- A strongly polynomial minimum cost circulation algorithm
- Factoring sparse multivariate polynomials
- Fast parallel absolute irreducibility testing
- An application of factoring
- Algorithms to construct Minkowski reduced and Hermite reduced lattice bases
- Irreducibility of multivariate polynomials
- Polymorphic arrays: A novel VLSI layout for systolic computers
- Strongly polynomial algorithm for a class of combinatorial LCPs
- On application of some recent techniques of the design of algebraic algorithms to the sequential and parallel evaluation of the roots of a polynomial and to some other numerical problems
- On principal ideal testing in algebraic number fields
- A modification of the LLL reduction algorithm
- Factoring polynomials and primitive elements for special primes
- Computer algebra: Past and future
- An application of simultaneous diophantine approximation in combinatorial optimization
- A hierarchy of polynomial time lattice basis reduction algorithms
- The existence of simple \(6\text{-}(14,7,4)\) designs
- An inequality about irreducible factors of integer polynomials
- Dual vectors and lower bounds for the nearest lattice point problem
- On the practical solution of the Thue equation
- Existence theorems in mathematics
- The iterated mod problem
- Simultaneously good bases of a lattice and its reciprocal lattice
- Complexity of computations in Commutative Division of the USSR Academy of Sciences
- Approximate factorization of multivariate polynomials and absolute irreducibility testing
- A heuristic irreducibility test for univariate polynomials
- Polynomial time algorithms for sentences over number fields
- A note on the \(f\)-factor-lattice of bipartite graphs
- Improved low-density subset sum algorithms
- On interpolating arithmetic read-once formulas with exponentiation
- A relation of primal--dual lattices and the complexity of shortest lattice vector problem
- Sentences over integral domains and their computational complexities
- New \(t\)-designs and large sets of \(t\)-designs
- Renormalization automated by Hopf algebra
- Simultaneous reduction of a lattice basis and its reciprocal basis
- Recognizing badly presented \(Z\)-modules
- An upper bound on the average number of iterations of the LLL algorithm
- An algorithm for finding a shortest vector in a two-dimensional modular lattice
- A partial digest approach to restriction site mapping
- Computation and rationality of Belyi functions in genus zero
- On the period matrix of a Riemann surface of large genus (with an appendix by J. H. Conway and N. J. A. Sloane)
- Lattice basis reduction: Improved practical algorithms and solving subset sum problems
- Distribution of Hermite's constant and the shortest vector in lattices of dimension two
- Factorization properties of lattices over the integers
- Factoring multivariate integral polynomials
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- Solving norm form equations via lattice basis reduction
- Diophantine approximation of matrices
- Polar varieties, real equation solving, and data structures: the hypersurface case
- Real data-integer solution problems within the Blum-Shub-Smale computational model
- Straight-line programs in geometric elimination theory
- The optimal LLL algorithm is still polynomial in fixed dimension.
- Tile invariants: New horizons.
- On lattice reduction for polynomial matrices
- The better bound of private key in RSA with unbalanced primes
- Computing the sign or the value of the determinant of an integer matrix, a complexity survey.
- On the solution of units and index form equations in algebraic number fields
- On the limits of nonapproximability of lattice problems
- Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey
- Complexity of the Havas, Majewski, Matthews LLL Hermite normal form algorithm
- Approximate solutions of polynomial equations.
- Short vectors of planar lattices via continued fractions
- The chords' problem
- Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
- Connected components of the moduli of elliptic \(K3\) surfaces
- Cryptanalysis of a public key cryptosystem based on Diophantine equations via weighted LLL reduction
- Return of GGH15: provable security against zeroizing attacks
- On the hardness of the computational ring-LWR problem and its applications
- Twist-2 at seven loops in planar \( \mathcal{N} =4\) SYM theory: full result and analytic properties
- Planckian axions and the weak gravity conjecture
- Fiat-Shamir and correlation intractability from strong KDM-secure encryption
- Shortest vector from lattice sieving: a few dimensions for free
- Solving a class of modular polynomial equations and its relation to modular inversion hidden number problem and inversive congruential generator
- Segment LLL reduction of lattice bases using modular arithmetic
- Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness
- On the orthogonality of the Chebyshev-Frolov lattice and applications
- Matrix product constraints by projection methods
- An even extremal lattice of rank 64
- Calculation of Belyi functions for trees with weighted edges
- Isomorphism theorem on vector spaces over a ring
- Analysis of hidden number problem with hidden multiplier
- Effective resolution of Diophantine equations of the form \(u_n+u_m=w p_1^{z_1} \dotsm p_s^{z_s}\)
- Lattice attacks against elliptic-curve signatures with blinded scalar multiplication
- On lattice-based algebraic feedback shift registers synthesis for multisequences
- Algorithms for commutative algebras over the rational numbers
- Systematics of aligned axions
- Four-loop non-singlet splitting functions in the planar limit and beyond
- CSIDH: an efficient post-quantum commutative group action
- Fault-tolerant modular reconstruction of rational numbers
This page was built for publication: Factoring polynomials with rational coefficients
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1165896)