[QUOTE=bsquared;190532]I misjudged the importance of C149, sorry. There are plenty of other numbers out there for testing siqs; I've started poly selection.[/QUOTE]

Thanks. As you mention, C149 will not be easy by any QS version,
including triple large primes. Never-the-less, the benchmark QS advocates
would probably most like to see would be C155=512bits. If I recall, we
were trying to talk Paul out of attemping it any time soon. Carl Pomerance
gave a series of lectures here, and wrote up the article "Tale of two sieves"
partly based on the lectures for the AMS Notices. At that time the
comparison was RSA129 and RSA130, qs -vs- gnfs. Carl, for one, would
certainly be interested in larger QS records; but he likely would have wanted
(and believed that there were) improvements to keep QS competitive
somewhat further out.

Not sure whether we'll see 512-bit QS anytime soon, but the recent
64-bit lasieve (linux) binaries, and the transparency of msieve (for the user,
at least) suggests that gnfs has gotten well out of the range where even
the most enthusiastic advocates of QS (and it's improved variants) seem
likely to reach. We had C163 from W+D and C169 from B+D, and Serge
reports that while doing the polyn selection for our C174 gnfs he's done
some tuning that make current version of 1.43 fluent out to nearly 180-digits.
Perhaps we'll get an update from Thorsten, to see what 190-digits looks
like, and we can try smaller-large primes to see how small we can make
the matricies look (if Tom's correct that larger-large primes aren't essential).

-Bruce (" +D", resp. "/D", as in C/D)
----

PS - Incidently, speaking of Greg (="C/"); one of the points of
512-bit QS was that QS would be more suitable for large distributed
projects (like RSA129), making use of general public pcs. That'll
be one of the things to watch for in NFS@home, which has just
recently reserved the four most wanted base-2's. (Not even
"fiddled" with.)

One very clever optimization for the quadratic sieve with large inputs is described [url="http://www.daemonology.net/blog/2005-11-30-quadratic-sieve-constant.html"]here[/url]. It promises to make sieving twice as fast for large enough inputs. For the record, I've coded this up and 'large enough' is around 100 digits, but

- the memory use increases drastically

- getting the factor of 2 increase in sieving speed requires making the sieve interval so small that the relation discovery rate drops by a factor of about 4, so at least for 100-digit problems it's a net loss.

That doesn't mean the rest of the QS parameters can't be tweaked to make it competitive. Too bad speeding QS up isn't interesting, and there wouldn't be any interest in porting the modifications to an NFS lattice siever :)

[quote=bdodson;190539]Thanks. As you mention, C149 will not be easy by any QS version,
including triple large primes. Never-the-less, the benchmark QS advocates
would probably most like to see would be C155=512bits. [/quote]

Yikes! The C149 was daunting enough... another 6 digits puts it over the horizon.

Although I think a new record for siqs would be neat, really I just want to try to push back on the qs/gnfs boundary a bit. Right now, it seems to be at 90-95 digits (I haven't tested this first-hand). I'd like to see if 3LP can be effective at that level to achieve a speedup.

[QUOTE=bsquared;190549]Right now, it seems to be at 90-95 digits (I haven't tested this first-hand). [/QUOTE]
Although I haven't run any gnfs < 90 digits, it would seem that with a tweaked msive poly selector, on 64-bit platform, the cutoff is more like 86-digits. For reference My C2D 2GHz can knock off a C90 in ~ 50mins (incl. poly search) by GNFS, while the same would take around 1h15m by Yafu (quoting numbers from memory)

[QUOTE=axn;190551]Although I haven't run any gnfs < 90 digits, it would seem that with a tweaked msive poly selector, on 64-bit platform, the cutoff is more like 86-digits. For reference My C2D 2GHz can knock off a C90 in ~ 50mins (incl. poly search) by GNFS, while the same would take around 1h15m by Yafu (quoting numbers from memory)[/QUOTE]

I haven't tested numbers smaller than c90 very much yet - I had a few crashes of gnfs-lasieve4I12e with c8x'es, so I set the cutoff to 90 digits in my aliqueit.ini file.

btw: Has anyone tested the 1[B]1[/B]e-siever on c8x'es yet? Is it faster than 12e?

[QUOTE=Andi47;190555]btw: Has anyone tested the 1[B]1[/B]e-siever on c8x'es yet? Is it faster than 12e?[/QUOTE]

I am using it for < 95 digits. It is competitive with 12e at 92-94 digits, and slightly faster below that. Of course, it also depends on the actual sieve parameters used, so YMMV.

[quote=axn;190551]Although I haven't run any gnfs < 90 digits, it would seem that with a tweaked msive poly selector, on 64-bit platform, the cutoff is more like 86-digits. For reference My C2D 2GHz can knock off a C90 in ~ 50mins (incl. poly search) by GNFS, while the same would take around 1h15m by Yafu (quoting numbers from memory)[/quote]

That's pretty discouraging data, from the standpoint of sinking a lot of time into 3LP development. I doubt it would result in a speedup in QS at that size due to the extra overhead. I'll maybe have to re-evaluate what I want to work on next.

[QUOTE=jasonp;190544]One very clever optimization for the quadratic sieve with large inputs is described [url="http://www.daemonology.net/blog/2005-11-30-quadratic-sieve-constant.html"]here[/url]. It promises to make sieving twice as fast for large enough inputs. For the record, I've coded this up and 'large enough' is around 100 digits,

... Too bad speeding QS up isn't interesting, and there wouldn't be any interest in porting the modifications to an NFS lattice siever :)[/QUOTE]

My immediate concern was near-term c149. Beyond that, it is certainly
the case that I've spent too much of my training in factorization issues
(such as it is) with people that were looking very carefully at comparing
gnfs at n with gnfs at 10^5*n, to be able to get the full effect of the
worse constants in the asymptotic runtime somewhat beyond 512-bits.
Compare that with what our QS advocate reports:

[QUOTE]
with the result that the Number Field Sieve only becomes faster than the Quadratic Sieve somewhere around 110--140 digits.

... Since most of the initialization work depends only upon ..., this provides a very significant reduction in the initialization cost -- thereby permitting smaller sieve lengths M to be used and providing a speedup of roughly a factor of 2.

We can do better. ... I expect this to provide another factor of 2 speedup.

Now to the interesting point: A factor of 2 speedup in the Quadratic Sieve is more significant than it sounds. It allows you to factor integers 3-4 digits longer in the same amount of time; that much isn't very impressive. It also moves the tradeoff point between the Quadratic Sieve and the Number Field Sieve -- the point where GNFS takes over as the fastest algorithm available -- upwards by roughly 15 digits. Gain a couple of factors of two, and the tradeoff point is around 155 digits -- that is, 512 bits -- and the Quadratic Sieve becomes interesting for "cryptography-sized" integers. [/QUOTE]

We did the very first gnfs -vs- QS comparison (that was
A. Lenstra/bdodson, "...An explosive experiment", Crypto '95).
We got c112; not "110 --- 140 digits".

Even if one believed that there were two factor-of-two improvements
(not just one), _and_ that combined they'd add "roughly 15 digits" to the
crossover, there's a large difference between 112+15 -vs- 140+15.

I'm not asserting that QS improvements aren't interesting. But if it were
my money (which it isn't), I'd be more interested in getting polyn searching
up above C182. As I was mentioning, we know where lenstra@epfl is
putting his money; Bos is his student there, and Thorsten's listed as a
epfl research associate (or some such). -Bruce ("no fiddling")
---

PS - How long ago was this? We got a speed-up of a factor of two
between the first c116 and the second one by using Scott Contini's
new matrix code for the just introduced Block Lanczos. Scott subsequently
did his grad work with Pomerance at Univ. Ga., and (surprise) is also an an
early advocate of siqs.

PPS - Well. Much, much less than 92+15 ...

I've got automated msieve and gnfs running on the aliquot sequences - not a difficult task but means I have a ready supply of gnfs and msieve timings for small numbers in the 80-100 digit range.

Curve-fits (yes, I know the asymptotics aren't like this, but the clusters are wide enough that I'm not confident of anything more complicated than a straight line through the N:log t fuzz) are something like exp(0.22*n - 10.7) seconds for msieve up to n=90ish digits, exp(0.12*n-2.3) seconds for gnfs-lasieve4I12e at n=90..100 digits, for a crossover somewhere around 85 digits.

Here are some benchmarks with threads on my Core2 Q9550 @ 3.4GHz running on Windows7 64bit with YAFU 1.11 32k.

C75: siqs(281396163585532137380297959872159569353696836686080935550459706878100362721)

[U]64bit Windows Binary[/U]
1 thread = 94.7834 seconds
2 threads = 51.1399 seconds = [B]1.85x[/B]
3 threads = 36.4441 seconds = [B]2.60x[/B]
4 threads = 31.9148 seconds = [B]2.97x[/B]

[U]32bit Windows Binary[/U]
1 thread = 107.9762 seconds
2 threads = 59.3384 seconds = [B]1.82x[/B]
3 threads = 41.5894 seconds = [B]2.60[/B]
4 threads = 36.6281 seconds = [B]2.95x[/B]

A big gain using 3 threads but only slightly faster using 4. It would be interesting to see if that changes much on a Core i7 with more memory bandwidth.

[quote=Jeff Gilchrist;190618] It would be interesting to see if that changes much on a Core i7 with more memory bandwidth.[/quote]

Thanks Jeff! That would be interesting to see if it is a memory bandwidth thing or just thread overhead. Anyone with an idle i7 that wants to see?

The windows 64 bit binaries are now on the [url=http://bbuhrow.googlepages.com/home]website[/url], along with the 1.11 source code.

Also, Jeff noticed a bug wherein the program crashes if you try to restart a siqs factorization that has already finished. Restarting a partially finished factorization still works fine, multi-threaded or not. It's fixed in my development source now.