- 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.