I've been running a search for Mordell curves of rank >=8 for about 12 months and have identified approximately 280,000 curves in our archivable range, amongst many millions that aren't.
For this search I have been utilizing up to 60 3Ghz+ cpus at any one time. Right now I'm reaching the point of decreasing return and greatly increased memory requirements. As such, I need to be a little smarter in some of the maths.
My question is, then, what is believed (or known) to be the fastest factoring algorithm for positive integers < 2^60.
I'm not overly keen to consume further multiple GHz decades of processing power unless I can get a reasonable return on investment, for which a fast factoring algorithm would certainly help.
Any ideas are more than welcome.
EDIT:
Reading through the responses makes me realise that I should probably add that I want to keep the factoring within 64 bit arithmetic. The Pollard Rho algorithm was interesting, but probably would exceed the 64 bit limit during its execution.
Another part of the puzzle it that, from the factorisations, I'm storing the differences of divisor pairs for each number factored. This may, potentially, leave me with an array of about 50,000,000 values which then subsequently needs to be sorted.
I have been using Pari/GP for this project and, up till now, it's been great. My current problem is mainly with memory usage, with each Pari/GP task taking over 8GByte of memory. This is preventing my 32 core machine from being as efficient as it may otherwise have been. Hence my intent to move to 64 bit arithmetic and 'C' code, to hopefully gain efficiencies in both time and space, thus breathing new life into an otherwise stalling project.
Update:
Thank you to all those that responded with so many good suggestions on how to proceed.
Eventually I've decided to use the flint library, as suggested by William Hart, rather than try to re-invent the wheel. The ability of flint to work directly with 64 bit integers gives me a great advantage as regards memory usage and speed when compared to my current setup. In particular I can now run all 32 cores on my main machine and still have memory left over, potentially giving an 8 fold improvement on processing throughput.
Kevin.
Best Answer
Shanks's SQUFOF (Square FOrm Factorisation) might well be worth a detailed look.
Henri Cohen comments:
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.
Some more references and quotes, and some commentary.
Gower and Wagstaff (Square form factorization, Math of Computation, 2008) in a paper on SQUFOF:
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)
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.