I've found another QS program. [url]http://www.thorstenreinecke.de/qsieve/[/url]

On my P4 it's [b]much[/b] slower than msieve and ppsiqs, but i've heard others that the differance isn't that large.
[code]Factoring 15876196797381387446616537503748919146510691236383998566352574692051
on my P4 @ 2,5GHz

msieve: 144 seconds
ppsiqs: 222 seconds
qsieve: 1450 seconds (only qs, no ecm, p-1 etc)
[/code]

It has been used to factor partition number 11834 (c116) which took more than 2 months using various pc's. :w00t:

Clearly inefficient use of cpu time. I'm sure msieve would have been much faster and GGNFS could have done it in one week or so on a fast pc

[QUOTE=smh]Ehh, weren't that partition numbers?[/QUOTE]

Were they? I only noticed the familiar URL... :redface:

Luigi

[QUOTE=smh]I've found another QS program. [url]http://www.thorstenreinecke.de/qsieve/[/url]

On my P4 it's [b]much[/b] slower than msieve and ppsiqs, but i've heard others that the differance isn't that large.

[...]

It has been used to factor partition number 11834 (c116) which took more than 2 months using various pc's. :w00t:

Clearly inefficient use of cpu time. I'm sure msieve would have been much faster and GGNFS could have done it in one week or so on a fast pc[/QUOTE]
Maybe the author would consider grafting msieve into the rest of his
architecture? I gave up on a client-server application to do distributed
sieving, but if all of that is already written it would be great to make it an
order of magnitude faster :smile:

jasonp

[url]http://xyyxf.at.tut.by/records.html#qs[/url]

Msieve becomes enough fast to beat multiprocessor mpqs4linux results.
C104_146_73 = P50*P54 took one day, C105_104_71 is upcoming.

And all that in 80 kb!

Great software.

[QUOTE]C104_146_73 = P50*P54 took one day[/QUOTE]

On what cpu?

And how many hours exactly? There's a big difference between 24 and 45 hours.

[QUOTE=smh]On what cpu?

And how many hours exactly? There's a big difference between 24 and 45 hours.[/QUOTE]Less than 23.5 hours, but the run was switched between different types of computers. Ask Tom for more details.

BTW I'm going to try to factor a C114 with MSieve. Should take about a month on my Althon-XP 1600+.

SIQS Bicentennial
 

Jason,

This morning, msieve finished factoring its 200th cyclotomic
number which has been submitted to
Factorizations of Cyclotomic Numbers
[url]http://www.asahi-net.or.jp/~KC2H-MSM/cn/index.htm[/url]

On a sad note, the last of the <100 digit numbers will
finish today.

Excellent software!!! :bow:

Tom

[QUOTE=error404]
This morning, msieve finished factoring its 200th cyclotomic
number which has been submitted to
Factorizations of Cyclotomic Numbers

On a sad note, the last of the <100 digit numbers will
finish today.
[/QUOTE]
Congrats and condolences as the case may be :smile:

I've been experimenting with using triple large primes in msieve, and have modified the sieving stage enough to be able to run some experiments. Originally the code used a 90-bit version of SQUFOF to do the heavy lifting for factoring tri-composites, but that turned out to be really slow. The current version uses a homegrown tiny MPQS implementation which is 5.5x faster. Does anyone know if 10ms to factor an 80-bit number is a good time for a 1GHz CPU? What about 20ms for a 90-bit number?

For my test C100 ordinary 2-prime msieve finishes the sieving in ~17.5 hours; the 3-prime version has not finished after 3 days. While the number of pruning passes appears to be increasing steadily like Paul's TMPQS paper states, I haven't seen an explosion in cycles yet. Maybe the sieving cutoffs are set too conservatively. Statistics collected during the run indicate that only 4% of the relations for which the tiny MPQS code is used actually yield a 3LP relation.

Brief experiments with a C105 show that the slowdown in switching to three primes is reduced by about half, but that in turn means that for this implementation the crossover point where using 3 large primes becomes more efficient is going to be above 110 digits. This is well past the point where you have a valid excuse not to be using GNFS.

Oh well, this isn't entirely unexpected. I guess it's time to begin transferring my MPQS experience to someone else's NFS implementation. I promise that if I get a bright idea to speed up msieve or someone finds another bug, then new versions will be released. But after a few more experiments the code will probably go into mothballs.

Thanks for all your support,
jasonp

[QUOTE=jasonp]But after a few more experiments the code will probably go into mothballs.[/QUOTE]

I haven't looked into the code (and hence can't say anything about the obviousness of the performed functions), but I suggest doing a thorough documentation of the code when you expect to not look at it for a while. It is
very hard to get into it again after let's say half a year.
In addition, maybe someone else wants to integrate improvements. Or there is a bug and you are not available...

This all makes sure this great program stays great. :bow:

[QUOTE=jasonp]Congrats and condolences as the case may be :smile:

I've been experimenting with using triple large primes in msieve, and have modified the sieving stage enough to be able to run some experiments. Originally the code used a 90-bit version of SQUFOF to do the heavy lifting for factoring tri-composites, but that turned out to be really slow. The current version uses a homegrown tiny MPQS implementation which is 5.5x faster. Does anyone know if 10ms to factor an 80-bit number is a good time for a 1GHz CPU? What about 20ms for a 90-bit number?

For my test C100 ordinary 2-prime msieve finishes the sieving in ~17.5 hours; the 3-prime version has not finished after 3 days. While the number of pruning passes appears to be increasing steadily like Paul's TMPQS paper states, I haven't seen an explosion in cycles yet. Maybe the sieving cutoffs are set too conservatively. Statistics collected during the run indicate that only 4% of the relations for which the tiny MPQS code is used actually yield a 3LP relation.

Brief experiments with a C105 show that the slowdown in switching to three primes is reduced by about half, but that in turn means that for this implementation the crossover point where using 3 large primes becomes more efficient is going to be above 110 digits. This is well past the point where you have a valid excuse not to be using GNFS.
[/QUOTE]

So is vers. 0.88 still the most updated?

Luigi

[QUOTE=ET_]
So is vers. 0.88 still the most updated?
[/QUOTE]
0.88 is the latest publicly available release. There are one or two (minor) bugs that it would be nice to fix, so at the least one more version should be out sometime soon.

There have been more developments on the 3-large-prime front. I tried drastically reducing the size of the factor base, and sieving for my test C100 finished in just 42 hours (the first 3LP run took over 90 hours). Version 0.88 needs 20 hours on the same machine, so there's a chance that triple large primes may be faster after all, for the input sizes people care about. I'm running a test C105 with triple large primes now; if it can finish in under 90 hours then it will be worthwhile to do another major release.

Fingers crossed,
jasonp