Using p=2 for sieving (Quadratic sieve algorithm)

[bsquared]

Originally Posted by Peter Hackman

Unless my programs are completely wrong,
this number yields completely to Pollard rho;

True, but using a much higher bound for the maximum number of iterations than I normally use when I know I can get the factors in a few hundred milliseconds using QS (after removing the easy Pollard Rho factors...). Maybe my Rho implementation is just slow

Also, P+1 can find the penultimate factor fairly easily.

- ben.

[Peter Hackman]

I ran the program simply because I have it. It (my version) is not fast; I think this factorization took 3 seconds.

Im impressed with the running times that people give here. I'm a pure mathematician (retired University lecturer) with no real background in CS or programming, so this thing is a little hobby of mine.

I've been testing a MPQS program whose main virtue is being not too long, but it's slow.

I tried things like scaled logs (factor 100)
varying factor base lengths, keeping a few powers above the small primes limit (like, say, 64, 81, 125 above 57), changing the target and tolerance factor, enough to convince me that the main problem lies elsewhere.
I haven't yet tried multipliers because Silverman's paper left a little gap -
it didn't explain what it means to "use" the KS function (I know now) -
there was also a typo, a missing index. Question: reference for KS, theory?

I just profiled a run on a 50-digit number, and I spent something like 156 seconds on inverses (would inverses modulo products speed things up?)
64 on trial division (resieving interesting option?) and 16 on Gauss (I think I know what the trouble is here). I have no clear picture of the sieving time. Morrison-Brillhart's square root procedure takes 1.8 seconds per call
(the obvious alternative would require a different representation of matrices to be efficient)
modular square roots of N (Lucas U((p+3)/2)) 0.6, etc.
Finding polynomial coefficients a,b took less.

I believe some of the problems may be language related; you got to know the right way to represent things proper to that language.
E.g., some friends showed me how to speed certain things up (in Python 2.5) using strings instead of lists.
Re-writing a certain loop a certain way speeded things by 40%.
It's not THAT important really, but I'd like to factor a few 70 digit numbers before I die.

[jasonp]

Originally Posted by Peter Hackman

Im impressed with the running times that people give here. I'm a pure mathematician (retired University lecturer) with no real background in CS or programming, so this thing is a little hobby of mine.

I believe some of the problems may be language related; you got to know the right way to represent things proper to that language.
E.g., some friends showed me how to speed certain things up (in Python 2.5) using strings instead of lists.
Re-writing a certain loop a certain way speeded things by 40%.
It's not THAT important really, but I'd like to factor a few 70 digit numbers before I die.

You should not use Python if performance is a concern. It's great for algorithm experiments, but for industrial-strength number crunching like this it just is not fast enough.

The Readme in the msieve source contains many factoring references, including one that goes into detail on the KS algorithm. Maybe you can peruse the source for ideas; on a fast modern machine msieve can complete a 70-digit job in less than 90 seconds.

[Peter Hackman]

Originally Posted by jasonp

You should not use Python if performance is a concern. It's great for algorithm experiments, but for industrial-strength number crunching like this it just is not fast enough.

The Readme in the msieve source contains many factoring references, including one that goes into detail on the KS algorithm. Maybe you can peruse the source for ideas; on a fast modern machine msieve can complete a 70-digit job in less than 90 seconds.

Thanks for you response. I'm aware of some of the shortcomings of Python
in this context; for instance, binary Euclid is much slower than the division variant at that level! I never extended it.

But I´m sure differences between languages alone can't really account for a factor 100 - the number discussed here takes me 80 seconds!
What would a realistic factor be, in comparing python/C, everything else equal?

SIQS would probably cut the inversion time drastically (I haven't quite decided the best generation strategy; there also remains a serious bug, probably a skewed argument); I've done some thinking about improvements on trial division, and my gauss routine uses bit operations on bigints, not optimal, I suppose.
Those are the points I would work on before I contemplate learning a lowlevel language at my advanced age!

I will print your code if it's not too long. I have a printout of Willam Hart's program (28 pages) and one (in ratfor) by Wagstaff (34)
from which I already took a few ideas.

I've finally found incomplete references on KS; e.g., in Knuth's Bible.
It's easier to use an idea correctly when you know what it's all about.
Regarding the above discussion my routine gives 1 as the optimum, with clear peaks at 15 and 71, so it can't be all wrong. (For some reason it appears that Hart only tests prime multipliers whereas you test all square-free numbers up to a certain limit. I sum over p<1000 for no scientific reason at all). It seems that when I use a non-trivial multiplier I
often get LOTS of redundance, which I don't really understand.
I stop sieving when smooths+ 0.07*partials > 0.96*length of factorbase.