## Return to Answer

2 significantly expanded

Some more references and quotes, and some commentary.

Gower and Wagstaff (Square form factorization, Math of Computation, 2008) in a paper on SQUFOF:

On a 32-bit computer SQUFOF is the clear champion factoring algorithm for numbers between $10^{10}$ and $10^{18}$, and will likely remain so.

More recently William Hart proposed a Fermat-variant he called A One Line Factoring Algorithm, which he describes as competitive with SQUFOF in practise (while only being $O(n^{1/3})$ ). In the respective paper, to be precise a preprint thereof I do not have the actual paper, he writes (J. Aust. Math. Soc. 2012)

Most modern computer algebra packages implement numerous algorithms for factoring. For number that fit into a single machine word Shanks' SQUFOF is popular as it has run time $O(n^{1/4})$ with a very small implied constant.

So, for the range asked for in the question I am quite confident that SQUFOF would be a good choice. It should however be noted, this is also discussed in Cohen's book, that as the numbers get larger (beyond the mentioned threshold) SQUFOF becomes unattractive while, eg, Pollard rho stays interesting. The rough reason for this seems to be that SQUFOF does not profit from 'small' factors, as opposed to, e.g. Pollard (cf Laurent Berger's answer). However, for numbers in that range and after trial divison (Cohen then suggested trial division by primes up to 500000) there are not that 'small' factors anyway.

As already pointed out a big plus for SQUFOF is that the involved numbers are only size $2\sqrt{N}$, in contrast to other methods requiring often $N$ or even $N^2$. This affects only the constant in the running time, but this is also important, and in addition in practise allows to get by with simple datatypes for longer.

1

Shanks's SQUFOF (Square FOrm Factorisation) might well be worth a detailed look.

Henri Cohen comments:

This method is very simple to implement and has the big advantage of working exclusively with numbers which are at most $2\sqrt{N}$ [...] Therefore it is eminently fast and practical when one wants to factor numbers less than $10^{19}$, even on a pocket calculator.

And $2^{60}$ is just below $10^{19}$; and indeed the $10^{19}$ should arise as the number such that $2\sqrt{N}$ still fits in an "int". For reference, the complexity is $O(N^{1/4+\varepsilon})$; but this is not the main point.

Typically, this would have to be preceeded with trial division for small factors and (possibly) some primality test.

In general, I recommend the relevant chapters of the book "A course in computational algebraic number theory" by Henri Cohen (from which the quote is taken); he typically in addition to theory and algorithms, also discusses practical aspects of implementation (the book being not recent some of them might have to be modified, but still the practical aspect and discussion of ranges is present).

Also, various other references of SQUFOF are easy to find via a web-search.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 14, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9583503603935242, "perplexity_flag": "middle"}