Python Driver for GGNFS and MSIEVE

[bsquared]

Originally Posted by KenshinPT

I think I get it, but... let me say what I understood :)

... you mean that all possibilities (brute force) would take 2000 years to solve on a single CPU... but as this is brute force, this could take less...

For example: If you're lucky or if both primes are very close it could take 1 week, one day or one hour!?!

That's it?

I was talking about how the running time of the number field sieve factorization method scales with the size of the input number. If it takes a 232 digit number 2000 years on one cpu, then a 265 digit number will take 200,000 years (give or take a few millenia ).

Brute force (i.e. trial division or fermat's method) is out of the question for numbers of this size if the two primes are randomly chosen and have the same number of digits. Really, any factorization method is out of the question if that is true, but I'm trying to let you discover the futility of it for yourself.

[R.D. Silverman]

Originally Posted by KenshinPT

"The effort took almost 2000 2.2GHz-Opteron-CPU years according to the submitters, just short of 3 years of calendar time."

Sometimes I enjoy when I am wrong :D but does this means that if I have one 2.2GHz-Opteron-CPU it would take 2000 years to solve?!

Well... I just need to find more 1999 computers and then I can solve it in one year :D

It also takes a large, very tightly coupled (e.g. Infiniband speed or better)
parallel computer with at least 1 Terabyte of memory to do the linear
algebra.

It would be hard to buy this system at PC's 'R' Us.

[R.D. Silverman]

Originally Posted by KenshinPT

I think I get it, but... let me say what I understood :)

... you mean that all possibilities (brute force) would take 2000 years to solve on a single CPU... but as this is brute force, this could take less...

Estimate the number of primes that need to be searched. Assume you
can do 10^20 per second on each CPU and that you had 10^20 such
computers. There are ~31 million seconds in a year. Now estimate
the number of years it would take you.

For example: If you're lucky or if both primes are very close it could take 1 week, one day or one hour!?!

That's it?

Try 10^100 YEARS.

[firejuggler]

no, it mean that the work done would take a single opteron @2.2Ghz 2000 year, but in fact took only 3 "real year', calendar time, to accomplish that factorisation.
multicore at work here.
imagine you have a dual core opteron working 24h/24 365d/365, you produce 2 2.2GHz-opteron cpu year in 1 year calendar time.
Now with my i5 2500k, clocked at 3.3Ghz , with its 4 core would produce (speed increase = production increase, to keep it simple) 4*1.5 =6 2.2GHz opteron-cpu year.
so a total of 8 opteron cpu-year
the submiter got 2000 cpu-year in 3 calendar year. That mean a lot of computer were involved.

[KenshinPT]

Originally Posted by R.D. Silverman

Try 10^100 YEARS.

Does that means I should hit CRTL+C?

[fivemack]

Originally Posted by KenshinPT

I think I get it, but... let me say what I understood :)

... you mean that all possibilities (brute force) would take 2000 years to solve on a single CPU... but as this is brute force, this could take less...

For example: If you're lucky or if both primes are very close it could take 1 week, one day or one hour!?!

No, this is not the brute-force method. RSA768 was factored using the GNFS method; this is the most efficient method currently known, and one of its features is that it runs in a time independent of the size of the prime factors. You know when you start the job how long it will take to finish, and the answer for a 265-digit general number is about 200,000 Opteron-years - that is, a year on a supercomputer which costs about twenty million pounds.

[firejuggler]

or, if you have 33 334 i5-2500k clocked at stock speed, you can do it in one year, 10 000 if you want in a bit above 3 years. that, working 24H/24, no break.
Even using fivemack's 48 core monster ( running at 2GHz if my memory serve), it would require 4583.33 years to get enough relations to start the final step. Now, imagining you have enough money to buy 1528 of those system, it will take 3 years to prepare the data.
And That, is the most effective way (to this day)

[bsquared]

Originally Posted by firejuggler

Now, imagining you have enough money to buy 1528 of those system, it will take 3 years to prepare the data.
And That, is the most effective way (to this day)

Scaling the number of some suitably fast computer might* get you the data you need, but won't get you the factors. To have a hope of getting the factors on the same time scale at which you obtained the data, you will need a much more expensive system to run the post-processing.


*assuming facts not in currently in evidence about the software required to do the sieving. Namely, that AFAIK, neither ggnfs nor msieve has been attempted to be run on numbers of this size and may not work at all.

[KenshinPT]

Thanks you so much for the replies. Now everything is more clear :)

[Walter Nissen]

Does a slightly smaller lp produce a matrix which will require less
RAM to solve ?
If lpbr = lpba = 29 is optimal for an s204 , but only 1.4 GiB of
RAM is available , might lp = 28 be a better choice than 29 ?

[jasonp]

Yes, a smaller LP generates a somewhat smaller matrix. Whether this is better than using a larger LP depends on how fast relations are accumulating. Your choice of LP determines how long you have until you run out of non-duplicated relations, or run out of relations entirely, so for large jobs the choice is dealing with a big matrix or not generating a matrix at all.

You can reduce the effect of a too-big matrix by sieving more, but that eats into the gain in relation rate from using a larger LP. Plus there's a poorly-understood limit to the extent that oversieving will reduce the matrix size.