Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
I missed the comment that the numbers are of a special form and hence limited in possibility. I added another possible way of handling this using a lookup table.
@quid I have some figures: it takes 0.025 sec on my x64 2.00 GHz laptop to run 20 curves to factor primes $<2^{32}$, but it takes negligible time to trial divide up to 500000. I can probably increase the limit a little more, up to a point where the run time is significant. But the expected efficiency is small, so I think there is probably not much difference anyway. So upon reflection: 500000 as a limit seems like a decent idea. I think the ideal number also depends on the range ECM handles. In this case the small primes will be found by the curves, so the limit does not need to be that high.
@quid Roughly speaking, suppose I aim to trial divide a range of primes. Then equivalently, I can set a set of 20 curves to find that same range (20 curves to get a high prob. of >0.95). So any time the 20 curves takes less time than the trial division, switching to ECM is faster. Unfortunately I did not find that leveling point. Also, I agree that given OP's range, after trial testing the small ones the case is usually the same as the paper (2-4 factors) so SQUFOF seems like the better choice. My suggestions/comments are for the case when he wants to do it via ECM.
@quid I am not too sure how the association works. I mentioned INRIA since the papers are usually hosted by its webpages and it appears that the authors are linked to the organization. But I guess you are right, probably more correct to quote Jérôme Milan instead. As for trial division testing beyond $2^{10}$ (not sure what actual values are) does not seem very effective. It is still good to trial test the very small ones though, since the time taken is negligible; It should be the medium ones that should not be tested by trial division.
Quick answer: there are 2 ways to get md5(x)=y. One is by finding x, where no method is known to be better than bruteforcing x. Another way, which your question seems to suggest, is to study related-keys and try to get md5(x) without finding x. To my best of knowledge there are no results of this kind. There are studies on the differential probabilities, which is very low as you can imagine, very unlikely to beat bruteforcing. However, if the salt is fixed, one may use rainbow tables so that future searches are faster.
