Hasty Briefsbeta

Bilingual

Bernstein's Factorization Method Helped Factor RSA-240 in 2020

4 hours ago
  • Bernstein's algorithm finds all small prime factors less than a bound B for a list of integers, known as batch smoothness detection.
  • It contributed to a 25% reduction in time spent factoring RSA-240 (a 795-bit number) by Boudot et al. in 2020.
  • The algorithm uses product trees and 2-adic division to efficiently compute modular reductions without expensive divisions.
  • The Python implementation includes auxiliary algorithms: TwoAdicInverse, TwoAdicDivision, ConstructProductTree, FindDividingPrimes, and the main BernsteinFactorization.
  • The code is demonstrated with a numerical example factoring small integers [492, 2567, 3135, 5889] using primes up to 19, yielding correct factor lists.
  • The algorithm is part of a 'Practical Number Field Sieve for Programmers' series, focusing on integer factorization and discrete logarithm computation.