Time needed to factor a 150 digit number

[ladderbook]

Hi I would like to ask how long does it take for factoring a 150 digits number using msieve? I have 3gb ram and using 1.6 ghz dual core.

[Batalov]

On a hundred small-to-medium jobs, I've found that you generally need
10 hrs for a SNFS-150
100 hrs for a SNFS-180
1000 hrs for a SNFS-210
... well, and obviously ...
1 hr for a SNFS-120

Maybe twice that for a 32-bit OS.

For a GNFS estimate, first multiply #digits by 1.4, then look up in the table above. So if your number has no special form, a GNFS-150 will take as long as a SNFS-210, about 1000 hrs.

Cheers,
Serge

[jasonp]

Sorry about the pessimistic estimate I sent via email...it used to be that you really did need a year for a 512-bit RSA key.

[Batalov]

Sorry to err on the optimistic side, too.

I've later thought that you should additionally account for:
1) you may mean 156-digit number (e.g. for an RSA key) and this is not the same as 150-digit. But even if it is 150-digit...
2) 1.4 ad hoc factor may be too optimistic (10/7 is about right; note - it goes into the exponent, so it is not so unimportant)
3) considering 1.6GHz CPU, you may additionally double the estimate above.
4) the polynomial search time (and the batteries) are not included.

So, with your CPU, it may be ~4000-5000 cpu hours for a 150-digit number, divided by 2 cpus = ~100 calendar days.

For a 156-digit number, ~200 calendar days (same 2 cpus) ~ a CPU-year. So Jason is right there on target, too.

But if you have a 100 of those cpus... then you are not going to be bored.

[henryzz]

why has no one suggested using ggnfs

[jasonp]

Those times assume using the same GGNFS software (possibly with msieve postprocessing) everyone here uses. If you don't use the number field sieve, scale the runtime up to +infinity. The largest QS factorization is 136 digits and it took months, so nobody is in a hurry to beat that record.

[ladderbook]

I see. If I am factoring a RSA key would it help if I know the E?

[ladderbook]

Now I have another question. If I want to create a number of about 190 digits that should be extremely difficult to factorize. What should my approach to create this number? (Other than choosing 2 prime number as the factor, what other consideration could I take?)

Thanks.

[jrk]

Originally Posted by ladderbook

Now I have another question. If I want to create a number of about 190 digits that should be extremely difficult to factorize. What should my approach to create this number? (Other than choosing 2 prime number as the factor, what other consideration could I take?)

The two primes should be safe primes.

[bsquared]

Originally Posted by ladderbook

Now I have another question. If I want to create a number of about 190 digits that should be extremely difficult to factorize. What should my approach to create this number? (Other than choosing 2 prime number as the factor, what other consideration could I take?)

Thanks.

Gordon's algorithm is a method to quickly generate strong primes. It is given in section 4.53 of the Handbook of Applied Cryptography . An extremely difficult number to factor would be composed of two large strong primes of similar size.

Yafu has an implementation of this (not optimized much for speed yet), for generating strong pseudoprimes up to a few thousand bits long (function rsa()).

[jasonp]

Originally Posted by ladderbook

I see. If I am factoring a RSA key would it help if I know the E?

That actually is a hard question. If e is small there is no known way to use that to break RSA faster, however if the private exponent is small (i.e. smaller than about 1/3 the size of the modulus) there are attacks on RSA that are faster than factoring