Factoring polynomials with rational coefficients

DOI10.1007/BF01457454zbMath0488.12001WikidataQ56210589 ScholiaQ56210589MaRDI QIDQ1165896

László Lovász, Arjen K. Lenstra, Hendrik W. jun. Lenstra

Publication date: 1982

Published in: Mathematische Annalen (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/182903

zbMATH Keywords

cryptography polynomial-time algorithm diophantine approximation operations research lattice basis reduction algorithm factorization of primitive polynomials

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Polynomials in number theory (11C08) Polynomials (irreducibility, etc.) (11R09)

Related Items

Computing theta functions with Julia, Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance, The inapproximability of lattice and coding problems with preprocessing, Shrinking integer lattices, On the orthogonality of the Chebyshev-Frolov lattice and applications, Matrix product constraints by projection methods, Lattice-based algorithms for number partitioning in the hard phase, LLL-reduction for integer knapsacks, An even extremal lattice of rank 64, Cryptanalytic results on `Dual CRT' and `Common Prime' RSA, Computing sparse multiples of polynomials, 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, Three-loop anomalous dimension of the non-singlet transversity operator in QCD, 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, Approximating the SVP to within a factor $(1+1/\dim^\varepsilon)$ is NP-hard under randomized reductions, On membership comparable sets, Further improvement of factoring $N=p^rq^s$ with partial known bits, A generalized attack on some variants of the RSA cryptosystem, Partial key exposure attacks on RSA: achieving the Boneh-Durfee bound, Thinner is not always better: cascade knapsack problems, Computing subfields of number fields and applications to Galois group computations, The complexity of computing all subfields of an algebraic number field, Functor of points and height functions for noncommutative Arakelov geometry, Stable presentation length of 3-manifold groups, A verified implementation of the Berlekamp-Zassenhaus factorization algorithm, Solving the FCSR synthesis problem for multi-sequences by lattice basis reduction, On the optimality of lattices for the Coppersmith technique, Second order statistical behavior of LLL and BKZ, A public-key encryption scheme based on non-linear indeterminate equations, Approximate short vectors in ideal lattices of $\mathbb{Q}(\zeta_{p^e})$ with precomputation of ${\mathrm {Cl}}(\mathcal{O}_K)$, A semidefinite programming method for integer convex quadratic minimization, Polynomial computability of fields of algebraic numbers, FPT-algorithms for some problems related to integer programming, Partial strategyproofness: relaxing strategyproofness for the random assignment problem, Coppersmith's lattices and ``focus groups: an attack on small-exponent RSA, Deterministic polynomial factoring over finite fields: a uniform approach via $\mathcal{P}$-schemes, Solving market split problems with heuristical lattice reduction, Analysis of DeepBKZ reduction for finding short lattice vectors, Deterministic normal position transformation and its applications, On the Diophantine equation $\binom{n}{k} = \binom{m}{l} + d$, Small CRT-exponent RSA revisited, Uniform rates of approximation by short asymptotic expansions in the CLT for quadratic forms, New number-theoretic cryptographic primitives, Short principal ideal problem in multicubic fields, Algorithms for CRT-variant of approximate greatest common divisor problem, Finding small solutions of the equation $Bx-Ay=z$ and its applications to cryptanalysis of the RSA cryptosystem, Indiscreet logarithms in finite fields of small characteristic, Improved attacks on knapsack problem with their variants and a knapsack type ID-scheme, Noisy polynomial interpolation modulo prime powers, The shortest vector problem and tame kernels of cyclotomic fields, Numerical performance of optimized Frolov lattices in tensor product reproducing kernel Sobolev spaces, Approximating rings of integers in number fields, Quantum algorithms for computing general discrete logarithms and orders with tradeoffs, On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond, Approximate CVP$_p$ in time $2^{0.802n}$, A Lucas-Lehmer approach to generalised Lebesgue-Ramanujan-Nagell equations, A $2^{n/2}$-time algorithm for $\sqrt{n} $-SVP and $\sqrt{n} $-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP, On bounded distance decoding with predicate: breaking the ``lattice barrier for the hidden number problem, On the ideal shortest vector problem over random rational primes, The convergence of slide-type reductions, On the success probability of solving unique SVP via BKZ, Rank and border rank of Kronecker powers of tensors and Strassen's laser method, Lattice size and generalized basis reduction in dimension three, Algorithmically solving the tadpole problem, Decomposing algebraic sets using Gröbner bases, LLL $\and$ ABC, Noisy Chinese remaindering in the Lee norm, Calculating ``small solutions of inhomogeneous relative Thue inequalities, The tadpole problem, On the construction of the finite simple groups with a given centralizer of a 2-central involution, A deterministic algorithm for finding $r$-power divisors, Exact result in $\mathcal{N} = 4$ SYM theory: generalised double-logarithmic equation, A polynomial-time algorithm for solving the hidden subset sum problem, Fast reduction of algebraic lattices over cyclotomic fields, Faster enumeration-based lattice reduction: root Hermite factor $k^{1/(2k)}$ time $k^{k/8+o(k)}$, Lattice reduction for modules, or how to reduce ModuleSVP to ModuleSVP, Slide reduction, revisited -- filling the gaps in SVP approximation, Random lattices, threshold phenomena and efficient reduction algorithms., A lattice-based public-key cryptosystem, Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio, Simple periodic boundary conditions for molecular simulation of uniaxial flow, A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor, Computing the primary decomposition of zero-dimensional ideals, BBP-type formulas -- an elementary approach, A physical study of the LLL algorithm, Deep learning Gauss-Manin connections, A practical algorithm for completing half-Hadamard matrices using LLL, Search for combinatorial objects using lattice algorithms -- revisited, Short simplex paths in lattice polytopes, Generating cryptographically-strong random lattice bases and recognizing rotations of $\mathbb{Z}^n$, Revisiting orthogonal lattice attacks on approximate common divisor problems, On Lovász' lattice reduction and the nearest lattice point problem, On the period matrix of a Riemann surface of large genus (with an appendix by J. H. Conway and N. J. A. Sloane), Connected components of the moduli of elliptic $K3$ surfaces, A strongly polynomial minimum cost circulation algorithm, Factoring sparse multivariate polynomials, Fast parallel absolute irreducibility testing, Algorithms to construct Minkowski reduced and Hermite reduced lattice bases, Irreducibility of multivariate polynomials, Polymorphic arrays: A novel VLSI layout for systolic computers, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Strongly polynomial algorithm for a class of combinatorial LCPs, Distribution of Hermite's constant and the shortest vector in lattices of dimension two, Cryptanalysis of a public key cryptosystem based on Diophantine equations via weighted LLL reduction, Return of GGH15: provable security against zeroizing attacks, 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, On the hardness of the computational ring-LWR problem and its applications, A modification of the LLL reduction algorithm, Factorization properties of lattices over the integers, Twist-2 at seven loops in planar $ \mathcal{N} =4$ SYM theory: full result and analytic properties, Factoring polynomials and primitive elements for special primes, Planckian axions and the weak gravity conjecture, Factoring multivariate integral polynomials, Computer algebra: Past and future, An application of simultaneous diophantine approximation in combinatorial optimization, A hierarchy of polynomial time lattice basis reduction algorithms, The hardness of approximate optima in lattices, codes, and systems of linear equations, The existence of simple $6\text{-}(14,7,4)$ designs, Solving norm form equations via lattice basis reduction, Diophantine approximation of matrices, Fiat-Shamir and correlation intractability from strong KDM-secure encryption, Shortest vector from lattice sieving: a few dimensions for free, An inequality about irreducible factors of integer polynomials, Solving a class of modular polynomial equations and its relation to modular inversion hidden number problem and inversive congruential generator, Polar varieties, real equation solving, and data structures: the hypersurface case, Dual vectors and lower bounds for the nearest lattice point problem, On the practical solution of the Thue equation, Real data-integer solution problems within the Blum-Shub-Smale computational model, Existence theorems in mathematics, Segment LLL reduction of lattice bases using modular arithmetic, The iterated mod problem, Simultaneously good bases of a lattice and its reciprocal lattice, Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness, Straight-line programs in geometric elimination theory, Computational complexity of the landscape. I., Factoring bivariate sparse (lacunary) polynomials, Finding shortest lattice vectors faster using quantum search, A polynomial time algorithm for GapCVPP in $l_1$ norm, The three-loop splitting functions in QCD: the helicity-dependent case, The optimal LLL algorithm is still polynomial in fixed dimension., Tile invariants: New horizons., The better bound of private key in RSA with unbalanced primes, On computing the intersection of a pair of algebraic surfaces, Computing the sign or the value of the determinant of an integer matrix, a complexity survey., Algorithms for sentences over integral domains, Complexity of computations in Commutative Division of the USSR Academy of Sciences, Approximate factorization of multivariate polynomials and absolute irreducibility testing, Computational complexity of sentences over fields, A heuristic irreducibility test for univariate polynomials, Polynomial time algorithms for sentences over number fields, An application of lattice basis reduction to polynomial identities for algebraic structures, A note on the $f$-factor-lattice of bipartite graphs, Improved low-density subset sum algorithms, Covering and packing in ${\mathbb Z^n}$ and ${\mathbb R^n}$. II, Quadratic compact knapsack public-key cryptosystem, Cryptanalysis of RSA with two decryption exponents, Cryptanalysis of RSA with more than one decryption exponent, Optimal routing in double loop networks, Valid inequalities for mixed integer linear programs, Lattice-based treshold-changeability for standard CRT secret-sharing schemes, 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 interpolating arithmetic read-once formulas with exponentiation, On asymptotic extrapolation, A relation of primal--dual lattices and the complexity of shortest lattice vector problem, The number of roots of a lacunary bivariate polynomial on a line, Factoring polynomials over global fields, On the solution of units and index form equations in algebraic number fields, On selecting a maximum volume sub-matrix of a matrix and related problems, The hyperelliptic integrals and $\pi $, Sentences over integral domains and their computational complexities, On the limits of nonapproximability of lattice problems, New $t$-designs and large sets of $t$-designs, Improved nonlinear multiuser precoding using lattice reduction, Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey, Renormalization automated by Hopf algebra, Complexity of the Havas, Majewski, Matthews LLL Hermite normal form algorithm, Simultaneous reduction of a lattice basis and its reciprocal basis, Recognizing badly presented $Z$-modules, Approximate solutions of polynomial equations., An upper bound on the average number of iterations of the LLL algorithm, Factoring multivariate polynomials over finite fields, Short vectors of planar lattices via continued fractions, The chords' problem, An algorithm for finding a shortest vector in a two-dimensional modular lattice, A partial digest approach to restriction site mapping, Solvability by radicals is in polynomial time, Approximating $SVP_{\infty}$ to within almost-polynomial factors is NP-hard, Computation and rationality of Belyi functions in genus zero, A parallel search for good lattice points using LLL-spectral tests, Information transfer fidelity in spin networks and ring-based quantum routers, On random nonsingular Hermite normal form, Torsion part of $\mathbb{Z}$-module, Solving polynomial systems in integers, On algorithms to find $p$-ordering, A fixed point iterative approach to integer programming and its distributed computation, Reflections on termination of linear loops, Column basis reduction and decomposable knapsack problems, New lattice attacks on DSA schemes, The SIAM 100-Digit Challenge: a decade later. Inspirations, ramifications, and other eddies left in its wake, Searching for good two-term fifth-order multiple recursive random number generators, Factors of low individual degree polynomials, Classification of symmetric toroidal orbifolds, Algorithms for near solutions to polynomial equations, Divisible $\mathbb{Z}$-modules, Lattice of $\mathbb{Z}$-module, The absolute trace of totally positive reciprocal algebraic integers, Software for the Gale transform of fewnomial systems and a Descartes rule for fewnomials, Practical cryptanalysis of ISO 9796-2 and EMV signatures, An efficient lattice reduction using reuse technique blockwisely on NTRU, Lattice based extended formulations for integer linear equality systems, Probability method for cryptanalysis of general multivariate modular linear equation, On multidimensional Diophantine approximation of algebraic numbers, Harmonic divisors and rationality of zeros of Jacobi polynomials, An efficient algorithm for factoring polynomials over algebraic extension field, Deformation techniques to solve generalised Pham systems, A quasi quadratic time algorithm for hyperelliptic curve point counting, Modular Las Vegas algorithms for polynomial absolute factorization, Practical strategies for generating rank-1 split cuts in mixed-integer linear programming, Comments on the height reducing property, The multiple zeta value data mine, Correcting noisy exponentiation black-boxes modulo a prime, PotLLL: a polynomial time version of LLL with deep insertions, Small secret exponent attack on RSA variant with modulus $N=p^rq$, Bounds for solid angles of lattices of rank three, Six-loop anomalous dimension of twist-three operators in $\mathcal{N} = 4$ SYM, Non-linear polynomial selection for the number field sieve, Faster $p$-adic feasibility for certain multivariate sparse polynomials, Loop-reduction LLL algorithm and architecture for lattice-reduction-aided MIMO detection, A note on Gao's algorithm for polynomial factorization, Some lattice attacks on DSA and ECDSA, Hardness of approximating the closest vector problem with pre-processing, Simplicial volume and fillings of hyperbolic manifolds, On reducing factorization to the discrete logarithm problem modulo a composite, Is every matrix similar to a polynomial in a companion matrix?, Splitting full matrix algebras over algebraic number fields., Another 80-dimensional extremal lattice, Rational points on curves, Proper reparametrization for inherently improper unirational varieties, Approximate polynomial GCD over integers, Proving termination of nonlinear command sequences, Sparse bivariate polynomial factorization, Reduction theory of point clusters in projective space, ETRU: NTRU over the Eisenstein integers, A simple rederivation of Onsager's solution of the 2D Ising model using experimental mathematics, Proving inequalities and solving global optimization problems via simplified CAD projection, LLL for ideal lattices: re-evaluation of the security of Gentry-Halevi's FHE scheme, Lower bounds for heights on finitely generated groups, Rational orthogonal approximations to orthogonal matrices, Large-$n_{f}$ contributions to the four-loop splitting functions in QCD, A generalization of the LLL-algorithm over Euclidean rings or orders, A hybrid symbolic-numerical approach to the center-focus problem, Analysis of decreasing squared-sum of Gram-Schmidt lengths for short lattice vectors, On the path-width of integer linear programming, Cryptanalysis of Dual RSA, Factorization of solvable polynomials over finite fields and the generalized Riemann hypothesis, Decomposition of algebras over finite fields and number fields, A unified method for multivariate polynomial factorizations, On a smooth quartic surface containing 56 lines which is isomorphic as a $K3$ surface to the Fermat quartic, On periodicity of geodesic continued fractions, Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices, Non-standard approaches to integer programming, Branching on general disjunctions, Factoring polynomials and the knapsack problem, Multivariate Gabor frames and sampling of entire functions of several variables, Cryptanalysis of a quadratic knapsack cryptosystem, A new exceptional polynomial for the integer transfinite diameter of $[0,1$], Topics in computational algebraic number theory, Some inequalities related to the Seysen measure of a lattice, Isomorphisms of algebraic number fields, The inverse moment problem for convex polytopes, Solving exponential diophantine equations using lattice basis reduction algorithms, On finite-precision representations of geometric objects, An experimental comparison of some LLL-type lattice basis reduction algorithms, Parallel Cholesky-based reduction for the weighted integer least squares problem, Cryptanalysis of a knapsack-based probabilistic encryption scheme, Decomposing homogeneous modules of finite groups in characteristic zero., Nonhomogeneous subalgebras of Lie and special Jordan superalgebras, Numerical elimination and moduli space of vacua, Low-cost addition-subtraction sequences for the final exponentiation in pairings, Optimized frames and multi-dimensional challenges in time-frequency analysis, Four-dimensional Gallant-Lambert-Vanstone scalar multiplication, Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice, Fields of algebraic numbers computable in polynomial time. I, Modular polynomials on Hilbert surfaces, Integer programming and cryptography, On the resolution of index form equations in biquadratic number fields. II, Complexity of factoring and calculating the GCD of linear ordinary differential operators, Revisiting prime power RSA, A Unified Framework for Small Secret Exponent Attack on RSA, Faster Hashing to ${\mathbb G}_2$, A partial exhaustive search for good two-term third-order multiple recursive random number generators, Perturbation Analysis of the QR factor R in the context of LLL lattice basis reduction, Cryptanalysis of an RSA variant with moduli $N=p^r q^l$, Improved hardness results for unique shortest vector problem, Bounded-degree factors of lacunary multivariate polynomials, Six-loop anomalous dimension of twist-two operators in planar $ \mathcal{N}=4 $ SYM theory, Computing with characters of finite groups, Solving conics over functions fields, A relative van Hoeij algorithm over number fields, Polynomial factorization algorithms over number fields, A note on the concrete hardness of the shortest independent vector in lattices, Scalable revocable identity-based signature over lattices in the standard model, Remarks on the cryptanalysis of common prime RSA for IoT constrained low power devices, A Fast Phase-based Enumeration Algorithm for SVP Challenge Through $$y$$-Sparse Representations of Short Lattice Vectors, Moduli spaces and the inverse Galois problem for cubic surfaces, Partial Key Exposure Attack on CRT-RSA, A Low Data Complexity Attack on the GMR-2 Cipher Used in the Satellite Phones, New Attacks on RSA with Moduli N = p r q, Factoring RSA Moduli with Weak Prime Factors, A New Partial Key Exposure Attack on Multi-power RSA, Improving small private exponent attack on the Murru-Saettone cryptosystem, Lattice Point Enumeration on Block Reduced Bases, Attacking the linear congruential generator on elliptic curves via lattice techniques, Abelian lifts of polynomials, Cryptographic Applications of Capacity Theory: On the Optimality of Coppersmith’s Method for Univariate Polynomials, Computational approach to compact Riemann surfaces, Polynomial-time data reduction for weighted problems beyond additive goal functions, Lower bounds on the size of general branch-and-bound trees, Objective molecular dynamics for atomistic simulation of macroscopic fluid motion, Improving convergence and practicality of slide-type reductions, On completely factoring any integer efficiently in a single run of an order-finding algorithm, Towards classical hardness of module-LWE: the linear rank case, Twisted-PHS: using the product formula to solve approx-SVP in ideal lattices, Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting), Computation of Hurwitz spaces and new explicit polynomials for almost simple Galois groups, Cullen numbers in sums of terms of recurrence sequence, Computing torsion subgroups of Jacobians of hyperelliptic curves of genus 3, Picard curves over with good reduction away from 3, Algorithms for the approximate common divisor problem, A lattice reduction algorithm based on sublattice BKZ, On the (M)iNTRU assumption in the integer case, The irreducible vectors of a lattice: some theory and applications, Additive Diophantine equations with binary recurrences, $\mathcal{S}$-units and several factorials, An improved method for predicting truncated multiple recursive generators with unknown parameters, A Tool Kit for Partial Key Exposure Attacks on RSA, An Improved Analysis on Three Variants of the RSA Cryptosystem, Cryptanalysis of a Homomorphic Encryption Scheme Over Integers, Partial Bits Exposure Attacks on a New Commitment Scheme Based on the Zagier Polynomial, Improved Results on Cryptanalysis of Prime Power RSA, Algorithms for the Shortest and Closest Lattice Vector Problems, An Experiment of Number Field Sieve over GF(p) of Low Hamming Weight Characteristic, A backward heuristic algorithm for two-term multiple recursive random number generators, Using the Inhomogeneous Simultaneous Approximation Problem for Cryptographic Design, Existence of primitive divisors of Lucas and Lehmer numbers, General Theory for Integer-Type Algorithm for Higher Order Differential Equations, Security of the most significant bits of the Shamir message passing scheme, La réduction des réseaux. Autour de l'algorithme de Lenstra, Lenstra, Lovász, Fast LLL-type lattice reduction, Hardness of approximating the shortest vector problem in high $\ell_{p}$ norms, Theory of computational complexity. Part 9. Transl. from the Russian., Some computations on the spectra of Pisot and Salem numbers, An Implementation of the Number Field Sieve, Solving resultant form equations over number fields, Constructing multidimensional periodic continued fractions in the sense of Klein, Computation of highly ramified coverings, Just a Little Bit More, Finding Shortest Lattice Vectors in the Presence of Gaps, On the determinant of an integral lattice generated by rational approximants of the Euler constant, How to pick a random integer matrix? (and other questions), Partial Key Exposure Attacks on CRT-RSA: Better Cryptanalysis to Full Size Encryption Exponents, Improvement of Lattice-Based Cryptography Using CRT, Simplification of the Lattice Based Attack of Boneh and Durfee for RSA Cryptoanalysis, The Diagonal Reduction Algorithm Using Fast Givens, Character Varieties For : The Figure Eight Knot, Post-Quantum Cryptography: State of the Art, Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding, On shifted Eisenstein polynomials, Towards Optimal Bounds for Implicit Factorization Problem, Peak-power reduction by the lattice-reduction-aided closest point search for MIMO broadcast channels, Quantum algorithms for algebraic problems, Analysis of Gauss-Sieve for Solving the Shortest Vector Problem in Lattices, Automated discovery and proof of congruence theorems for partial sums of combinatorial sequences, Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields, Partial Key Exposure Attacks on RSA with Multiple Exponent Pairs, Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle, Collision-Free Hashing from Lattice Problems, Numerical calculation of three-point branched covers of the projective line, A Subfield Lattice Attack on Overstretched NTRU Assumptions, A bound for the degree of a system of equations determining the variety of reducible polynomials, Cryptanalysis of large RSA exponent by using the LLL algorithm, Advanced determinant calculus: a complement, Some necessary clarifications about the chords' problem and the partial digest problem, Improved results on the Mertens conjecture, SLIDE REDUCTION, SUCCESSIVE MINIMA AND SEVERAL APPLICATIONS, A sieve algorithm based on overlattices, Approximating the densest sublattice from Rankin’s inequality, Constructing abelian surfaces for cryptography via Rosenhain invariants, Nonvanishing of twists of -functions attached to Hilbert modular forms, Bounding basis reduction properties, Towards faster polynomial-time lattice reduction, A trace map attack against special ring-LWE samples, Efficient hash maps to $\mathbb{G}_2$ on BLS curves, Computing sum of squares decompositions with rational coefficients, Classical attacks on a variant of the RSA cryptosystem, Solving the search-LWE problem over projected lattices, Low-density attack revisited, An extension of Kannan's embedding for solving ring-based LWE problems, A knapsack-based probabilistic encryption scheme, A new approach for finding low-weight polynomial multiples, On a dual/hybrid approach to small secret LWE. A dual/enumeration technique for learning with errors and application to security estimates of FHE schemes, Attacks on pseudo random number generators hiding a linear structure, Lattice-based fault attacks on deterministic signature schemes of ECDSA and EdDSA, Complexity of integer quasiconvex polynomial optimization, Cryptanalysis of RSA variants with primes sharing most significant bits, Application of automorphic forms to lattice problems, Oscillations in the Goldbach conjecture, Efficient algorithms for discrete lattice calculations, Post-quantum cryptography: lattice signatures, Approximate CVP in time $2^{0.802 n}$ -- now in any norm!, Ciphertext-only attacks against compact-LWE submitted to NIST PQC project, Certifying solutions to overdetermined and singular polynomial systems over $\mathbb{Q}$, Property-preserving hash functions for Hamming distance from standard assumptions, On the lattice isomorphism problem, quadratic forms, remarkable lattices, and cryptography, Dual lattice of $\mathbb{Z}$-module lattice, Obfuscated fuzzy Hamming distance and conjunctions from subset product problems, Lattices with symmetry, Analytic properties of spherical cusp forms on $\mathrm{GL}(n)$, Revisiting approximate polynomial common divisor problem and noisy multipolynomial reconstruction, On the smoothing parameter and last minimum of random orthogonal lattices, Predicting truncated multiple recursive generators with unknown parameters, Estimation of the hardness of the learning with errors problem with a restricted number of samples, Solving low-density multiple subset sum problems with SVP oracle, Data science applications to string theory, Abstract tropical linear programming, Self-dual DeepBKZ for finding short lattice vectors, A subexponential-time, polynomial quantum space algorithm for inverting the CM group action, Efficient computation of multidimensional theta functions, A polynomial algorithm for minimizing discrete convic functions in fixed dimension, New orthogonality criterion for shortest vector of lattices and its applications, On the complexity of quasiconvex integer minimization problem, Gradual sub-lattice reduction and a new complexity for factoring polynomials, A pivoted LLL algorithm, Computation of Darboux polynomials and rational first integrals with bounded degree in polynomial time, Spectral test of the MIXMAX random number generators, Extended partial key exposure attacks on RSA: improvement up to full size decryption exponents, MLAMBDA: a modified LAMBDA method for integer least-squares estimation, On post-processing in the quantum algorithm for computing short discrete logarithms, Recovering a sum of two squares decomposition, Guessing singular dependencies, Explicit rates of approximation in the CLT for quadratic forms, Formalizing the LLL basis reduction algorithm and the LLL factorization algorithm in Isabelle/HOL, The complexity of LSH feasibility, The upper density of an automatic set is rational, Limits of a conjecture on a leakage-resilient cryptosystem, On minimum integer representations of weighted games, Towards factoring in $\mathrm{SL}(2,\mathbb F_{2^n})$, Privately outsourcing exponentiation to a single server: cryptanalysis and optimal constructions, Factoring polynomials over global fields. I, Factoring polynomials over global fields. II., Computation of unirational fields, Irreducible constituents of monomial representations., Around the numeric-symbolic computation of differential Galois groups, Storage efficient algorithm for Hermite normal form using LLL, Efficiently factoring polynomials modulo $p^4$, Dynamic self-dual DeepBKZ lattice reduction with free dimensions and its implementation, Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification, Cryptanalysis of the RSA variant based on cubic Pell equation, Non-planar universal anomalous dimension of twist-two operators with general Lorentz spin at four loops in $\mathcal{N} = 4$ SYM theory, An improved LLL algorithm, The projection games conjecture and the hardness of approximation of Super-SAT and related problems, Simple $8$-$(31,12,3080)$, $8$-$(40,12,16200)$ and $8$-$(40,12,16520)$ designs from $\mathrm{PSL}(3,5)$ and $\mathrm{PSL}(4,3)$, Algebraic solutions to the connectivity problem for $m$-way layouts: Interaction-contrast ali\-asing, List decoding of number field codes, Lattice preconditioning for the real relaxation branch-and-bound approach for integer least squares problems, Sparse non-negative stencils for anisotropic diffusion, Geodesic continued fractions and LLL, Complexity of solving parametric polynomial systems, Reduction of Smith normal form transformation matrices, Detecting squarefree numbers, Cryptanalysis of RSA for a special case with $d > e$, Reconstruction algorithms for sums of affine powers, Cryptanalysis of elliptic curve hidden number problem from PKC 2017, Principal symmetric space analysis, A stochastic variant of the abelian sandpile model, Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes, On simultaneous approximation in quadratic integer programming, The complexity of solving low degree equations over ring of integers and residue rings, A probabilistic analysis on a lattice attack against DSA, A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram-Schmidt lengths, Generalized cryptanalysis of small CRT-exponent RSA, A new parallel lattice reduction algorithm for BKZ reduced bases, Implicit factorization of unbalanced RSA moduli, A note on BDD problems with $\lambda_2$-gap, Equivalence of polynomial identity testing and polynomial factorization, Formally verified certificate checkers for hardest-to-round computation, The remote set problem on lattices, Torsion $\mathbb Z$-module and torsion-free $\mathbb Z$-module, Embedded lattice and properties of Gram matrix, Complexity results for some eigenvector problems, Special values of multiple polylogarithms, Polynomials with Height 1 and Prescribed Vanishing at 1, Anomaly-free sets of fermions, Three-Dimensional Presentations for the Groups of Order at Most 30, Efficient lattice assessment for LCG and GLP parameter searches, Factoring multivariate polynomials via partial differential equations, On the linear independence measure of logarithms of rational numbers, Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the gaussian integer method, Computing points of bounded height in projective space over a number field, Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes, Attacking RSA with a Composed Decryption Exponent Using Unravelled Linearization, Attacking (EC)DSA Given Only an Implicit Hint, Lattice Reduction for Modular Knapsack, Hidden number problem with hidden multipliers, timed-release crypto, and noisy exponentiation, Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing, An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices, Cryptanalysis of the Co-ACD Assumption, On asymptotic complexity of computing discrete logarithms over GF(p), Complex Dimensions of Self-Similar Fractal Strings and Diophantine Approximation, Computing Riemann theta functions, TOPICS IN DIVISIBILITY: PAIRWISE COPRIMALITY, THE GCD OF SHIFTED SETS AND POLYNOMIAL IRREDUCIBILITY, Period computations for covers of elliptic curves, Recovering zeros of polynomials modulo a prime, Factorization of ℤ$$ \mathbb {Z}$$-Homogeneous Polynomials in the First q-Weyl Algebra, Class numbers of large degree nonabelian number fields, Polynomials with Restricted Coefficients and Prescribed Noncyclotomic Factors, Algorithms in Algebraic Number Theory, Experimental Math for Math Monthly Problems, Factorisation sur $\mathbb {Z}[X$ des polynômes de degré élevé à l’aide d’un monomorphisme], A polynomial reduction algorithm, Experimental Evaluation of Euler Sums, S-integral points on elliptic curves, Another Generalization of Wiener’s Attack on RSA, Block Reduced Lattice Bases and Successive Minima, Efficient Modular Arithmetic in Adapted Modular Number System Using Lagrange Representation, Block Systems of a Galois Group, An extension of a result about divisors in a residue class and its application to reducing integer factorization to computing Euler’s totient, Faster individual discrete logarithms in finite fields of composite extension degree, Rigorous computation of the endomorphism ring of a Jacobian, The PSLQ algorithm for empirical data, Explicit Hard Instances of the Shortest Vector Problem, Thrackles: An Improved Upper Bound, The Reductions for the Approximating Covering Radius Problem, A Lattice Attack on Homomorphic NTRU with Non-invertible Public Keys, An Experimental Study of Kannan’s Embedding Technique for the Search LWE Problem, Lattice-Based Fault Attacks Against ECMQV, Integer Reconstruction Public-Key Encryption, Implicit Related-Key Factorization Problem on the RSA Cryptosystem, First Study for Ramp Secret Sharing Schemes Through Greatest Common Divisor of Polynomials, Enumeration of Quartic Fields of Small Discriminant, Heeke Eigenforms in the Cohomology of Congruence Subgroups of SL(3, Z), A family of trapdoor ciphers, On the Diophantine equation |𝑎𝑥ⁿ-𝑏𝑦ⁿ|=1, New Computations of the Riemann Zeta Function on the Critical Line, Application of ECM to a class of RSA keys, Solving a Specific Thue-Mahler Equation, An optimal, stable continued fraction algorithm for arbitrary dimension, Prime values of polynomials and irreducibility testing, A natural lattice basis problem with applications, A deterministic version of Pollard’s $p-1$ algorithm, Improved Rounding for Spline Coefficients and Knots, The Solution of Triangularly Connected Decomposable Form Equations, Predicting nonlinear pseudorandom number generators, A multidimensional continued fraction based on a high-order recurrence relation, Symplectic Lattice Reduction and NTRU, Cryptanalysis of General Lu-Lee Type Systems, Rigorous and Efficient Short Lattice Vectors Enumeration, Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits, The Hidden Root Problem, Finding well approximating lattices for a finite set of points, Conway subgroup symmetric compactifications of heterotic string, Identification and signatures based on NP-hard problems of indefinite quadratic forms, Factoring Multivariate Polynomials over Large Finite Fields, Improved Partial Key Exposure Attacks on RSA by Guessing a Few Bits of One of the Prime Factors, Solving Thue equations without the full unit group, Hard and Easy Components of Collision Search in the Zémor-Tillich Hash Function: New Attacks and Reduced Variants with Equivalent Security, Применение теории решеток к анализу схем цифровой подписи, A note on solving linear Diophantine systems by usingL³-reduction algorithm, K3 surfaces with non-symplectic involution and compact irreducible G₂-manifolds, A Polynomial with Galois Groups SL₂(F₁₆), Polynomial identities for the ternary cyclic sum, Unnamed Item, Partial Key Exposure: Generalized Framework to Attack RSA, Integer Sets with Distinct Subset-Sums, NATURAL EXISTENCE PROOF FOR LYONS SIMPLE GROUP, Reconstructing Algebraic Functions from Mixed Data, A Polynomial Time Complexity Bound for Computations on Curves, Practical Implementation and Error Bound of Integer-Type Algorithm for Higher-Order Differential Equations, The monic integer transfinite diameter, Lattice basis reduction, Jacobi sums and hyperelliptic cryptosystems, An experiment of number field sieve for discrete logarithm problem over $\text{GF}(p^n)$, Application of mixed integer quadratic program to shortest vector problems, Analysis of PSLQ, an integer relation finding algorithm, On the Computation of Totally Real Quartic Fields of Small Discriminant, Extended GCD and Hermite Normal Form Algorithms via Lattice Basis Reduction, O'NAN GROUP UNIQUELY DETERMINED BY THE CENTRALIZER OF A 2-CENTRAL INVOLUTION, Computing Arithmetic Invariants of 3-Manifolds, Optimization problems with algebraic solutions: Quadratic fractional programs and ratio games, Commutative images of rational languages and the Abelian kernel of a monoid, Cryptanalysis of NTRU where the private polynomial has one or more consecutive zero coefficients, Meta-heuristic approaches to solve shortest lattice vector problem, ON THE CLOSURE OF A LATTICE IN THE FIELD OF COMPLEX NUMBERS, Evaluating the Cache Side Channel Attacks Against ECDSA, The Power of Leibniz-Like Functions as Oracles, Etude Algorithmique de Réseaux Construits avec la Forme Trace, Majoration de la norme des facteurs d'un polynôme : cas où toutes les racines du polynôme sont réelles, Higher-rank pointwise discrepancy bounds and logarithm laws for generic lattices, Cryptanalysis of Prime Power RSA with two private exponents, On the coefficients of the polynomial in the number field sieve, Diophantine equations coming from binomial near-collisions, A Tale of Three Signatures: Practical Attack of ECDSA with wNAF, Recovering Exact Results from Inexact Numerical Data in Algebraic Geometry, Worst Cases for the Exponential Function in the IEEE 754r decimal64 Format, Elliptic curves over totally real quartic fields not containing √5 are modular, CALCULATING RELATIVE POWER INTEGRAL BASES IN TOTALLY COMPLEX QUARTIC EXTENSIONS OF TOTALLY REAL FIELDS, Exploiting the security of N = prqs through approximation of ϕ(N), On the Isogeny Problem with Torsion Point Information, Unnamed Item, Cloud-Assisted LLL: A Secure and Efficient Outsourcing Algorithm for Approximate Shortest Vector Problem, Efficient Nyberg-Rueppel type of NTRU digital signature algorithm, Lattice Identification and Separation: Theory and Algorithm, Unnamed Item, Computing all power integral bases in orders of totally real cyclic sextic number fields, Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP), Sampling of entire functions of several complex variables on a lattice and multivariate Gabor frames, A Parametric Version of LLL and Some Consequences: Parametric Shortest and Closest Vector Problems, How can we solve a linear Diophantine equation by the basis reduction algorithm, On the Consistent Path Problem, The distribution of $k$-free numbers, Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH, Unnamed Item, An efficient algorithm for clustered integer least squares problems, Lattice Reformulation Cuts, Generalized Gorshkov–Wirsing Polynomials and the Integer Chebyshev Problem, Lattice Algorithms for Compression Color Space Estimation in JPEG Images, An Optimization Problem for Lattices, Analysis on a generalized algorithm for the strong discrete logarithm problem with auxiliary inputs, Unnamed Item, Unnamed Item, Smallest Reduction Matrix of Binary Quadratic Forms, Short Bases of Lattices over Number Fields, Divisors in residue classes, constructively, The History of the LLL-Algorithm, Hermite’s Constant and Lattice Algorithms, LLL: A Tool for Effective Diophantine Approximation, Selected Applications of LLL in Number Theory, The van Hoeij Algorithm for Factoring Polynomials, Using LLL-Reduction for Solving RSA and Factorization Problems, The Geometry of Provable Security: Some Proofs of Security in Which Lattices Make a Surprise Appearance, Cryptographic Functions from Worst-Case Complexity Assumptions, LLL reduction and a conjecture of Gunnells, Unnamed Item, Solving Systems of Modular Equations in One Variable: How Many RSA-Encrypted Messages Does Eve Need to Know?, A Digital Signature Scheme Based on CVP ∞, A Numerical Transcendental Method in Algebraic Geometry: Computation of Picard Groups and Related Invariants, A polynomial-time complexity bound for the computation of the singular part of a Puiseux expansion of an algebraic function, Irreducibility testing over local fields, Using number fields to compute logarithms in finite fields, Orbit Computation for Atomically Generated Subgroups of Isometries of $\mathbb{Z}^n$, RSA Moduli with a Predetermined Portion: Techniques and Applications, Speeding-Up Lattice Reduction with Random Projections (Extended Abstract), Predicting Lattice Reduction, A Survey of Solving SVP Algorithms and Recent Strategies for Solving the SVP Challenge, Benchmark Problems for Phase Retrieval, Testing Isomorphism of Lattices over CM-Orders, Singular Value Decomposition of Complexes, On the Structure of Reduced Kernel Lattice Bases, Randomized polynomial-time root counting in prime power rings, Efficient Algorithms to Test Digital Convexity, Exact Semidefinite Programming Bounds for Packing Problems, Quantum Hardness of Learning Shallow Classical Circuits, Determination of all rational preperiodic points for morphisms of PN, Computing prime divisors in an interval, Bit complexity of computing solutions for symmetric hyperbolic systems of PDEs with guaranteed precision, An Efficient Quadratic Programming Relaxation Based Algorithm for Large-Scale MIMO Detection, Computing Power Series Expansions of Modular Forms, A tale of two omegas, Totally positive algebraic integers with small trace, Algorithmic Construction of Hurwitz Maps, Computing Maximal Copies of Polyhedra Contained in a Polyhedron, Computing algebraic numbers of bounded height, Extension of Brickell’S Algorithm for Breaking High Density Knapsacks, Linear relations of zeroes of the zeta-function, String Reconstruction from Substring Compositions, Cryptanalysis of Short Exponent RSA with Primes Sharing Least Significant Bits, Interpolation and Approximation of Polynomials in Finite Fields over a Short Interval from Noisy Values, A New Class of Weak Encryption Exponents in RSA, Oscillations in weighted arithmetic sums, Knapsack Public Key Cryptosystems and Diophantine Approximation, Solving Low Density Knapsacks, Evaluation of the Adleman Attack on Multiply Iterated Knapsack Cryptosystems, Calculating “Small” Solutions of Relative Thue Equations, Pseudorandom Functions: Three Decades Later, Empirical Determinations of Feynman Integrals Using Integer Relation Algorithms, Calculating Four-Loop Corrections in QCD, A Brief History of Pairings, Deciding Orthogonality in Construction-A Lattices, A new attack on RSA and Demytko’s elliptic curve cryptosystem, Forty years of attacks on the RSA cryptosystem: A brief survey, Salem numbers with minimal trace, Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring, Sampling the Riemann-theta Boltzmann machine, A new attack on some RSA variants, Branch-and-bound solves random binary IPs in poly$(n)$-time, Quantum mechanics of bipartite ribbon graphs: integrality, lattices and Kronecker coefficients, Flat Tori with Large Laplacian Eigenvalues in Dimensions up to Eight, NTRU Fatigue: How Stretched is Overstretched?, Lattice Sieving via Quantum Random Walks, A heuristic technique for decomposing multisets of non-negative integers according to the Minkowski sum, A study of lattice reformulations for integer programming, Algebraic number fields and the LLL algorithm, Complex hyperbolic and projective deformations of small Bianchi groups, New Sparse Multivariate Polynomial Factorization Algorithms over Integers, Individual discrete logarithm with sublattice reduction, Practical attacks on small private exponent RSA: new records and new insights, Higher polynomial identities for mutations of associative algebras, All shall FA-LLL: breaking CT-RSA 2022 and CHES 2022 infective countermeasures with lattice-based fault attacks, Order bounds for C2-finite sequences, Computational Number Theory, Past, Present, and Future, Just how hard are rotations of $\mathbb{Z}^n$? Algorithms and cryptography with the simplest lattice, On the hardness of the finite field isomorphism problem, An entropy-regularized ADMM for binary quadratic programming, From approximate to exact integer programming, Reconstructing points of superelliptic curves over a prime finite field, The hidden number problem with small unknown multipliers: cryptanalyzing MEGA in six queries and other applications, Counting rational points of a Grassmannian, ARTEMIS: \textit{ab initio} restructuring tool enabling the modelling of interface structures, Solving 𝑆-unit, Mordell, Thue, Thue–Mahler and Generalized Ramanujan–Nagell Equations via the Shimura–Taniyama Conjecture, A generalized attack on the multi-prime power RSA, EHNP strikes back: analyzing SM2 implementations, Solving LWR via BDD Strategy: Modulus Switching Approach, Finding points on elliptic curves with Coppersmith's method, A bivariate polynomial-based cryptographic hard problem and its applications, A polynomial time algorithm for breaking NTRU encryption with multiple keys, Further cryptanalysis of a type of RSA variants, Deterministic factoring with oracles, Representation of hypergeometric products of higher nesting depths in difference rings, Irrational Quantum Walks, Proving an execution of an algorithm correct?, Approximating the chromatic polynomial is as hard as computing it exactly, Subfield attacks on HSVP in ideal lattices, On the measurement and simulation of the BKZ behavior for $q$-ary lattices, Log-$\mathcal{S}$-unit lattices using explicit Stickelberger generators to solve approx ideal-SVP, On module unique-SVP and NTRU, Improving bounds on elliptic curve hidden number problem for ECDH key exchange, Fast hashing to $\mathbb{G}_2$ on pairing-friendly curves with the lack of twists, Development and analysis of massive parallelization of a lattice basis reduction algorithm, Discrepancy of arithmetic progressions in grids, Fast practical lattice reduction through iterated compression, Finding short integer solutions when the modulus is small, An Efficient Algorithm for Integer Lattice Reduction, On the hardness of the NTRU problem, Partial key exposure attack on short secret exponent CRT-RSA, Differential fault attack on Montgomery ladder and in the presence of scalar randomization, \textsc{Rings}: an efficient Java/Scala library for polynomial rings, A sharper lower bound on Rankin's constant, Methodologies of Symbolic Computation, Cryptanalysis of the multi-power RSA cryptosystem variant, Counting roots for polynomials modulo prime powers, On the construction of class fields, Faster integer multiplication using short lattice vectors, Inversion of Band-Limited Discrete Fourier Transforms of Binary Images: Uniqueness and Algorithms, A third is all you need: extended partial key exposure attack on CRT-RSA with additive exponent blinding, THE ABSOLUTE -MEASURE OF TOTALLY POSITIVE ALGEBRAIC INTEGERS, Lattice-based cryptography: a survey, The special case of cyclotomic fields in quantum algorithms for unit groups, The curious case of the half-half Bitcoin ECDSA nonces, Chiral matter multiplicities and resolution-independent structure in 4D F-theory models, Private AI: Machine Learning on Encrypted Data, Subfield algorithms for ideal- and module-SVP based on the decomposition group, Mathematics of computation through the lens of linear equations and lattices, Interactions of computational complexity theory and mathematics, Moduli space reconstruction and weak gravity, On the computation of modular forms on noncongruence subgroups, Finding smooth integers in short intervals using CRT decoding, Approximate CVP_p in Time 2^{0.802 n}, Foreword, Galois group computation for rational polynomials, Explicit Galois realization of transitive groups of degree up to 15, A polynomial with Galois group $\text{SL}_2(11)$, Factoring polynomials over finite fields: A survey, Short Generators Without Quantum Computers: The Case of Multiquadratics, Short Stickelberger Class Relations and Application to Ideal-SVP, Random Sampling Revisited: Lattice Enumeration with Discrete Pruning, Small CRT-Exponent RSA Revisited, On a transfer theorem for the $\text{P}\neq \text{NP}$ conjecture, Kronecker's and Newton's approaches to solving: a first comparison, Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy, Improvements in the analysis of Kannan's CVP algorithm, Linear programming using limited-precision oracles, On the reduction of a random basis, Deterministic Construction of an Approximate M-Ellipsoid and its Application to Derandomizing Lattice Algorithms, Faster Homomorphic Evaluation of Discrete Fourier Transforms, A Unified Method for Private Exponent Attacks on RSA Using Lattices, A Vectorized, Cache Efficient LLL Implementation, On ideal class group computation of imaginary multiquadratic fields, Saturation of finitely-generated submodules of free modules over Prüfer domains, The SAGEX review on scattering amplitudes Chapter 4: Multi-loop Feynman integrals

Cites Work