BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Curtis Bright (University of Windsor) DTSTART:20240822T210000Z DTEND:20240822T220000Z DTSTAMP:20260513T193329Z UID:SFUOR/37 DESCRIPTION:Title: S AT and Lattice Reduction for Integer Factorization\nby Curtis Bright ( University of Windsor) as part of PIMS-CORDS SFU Operations Research Semin ar\n\nLecture held in ASB 10908.\n\nAbstract\nThe difficulty of factoring large integers into primes is the basis for cryptosystems such as RSA. Due to the widespread popularity of RSA\, there have been many proposed attac ks on the factorization problem such as side-channel attacks where some bi ts of the prime factors are available. When enough bits of the prime facto rs are known\, two methods that are effective at solving the factorization problem are satisfiability (SAT) solvers and Coppersmith's method. The SA T approach reduces the factorization problem to a Boolean satisfiability p roblem\, while Coppersmith's approach uses lattice basis reduction. Both m ethods have their advantages\, but they also have their limitations: Coppe rsmith's method does not apply when the known bit positions are randomized \, while SAT-based methods can take advantage of known bits in arbitrary l ocations\, but have no knowledge of the algebraic structure exploited by C oppersmith's method. In this paper we describe a new hybrid SAT and comput er algebra approach to efficiently solve random leaked-bit factorization p roblems. Specifically\, Coppersmith's method is invoked by a SAT solver to determine whether a partial bit assignment can be extended to a complete assignment. Our hybrid implementation solves random leaked-bit factorizati on problems significantly faster than either a pure SAT or pure computer a lgebra approach.\n\nThis is joint work with Yameen Ajani.\n LOCATION:https://researchseminars.org/talk/SFUOR/37/ END:VEVENT END:VCALENDAR