Hacker News new | past | comments | ask | show | jobs | submit login

No. What you're seeing in that log is only the two last steps in the number field sieve: linear algebra and the square root step. The rest of the details are missing.

The time of the square root is where you are seeing the 52 hours. That time is essentially 0 in relation to the whole process.

You can also see that the last 1033963 - 1026631 = 7332 iterations of Lanczos (on a 64Mx64M ~24GB matrix!) took 15 hours. We can then estimate that the matrix step required around 3 months on that particular setup.

We don't know anything about the sieving, but I'd venture it took significantly more computing power than the matrix, as is usually the case.




The sieving stage can be massively parallel and doesn't require large amounts of memory, with enough machines you could perform the sieve stage in under a day (and with more machines within an hour). A 100,000 node botnet could be very useful in this regard.

Knowing when you've got enough relations is an inexact science given there will be some duplicates amongst relations generated on separate machines, so it's not uncommon for a final bit of sieving to be required once msieve is pointed at the combined relations file (which is seen in the log).

It's the block Lanczos and matrix square root steps that cannot be parallelised efficiently[1].

Interest in the various Number Field Sieve algorithms (SNFS/GNFS) is one of the main reasons I started (and finished!) a part time degree in Mathematics to go along with my Comp Sci degree. Next on the list (after a break from 8 years of part time study) will be the M.Sc. courses[2].

1. It can be parallelised, but not efficiently, i.e. throwing 10 similar machines at the problem does not get the job done in a tenth of the time, only ~95% of the time. No efficient algorithm exists for doing this. Yet. If that does appear then RSA starts to look very very shaky.

2. The first of which (M820 The Calculus of Variations and Advanced Calculus) can be downloaded from here:

    http://chilli.open.ac.uk/dr9/
Yes, the entire course can be downloaded, (although it's more of a guided read of Apostol than a series of lectures.)


I'm not aware M823 can be downloaded (which is the first of the two number theory courses using Apostol)


Yes, sorry, got the courses mixed up.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: