Factoring polynomials with rational coefficients

1982/12/01 by A. K. Lenstra, H. W. Lenstra, László Lovász +1 · 64 citations
Computer Science · Mathematics · Engineering · #Coding theory and cryptography #Analytic Number Theory Research #graph theory and CDMA systems

paper · doi:10.1007/bf01457454

Cited by

• NP-hardness of SVP in Euclidean Space
• The hidden subgroup problem for infinite groups
• Probabilistic Analysis of LLL Reduced Bases
• On Taking r-th Roots without r-th Nonresidues over Finite Fields and Its Applications
• A polynomial algorithm for minimizing discrete convic functions in fixed dimension
• Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs
• On Factoring and Power Divisor Problems via Rank-3 Lattices and the Second Vector
• On the complex zeros and the computational complexity of approximating the reliability polynomial
• Sphere Decoding Revisited
• On the Cryptographic Hardness of Learning Single Periodic Neurons
• Algebra in Algorithmic Coding Theory
• Randomized Polynomial-Time Root Counting in Prime Power Rings
• The complete 10-tetrahedra census of orientable cusped hyperbolic 3-manifolds
• A survey about Hidden Subgroup Problem from a mathematical and cryptographic perspective
• Average hardness of SIVP for module lattices of fixed rank
• Fine-grained deterministic hardness of the shortest vector problem
• Deterministic list decoding of Reed-Solomon codes
• SVP_p is Deterministically NP-Hard for all p > 2, Even to Approximate Within a Factor of 2^log^1-ε n
• Hesse's Redemption: Efficient Convex Polynomial Programming
• Message Recovery Attack in NTRU via Knapsack
• Model Inversion Attacks Meet Cryptographic Fuzzy Extractors
• Bit retrieval: intractability and application to digital watermarking
• A hierarchy of polynomial time lattice basis reduction algorithms
• Quantized Compute and Forward: A Low-Complexity Architecture for Distributed Antenna Systems
• Lattice Identification and Separation: Theory and Algorithm
• Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases
• A Polynomial Time Version of LLL With Deep Insertions
• Lattice Reduction over Imaginary Quadratic Fields
• Some New Applications of Toric Geometry
• A Probabilistic Computing Approach to the Closest Vector Problem for Lattice-Based Factoring
• Traveling Salesman-Based Token Ordering Improves Stability in Homomorphically Encrypted Language Models
• Recovery of Integer Images from Limited DFT Measurements with Lattice Methods
• Approximations of generating functions and a few conjectures
• NoMod: A Non-modular Attack on Module Learning With Errors
• Predicting Module-Lattice Reduction
• Simultaneous Integer Relation Detection and Its an Application
• Parallel Spooky Pebbling Makes Regev Factoring More Practical
• TAPAS: Datasets for Learning the Learning with Errors Problem
• Conic optimization for extremal geometry
• Ratios of two powers of van der Laan-Padovan numbers
• An efficient quantum algorithm for computing S-units and its applications
• On Computing the Copositive Minimum and its Representatives
• Computational approach to compact Riemann surfaces
• On concatenations of two k-generalized Lucas numbers
• Toward the Analytic Bootstrap of Energy Correlators
• Are Neural Networks Collision Resistant?
• Rational and isolated quadratic points on hyperelliptic curves of rank 0 and small genus
• Reduction Theory of Algebraic Modules and their Successive Minima
• A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants
• Solving S-unit, Mordell, Thue, Thue-Mahler and generalized\n Ramanujan-Nagell equations via Shimura-Taniyama conjecture
• Theta invariants and Lattice-Point Counting in Normed ℤ-Modules
• Cryptanalysis of a New Knapsack Type Public-Key Cryptosystem
• Deterministic polynomial factorisation modulo many primes
• TPM-FAIL: TPM meets Timing and Lattice Attacks
• Minimizing Convex Functions with Rational Minimizers
• Factoring sparse polynomials fast
• Computing Igusa's Local Zeta Functions of Univariate Polynomials, and Linear Feedback Shift Registers
• Iterative Partition Search Variational Quantum Algorithm for Solving Shortest Vector Problem
• Classical Cryptosystems In A Quantum Setting
• Is Lattice Reduction Necessary for Vector Perturbation Precoding?
• A Threshold Phenomenon for the Shortest Lattice Vector Problem in the Infinity Norm
• A Relax-and-Round Approach to Complex Lattice Basis Reduction
• Computing Arakelov class groups
• The Geometry of LLM Quantization: GPTQ as Babai's Nearest Plane Algorithm