[QUOTE=rogue]GGNFS is limited to under 130 digits for a gnfs factorization. I've been playing around with a few between 120 and 125 digits, but more work needs to be done to determine the optimal parameters.[/QUOTE]Sander has used the ggnfs siever to find just over half the required relations to factor a c135. I used ggnfs a little bit but mostly the original Franke siever to find the rest. The post-processing is presently underway on a box at home. It's using the CWI tool set.

We hit problems with the ggnfs siever. It sieves over a much longer linelength in the untransformed coordinates than the Franke siever. We found approximately 40% of the relations to have |a| > 2^31 and so not fit in a 32-bit signed integer. Eventually I'll see what can be done to make those relations usable but as we have enough relations now for the task in hand the urgency has worn off.


Paul

[QUOTE=xilman]Under-sieving, IMO.

I'm sure they could have got the LA time down substantially if they had spent more sieving. However, they would have had an even harder time with the data handling and filtering.

Asymptotically the sieving and LA times should be equal. I don't believe that RSA-640 is anywhere near big enough for that rule to be particularly useful.


Paul[/QUOTE]

Historically, the LA has taken much less total CPU time than the sieving.
However, for large numbers, the *elapsed* time for the LA has always
been a significant fraction of the elapsed sieve time. This is because the
LA does not scale in parallel. Now we have an instance where the total
time for LA (not just elapsed time) is catching up to the sieve time.

People have repeatedly implied that I don't know what I am talking about
when I say that LA still does not run well in parallel. Yes, it runs. And
we can apply ~100 machines to it. However, we can apply thousands
of machines to sieving (if we had them) with little loss in efficiency.
The same is not true of LA.

[QUOTE=xilman]Sander has used the ggnfs siever to find just over half the required relations to factor a c135. I used ggnfs a little bit but mostly the original Franke siever to find the rest. The post-processing is presently underway on a box at home. It's using the CWI tool set.

We hit problems with the ggnfs siever. It sieves over a much longer linelength in the untransformed coordinates than the Franke siever. We found approximately 40% of the relations to have |a| > 2^31 and so not fit in a 32-bit signed integer. Eventually I'll see what can be done to make those relations usable but as we have enough relations now for the task in hand the urgency has worn off.

Paul[/QUOTE]

I misstated. ggnfs can handle larger than 130 digits, but has not been thoroughly tested for composites that large. The main issue (from my perspective) is parameter selection for which ggnfs does not have default parameters for composites over 126 digits.

Next project?
 

Did he say, what will be their next big factoring project?

Jens Franke's own SNFS projects M739 and 10^226+1 are still without
results.

Heikki

[QUOTE=R.D. Silverman]Historically, the LA has taken much less total CPU time than the sieving. However, for large numbers, the *elapsed* time for the LA has always been a significant fraction of the elapsed sieve time. This is because the LA does not scale in parallel. Now we have an instance where the total time for LA (not just elapsed time) is catching up to the sieve time.
[/QUOTE]
It would be nice to have an idea of just how (in)efficient their parallel LA step was in terms of processor utilization. [url=http://www.rsasecurity.com/rsalabs/node.asp?id=2088]This RSA labs paper by some obscure fellow named "Robert Silverman"[/url] mentions some early feasibility studies by Peter Montgomery of parallel Block Lanczos in which , by the time the number of processors reaches a mere 16, the per-processor utilization has dropped to an anemic 20%. Surely there have been some improvements to this (perhaps simply throwing faster ethernet at the problem is the main one), but it seems clear the algorithm simply doesn't scale well.

The other problem with the LA taking so long would seem to be that the longer things take when running such a tightly coupled procedure, the greater the odds of at least one of those nodes (or the entire system) going down (or merely running more slowly than the others for some reason) during the process. Even assuming that the LA code has been designed to be able to survive a few nodes going offline, the entire procedure becomes a weakest-link game, since all the other nodes need to wait while the offline node's part of the computation is redone or while the slow node finishes its current task. Then there is the problem of the entire system going down or having to be shut down (e.g. for maintenance or upgrades) - that is virtually guaranteed to happen when one is talking about a span of months. Bob's paper mentions a LA dataset size of roughly 6 TB for a 1024-bit RSA factorization - is writing periodic savefiles to disk even a viable option with such a large dataset?

[QUOTE=ewmayer]It would be nice to have an idea of just how (in)efficient their parallel LA step was in terms of processor utilization. [url=http://www.rsasecurity.com/rsalabs/node.asp?id=2088]This RSA labs paper by some obscure fellow named "Robert Silverman"[/url] mentions some early feasibility studies by Peter Montgomery of parallel Block Lanczos in which , by the time the number of processors reaches a mere 16, the per-processor utilization has dropped to an anemic 20%. Surely there have been some improvements to this (perhaps simply throwing faster ethernet at the problem is the main one), but it seems clear the algorithm simply doesn't scale well.

The other problem with the LA taking so long would seem to be that the longer things take when running such a tightly coupled procedure, the greater the odds of at least one of those nodes (or the entire system) going down (or merely running more slowly than the others for some reason) during the process. Even assuming that the LA code has been designed to be able to survive a few nodes going offline, the entire procedure becomes a weakest-link game, since all the other nodes need to wait while the offline node's part of the computation is redone or while the slow node finishes its current task. Then there is the problem of the entire system going down or having to be shut down (e.g. for maintenance or upgrades) - that is virtually guaranteed to happen when one is talking about a span of months. Bob's paper mentions a LA dataset size of roughly 6 TB for a 1024-bit RSA factorization - is writing periodic savefiles to disk even a viable option with such a large dataset?[/QUOTE]


Faster networks have improved things a great deal. But the inter-processor
latencies are still in the millisecond range. Until this latency comes down
by a lot, the LA will not scale well.

Tightly coupled machines such as the (now defunct) Intel Paragon
and the CM5 (I loved that machine!) had latencies in the ~10 microsecond
range....

According to the [URL=http://www.mellanox.com/products/hpc.html]manufacturer[/URL] of the Infiniband adapter cards of our cluster, the "small message latency" is 4.5 microseconds, with 860MB/s sustained throughput. That I have no software to run on it is maddening.

Alex

[QUOTE=ewmayer]It would be nice to have an idea of just how (in)efficient their parallel LA step was in terms of processor utilization. [/QUOTE]
Peter Montgomery and I have experimental results to suggest that performance is O(sqrt(N)) where N is the number of processors. We do not have a good, or even plausible, theoretical explanation.


Paul

Congrats again to the finders....

Strange ... no mention of the completed factorization on [url]http://www.rsasecurity.com/rsalabs/node.asp?id=2093[/url] ??

[QUOTE=CedricVonck]Congrats again to the finders....

Strange ... no mention of the completed factorization on [url]http://www.rsasecurity.com/rsalabs/node.asp?id=2093[/url] ??[/QUOTE]

I might say something about that, but as a condition of receiving severance
pay when I was laid off from RSA Labs, I was forced to sign an agreement
regarding what I was allowed to say in the future regarding RSA and its
management.

[QUOTE=R.D. Silverman]I might say something about that, but as a condition of receiving severance pay when I was laid off from RSA Labs, I was forced to sign an agreement regarding what I was allowed to say in the future regarding RSA and its management.[/QUOTE]

Does it rhyme with "fame"? :wink: