Approximating Factoring Speed
 

Hello everyone,

I just want to ask if there is a formula to approximate a factoring speed of a computer or even anyway to guess it?

Thanks a lot

Check out this site...

[url]http://mersenne-aries.sili.net/throughput.php[/url]

I think the OP wanted a formula for approximating the runtime to factor general numbers. Asymptotically, all the best methods have subexponential runtime but that will not tell you much about how long a particular number takes. We usually fall back on statistical regressions based on large numbers of factorizations that folks here keep records on, assuming that the parameters of a QS or NFS job are chosen to approximately minimize the runtime at any given size.

[QUOTE=jasonp;193797]Asymptotically, all the best methods have subexponential runtime[/QUOTE]

But it is only proven for Dixon's method.

@petrw1: Well I've seen your website and I get a little confused. I'm trying to see how cracking RSA codes can be fast but this is seems to be for the merssene numbers or something like this. Please if there is something I can estimate the RSA factoring speed.

@jasonp: What about estimating Shaheen supercomputer factoring speed ([url]http://en.wikipedia.org/wiki/Shaheen_%28supercomputer%29)?[/url]

@R. Gerbicz: Is this method can help me :D. Even though I Google it and it seems to be a way of factorization.[URL="http://www.mersenneforum.org/member.php?u=1384"][COLOR=red][/COLOR][/URL]
[U][/U]

If you have a specific input size and a specific computer in mind, there isn't much that the theory can tell you. Look up published RSA factorization times and attempt to extrapolate them to the machine you have in mind. The largest RSA type factorization was 200 digits in 2005, which needed about 18 months on ~100 machines. If the inputs are large enough, the asymptotic runtime of the number field sieve can give an indication about how much longer a larger factorization would take on the same machine, all other things being equal.

But other things are not equal; cryptographic key sizes are chosen to make it infeasible for [i]any[/i] machine in the universe to break a large enough RSA key size given what we know about factoring algorithms. In the 1990s a 1024-bit RSA key was considered essentially impossible to break (you would need more computers than existed on earth).

Wikipedia contains many articles on integer factorization; [url="http://en.wikipedia.org/wiki/Integer_factorization"]start here[/url] if you have not already done so.

So there is no specific way to estimate RSA factoring speed in a computer that has never been on experiment and has no similar peer that try factoring RSA.

Using the NFS to factor even reasonable small RSA-type keys is something that would probably not be attempted on a single computer. The sieving stage is very feasibly done in a highly parallel fashion on a large number of machines. However, a very large number of "intermediate results" (relations) have to be transported to a common processing node. The speed of this part of the process is highly dependent on the I/O infrastructure connecting the various parts. As a result it is really difficult to judge just how well a new computer will be able to perform on this type of computation. However, some extrapolation is possible if you have reasonable data on other NFS sieving runs that have been performed on the same machine.

i seem to remember someone saying that adding 5 digits doubles the difficulty
that might be completely wrong though or maybe just for qs or something

That's something like the behavior I see for fairly big QS runs, but extrapolating that out to large sizes would imply that QS had exponential runtime. It does not, but for inputs around 70-100 digits that's a reasonable approximation.

By the time you get to 190-200 digit GNFS, the sieving is still manageable (your sieving machines will need at least 1GB of memory for each instance of the lattice sieving tools) but the postprocessing would probably need modest HPC resources, i.e. a cluster with a high-speed interconnect, to finish in under a year. More troubling is that even if you had such a cluster, you need a linear algebra solver that can scale beyond one machine, and there are no such codes publicly available other than the CADO tools, which are still under active development. People here use multithreaded msieve for problems somewhat smaller than this level, but still need heroically-large single machines.

My 12GB i7/920 is flattered to be called heroically large, but I see your point.

[quote=fivemack;193929]My 12GB i7/920 is flattered to be called heroically large, but I see your point.[/quote]
what size gnfs postprocessing would you guess that "heroically large" pc would be able to cope with?

Polynomial selection for large GNFS is significantly better now than it was for RSA200 four years ago (I really need to read with some detail the Bochum presentations; I wish I'd heard of that event in time to jump on a train to Bochum), and indeed significantly better than it was when the polynomial for RSA768 was found :smile:

[url]http://www.hyperelliptic.org/tanja/SHARCS/talks06/Jens_Franke.pdf[/url] has the polynomial for RSA200; but with 32-bit primes each side, alim=rlim=2e8, I get (on the fastest Linux x86-64 machine in the office)

[code]
% batalov-lasieve/gnfs-lasieve4I16e -a rsa200.poly -f 200000000 -c 1000
total yield: 139, q=200001001 (15.46540 sec/rel) (650MB RSZ)
% batalov-lasieve/gnfs-lasieve4I16e -a rsa200-alim400.poly -f 400000000 -c 1000
total yield: 181, q=400001009 (10.59718 sec/rel) (1300MB RSZ)
[/code]

which is an order of magnitude slower per relation than M941, and clearly not enough yield. So it really wants primes larger than 32-bit each side; and I'd not be confident running primes larger than 32-bit each side on the i7, it probably wouldn't fit and would take about a year if it did.

Say 190 digits, if NFS@home is available for the sieving. I've done the processing for a few 180ish-digit GNFS and a 276-digit SNFS. I may well set up a 190-digit GNFS polynomial selection (msieve-gpu-degree6) job once M941 is finished, though bdodson or frmky might get there before me.

[quote=fivemack;193983]
[URL]http://www.hyperelliptic.org/tanja/SHARCS/talks06/Jens_Franke.pdf[/URL] has the polynomial for RSA200; but with 32-bit primes each side, alim=rlim=2e8, I get (on the fastest Linux x86-64 machine in the office)
[/quote]

The polynomial in those slides indicates they used 35 bit large primes on each side. Memory use during sieving is driven by the small prime bound, right, so this would probably still fit in a reasonable amount of memory. You'd just need to gather an astronomically large number of relations (which, indeed, they did).

[quote=bsquared;193985]The polynomial in those slides indicates they used 35 bit large primes on each side. Memory use during sieving is driven by the small prime bound, right, so this would probably still fit in a reasonable amount of memory. You'd just need to gather an astronomically large number of relations (which, indeed, they did).[/quote]
I think he means he wont have enough memory for postprocessing.

[b]fivemack:[/b] Precisely

[quote=henryzz;194046]I think he means he wont have enough memory for postprocessing.[/quote]

I suppose that could be. Speaking of which, we are soon going to get a rather impressive workstation here at work: 2 processor (16 cpus, with hyperthreading) Xeon 5570 with 96 GB 1333 DDR3 ECC RAM. But it will mostly be consumed with other work :cry:

[QUOTE=bsquared;194079]I suppose that could be. Speaking of which, we are soon going to get a rather impressive workstation here at work: 2 processor (16 cpus, with hyperthreading) Xeon 5570 with 96 GB 1333 DDR3 ECC RAM. But it will mostly be consumed with other work :cry:[/QUOTE]

Who is the vendor?

[quote=R.D. Silverman;194082]Who is the vendor?[/quote]

It is a Dell blade.

Oh, and a correction, we are getting 3 of those blades. I'll probably be able to use them for sieving occasionally, but I likely won't be able to monopolize any of them long enough for a large post-processing job.