The DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index.
Factoring polynomials with rational coefficients
Open accessOverview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 15,999
B., T. A. A. (1946) · The Mathematical Gazette · doi:10.1017/s0025557200071461 · Cited by 7,129
An Introduction To The Theory Of Numbers
Hardy, G. H., & Wright, E. M. (2008) · doi:10.1093/oso/9780199219858.001.0001 · Cited by 2,624
Approximate formulas for some functions of prime numbers
Rosser, J. B., & Schoenfeld, L. (1962) · Illinois Journal of Mathematics · doi:10.1215/ijm/1255631807 · Cited by 1,546
Integer Programming with a Fixed Number of Variables
Lenstra, H. W. (1983) · Mathematics of Operations Research · doi:10.1287/moor.8.4.538 · Cited by 1,440
Self-citationThe art of computer programming. Vol.2: Seminumerical algorithms
Knuth, D. E. (1981) · Virtual Defense Library (Ministerio de Defensa) · Cited by 1,232
Milner, R. (1976) · Cited by 742
An Inequality About Factors of Polynomials
Mignotte, M. (1974) · Mathematics of Computation · doi:10.1090/s0025-5718-1974-0354624-3 · Cited by 143
A sublinear additive sieve for finding prime number
Pritchard, P. (1981) · Communications of the ACM · doi:10.1145/358527.358540 · Cited by 53
Cited by
Fully homomorphic encryption using ideal lattices
Gentry, C. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536440 · Cited by 6,806
Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator
Matsumoto, M., & Nishimura, T. (1998) · ACM Transactions on Modeling and Computer Simulation · doi:10.1145/272991.272995 · Cited by 5,780
Trapdoors for hard lattices and new cryptographic constructions
Gentry, C., Peikert, C., & Vaikuntanathan, V. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374407 · Cited by 2,435
On lattices, learning with errors, random linear codes, and cryptography
Regev, O. (2009) · Journal of the ACM · doi:10.1145/1568318.1568324 · Cited by 2,315
On lattices, learning with errors, random linear codes, and cryptography
Regev, O. (2005) · Proceedings of the thirty-seventh annual ACM symposium on Theory of computing · doi:10.1145/1060590.1060603 · Cited by 2,313
NTRU: A ring-based public key cryptosystem
Hoffstein, J., Pipher, J., & Silverman, J. H. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0054868 · Cited by 1,947
Gentry, C., Sahai, A., & Waters, B. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40041-4_5 · Cited by 1,492
Fincke, U., & Pohst, M. (1985) · Mathematics of Computation · doi:10.1090/s0025-5718-1985-0777278-8 · Cited by 1,458
Efficient Fully Homomorphic Encryption from (Standard) LWE
Brakerski, Z., & Vaikuntanathan, V. (2011) · 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2011.12 · Cited by 1,449
Integer Programming with a Fixed Number of Variables
Lenstra, H. W. (1983) · Mathematics of Operations Research · doi:10.1287/moor.8.4.538 · Cited by 1,440
Self-citationLattice basis reduction: Improved practical algorithms and solving subset sum problems
Schnorr, C. P., & Euchner, M. (1994) · Mathematical Programming · doi:10.1007/bf01581144 · Cited by 1,427
Closest point search in lattices
Agrell, E., Eriksson, T., Vardy, A., & Zeger, K. (2002) · IEEE Transactions on Information Theory · doi:10.1109/tit.2002.800499 · Cited by 1,412
Generating hard instances of lattice problems (extended abstract)
Ajtai, M. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237838 · Cited by 1,405
A Survey on Homomorphic Encryption Schemes: Theory and Implementation
Acar, A., Aksu, H., Uluagac, A. S., & Conti, M. (2019) · ACM Computing Surveys · doi:10.1145/3214303 · Cited by 1,397
On Lovász’ lattice reduction and the nearest lattice point problem
Babai, L. (1986) · Combinatorica · doi:10.1007/bf02579403 · Cited by 938
Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
Micciancio, D., & Regev, O. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539705447360 · Cited by 907
The Decision Diffie-Hellman problem
Boneh, D. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0054851 · Cited by 895
Fifty Years of MIMO Detection: The Road to Large-Scale MIMOs
Yang, S., & Hanzo, L. (2015) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2015.2475242 · Cited by 814
Public-key cryptosystems from the worst-case shortest vector problem: extended abstract
Peikert, C. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536461 · Cited by 813
Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes
Smart, N. P., & Vercauteren, F. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-13013-7_25 · Cited by 808
The NP-completeness column: An ongoing guide
Johnson, D. S. (1986) · Journal of Algorithms · doi:10.1016/0196-6774(86)90020-9 · Cited by 794
Minkowski's Convex Body Theorem and Integer Programming
Kannan, R. (1987) · Mathematics of Operations Research · doi:10.1287/moor.12.3.415 · Cited by 777
Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities
Coppersmith, D. (1997) · Journal of Cryptology · doi:10.1007/s001459900030 · Cited by 771
Lossy Trapdoor Functions and Their Applications
Peikert, C., & Waters, B. (2011) · SIAM Journal on Computing · doi:10.1137/080733954 · Cited by 649
A hierarchy of polynomial time lattice basis reduction algorithms
Schnorr, C. P. (1987) · Theoretical Computer Science · doi:10.1016/0304-3975(87)90064-8 · Cited by 648
On the hardness of approximating vertex cover
Dinur, I., & Safra, S. (2005) · Annals of Mathematics · doi:10.4007/annals.2005.162.439 · Cited by 636
Micciancio, D., & Regev, O. (2009) · Post-Quantum Cryptography · doi:10.1007/978-3-540-88702-7_5 · Cited by 615
BKZ 2.0: Better Lattice Security Estimates
Chen, Y., & Nguyen, P. Q. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-25385-0_1 · Cited by 598
Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures
Lyubashevsky, V. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-10366-7_35 · Cited by 558
A sieve algorithm for the shortest lattice vector problem
Ajtai, M., Kumar, R., & Sivakumar, D. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380857 · Cited by 558
Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$
Brakerski, Z., & Vaikuntanathan, V. (2014) · SIAM Journal on Computing · doi:10.1137/120868669 · Cited by 538
A Decade of Lattice Cryptography
Peikert, C. (2016) · Foundations and TrendsŴ in Theoretical Computer Science · doi:10.1561/0400000074 · Cited by 504
Regev, O. (2006) · Lecture Notes in Computer Science · doi:10.1007/11818175_8 · Cited by 485
Public-key cryptosystems from lattice reduction problems
Goldreich, O., Goldwasser, S., & Halevi, S. (1997) · Lecture Notes in Computer Science · doi:10.1007/bfb0052231 · Cited by 482
CSIDH: An Efficient Post-Quantum Commutative Group Action
Castryck, W., Lange, T., Martindale, C., Panny, L., & Renes, J. (2018) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-03332-3_15 · Cited by 481
Pseudorandom Functions and Lattices
Banerjee, A., Peikert, C., & Rosen, A. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-29011-4_42 · Cited by 459
Improved algorithms for integer programming and related lattice problems
Kannan, R. (1983) · Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83 · doi:10.1145/800061.808749 · Cited by 441
MLAMBDA: a modified LAMBDA method for integer least-squares estimation
Chang, X. W., Yang, X., & Zhou, T. (2005) · Journal of Geodesy · doi:10.1007/s00190-005-0004-x · Cited by 423
Gama, N., & Nguyen, P. Q. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78967-3_3 · Cited by 413
Solving low-density subset sum problems
Lagarias, J. C., & Odlyzko, A. M. (1985) · Journal of the ACM · doi:10.1145/2455.2461 · Cited by 397
Cryptanalysis of RSA with private key d less than N/sup 0.292/
Boneh, D., & Durfee, G. (2000) · IEEE Transactions on Information Theory · doi:10.1109/18.850673 · Cited by 391
Quantum algorithms for algebraic problems
Childs, A. M., & van Dam, W. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.1 · Cited by 344
The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations
Arora, S., Babai, L., Stern, J., & Sweedyk, Z. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1472 · Cited by 344
Faster Fully Homomorphic Encryption
Stehlé, D., & Steinfeld, R. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-17373-8_22 · Cited by 330
Survey on Fully Homomorphic Encryption, Theory, and Applications
Marcolla, C., Sucasas, V., Manzano, M., Bassoli, R., Fitzek, F. H. P., & Aaraj, N. (2022) · Proceedings of the IEEE · doi:10.1109/jproc.2022.3205665 · Cited by 323
Discrete Logarithms in $GF ( P )$ Using the Number Field Sieve
Gordon, D. M. (1993) · SIAM Journal on Discrete Mathematics · doi:10.1137/0406010 · Cited by 322
Hardness of SIS and LWE with Small Parameters
Micciancio, D., & Peikert, C. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40041-4_2 · Cited by 299
Modular Forms, a Computational Approach
Stein, W. (2007) · Graduate Studies in Mathematics · doi:10.1090/gsm/079 · Cited by 297
New lattice-based cryptographic constructions
Regev, O. (2004) · Journal of the ACM · doi:10.1145/1039488.1039490 · Cited by 292
Generic Attacks on Secure Outsourced Databases
Kellaris, G., Kollios, G., Nissim, K., & O'Neill, A. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978386 · Cited by 284
Lattice Enumeration Using Extreme Pruning
Gama, N., Nguyen, P. Q., & Regev, O. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-13190-5_13 · Cited by 284
Generalized Compact Knapsacks Are Collision Resistant
Lyubashevsky, V., & Micciancio, D. (2006) · Lecture Notes in Computer Science · doi:10.1007/11787006_13 · Cited by 268
Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes
Boneh, D., & Venkatesan, R. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-68697-5_11 · Cited by 266
A Decade of Lattice Cryptography
Peikert, C. (2016) · now publishers, Inc. eBooks · doi:10.1561/9781680831139 · Cited by 256
The Learning with Errors Problem (Invited Survey)
Regev, O. (2010) · 2010 IEEE 25th Annual Conference on Computational Complexity · doi:10.1109/ccc.2010.26 · Cited by 255
The Two Faces of Lattices in Cryptology
Nguyen, P. Q., & Stern, J. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44670-2_12 · Cited by 252
Quantum Computation and Lattice Problems
Regev, O. (2004) · SIAM Journal on Computing · doi:10.1137/s0097539703440678 · Cited by 188
Factoring integers with the number field sieve
Buhler, J. P., Lenstra, H. W., & Pomerance, C. (1993) · Lecture Notes in Mathematics · doi:10.1007/bfb0091539 · Cited by 188
Self-citationQuantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers
Ekerå, M., & Håstad, J. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-59879-6_20 · Cited by 62
Quantum proofs for classical theorems
(2011) · Theory of Computing · doi:10.4086/toc.gs.2011.002 · Cited by 41
Bachlechner (2018) · doi:10.1103/physrevd.98.061301 · Cited by 30
On post-processing in the quantum algorithm for computing short discrete logarithms
Ekerå, M. (2020) · Designs, Codes and Cryptography · doi:10.1007/s10623-020-00783-2 · Cited by 23
Quantum algorithms for computing general discrete logarithms and orders with tradeoffs
Ekerå, M. (2021) · Journal of Mathematical Cryptology · doi:10.1515/jmc-2020-0006 · Cited by 3
Gottesman-Kitaev-Preskill codes: A lattice perspective
Conrad, J., Eisert, J., & Arzani, F. (2022) · Quantum · doi:10.22331/q-2022-02-10-648
Metadata
- Authors
- Lenstra, A. K., Lenstra, H. W., & Lovász, L.
- Venue
- Mathematische Annalen
- Published
- 1982-12
- Volume
- 261
- Issue
- 4
- Pages
- 515-534
- ISSN
- 0025-5831 (ISSN-L)
- 1432-1807
- OpenAlex
- W2141040012
- Cited by
- 4,018
- References
- 9
- FWCI
- 42.00
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.