I am reading this article:


The author mentions that trying to factor a number finding two squares such that its difference is the number is worse than trial division because most numbers have a small factor but only a fraction of them have a divisor near their root.

I am wondering how one can make this statement more precise.

  • $\begingroup$ The theory of smooth numbers is useful for the number of numbers with a small factor. I am not sure how to estimate the number of numbers with a factor "near" the square root. $\endgroup$ – Peter Sep 19 '19 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.