Given a factor base and a number N, find the largest number less than N which factorizes over the factor base. Is there a fast algorithm to solve this problem? I'm guessing not. (Assume a factor base like the first million prime numbers.)
Does this problem have a name?
Given a threshold T, find any number between N-T and N that factorizes over the factor base. For T large enough, the answer is easy, for smaller, it is hard. What characterizes the boundary between easy and hard?
The decision problem is, given T, determine if there is any number that factorizes.
Also consider smooth numbers barely larger than N.
Also consider negative integer exponents permitted on the factor base, so we seek rational numbers with smooth numerator and denominator.
Inspired by SNFS, including trying to crack Verisign certificates.
No comments :
Post a Comment