[QUOTE=R.D. Silverman;211489]I never bothered to do more than trivial optimizations to the squfof code.

(1) NFS spends so little time inside this routine, that optimizing it will not
have much effect.

(2) MPQS is a [b]lot[/b] faster for numbers of this size.[/QUOTE]

That's fine. The profiling was more for alpertron's benefit than yours, but I thought I'd include yours since you provided it.

Although:
(1) I thought you were interested in *any* improvement to your NFS code

(2) I was under the impression that SQUFOF was really tough to beat for 50ish bit numbers. Maybe NFS needs to split larger numbers where MPQS gains an advantage, but 50 bits seems to be in SQUFOF's wheelhouse. Can MPQS really factor 50 bit numbers in less than 100 microseconds, on average? [url]http://hal.inria.fr/docs/00/45/16/04/PDF/smallint_expcomp_draft_02_1.pdf[/url]

The main problem in using SIQS in numbers of this range in Java is the number of array accesses, which makes it slower. So I will use SQUFOF in order to find the two large primes.

bsquared's version of Silverman's implementation fails for me when asked to factor 2128691; q becomes zero before p==pnext

[QUOTE=bsquared;211495]Can MPQS really factor 50 bit numbers in less than 100 microseconds, on average? [url]http://hal.inria.fr/docs/00/45/16/04/PDF/smallint_expcomp_draft_02_1.pdf[/url][/QUOTE]

It does on my laptop. a 2.4GHz Core-2.

[QUOTE=R.D. Silverman;211498]It does on my laptop. a 2.4GHz Core-2.[/QUOTE]

It doesn't on a xeon 5160.

I moved my test routine into your lattice code, so that I could test things as written. I tested two ways, first calling squfof as is, which first redirects to mpqs and uses rho and squfof as backup. Second, by commenting out the call to mpqs. 10k samples of 51 bit pseudoprimes gives:

squfof only: 315 uS
mpqs+ squfof: 430 uS

10k samples of 55 bit pseudoprimes gives:
squfof only: 631 uS
mpqs + squfof: 430 uS

Using mpqs above 51 bits does start to get faster, but I wouldn't call it a [B]lot[/B] faster. Below 50 bits squfof is a clear win.