On Fri, 01 February 2002, "djbroadhurst" wrote:
> > if you throw a few trivial improvements into Fermat,
> > it's not too shabby on the just-over-word-size range
> So is there a range where Lehman's method (CP 5.1.2)
> is best? This is trial div up to n^(1/3)
> and then Fermat with multipliers up to n^(1/3).
> #ops = O(n^(1/3)*(log(log(n))))
It's a tough call.
Lehman's method isn't really a single method, it's a combination of what is effectively an O(f(p)) method and a O(g(N)) method.
In order to be a fair comparison, you'd have to compare it with all such pairs of algorithms.
I've not analysed the multiplier effectiveness in terms of decreased search-space, but to be honest, my gut-feel is still to prefer the Legendre symbol (effectively constant-factor, often around 10-20:1) boost.
If we are putting or finding limits to the size of N, which we are, then constant factors are hugely important.
I have already done this for something which is a bit like SQUFOF which was quite fun.
Actually, does anyone know the name of that algorithm? It is just like SQUFOF, but without the clever (Shank's?) hack that means you don't need to calculate with full-size numbers as you go, and stick entirely with half-sized numbers.
It seems like it could be a pregenitor to SQUFOF, but I have no idea who may have been behind it. Maybe it was Shank's version 0.9 before he realised the hack?
Don't be fooled, CRC Press are _not_ the good guys.
They've taken Wolfram's money - _don't_ give them yours.
Find the best deals on the web at AltaVista Shopping!