HackerPapers

arXiv:1003.5461cs.DS

A Note on Integer Factorization Using Lattices

Antonio Ignacio Vera

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

We revisit Schnorr's lattice-based integer factorization algorithm, now with an effective point of view. We present effective versions of Theorem 2 of Schnorr's "Factoring integers and computing discrete logarithms via diophantine approximation" paper, as well as new elementary properties of the Prime Number Lattice bases of Schnorr and Adleman.

arXiv comments
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms cs.DMDiscrete Mathematics

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Mar 2021 to Mar 2021.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Did Schnorr destroy RSA? Show me the factors 1 comment

    • OK, here is a brief overview for people: To factor a number N (assumed to essentially be the product of two very large primes), find a 'short' lattice vector [0] using LLL [1] (and BKZ reduction? [2]) that finds many relations of the form: (u_i) = p_i,0 * p_{i,1} * ... *…

      abetuskView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.