mersenneforum.org Time needed to factor a 150 digit number
 Register FAQ Search Today's Posts Mark Forums Read

 2008-11-19, 23:28 #1 ladderbook   Nov 2008 2·3 Posts Time needed to factor a 150 digit number 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.
 2008-11-20, 00:09 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 24×631 Posts 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
 2008-11-20, 03:02 #3 jasonp Tribal Bullet     Oct 2004 67478 Posts 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.
 2008-11-20, 03:20 #4 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100111011100002 Posts 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.
 2008-11-20, 07:37 #5 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 6,053 Posts why has no one suggested using ggnfs
 2008-11-20, 13:35 #6 jasonp Tribal Bullet     Oct 2004 3,559 Posts 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.
 2008-11-24, 23:39 #7 ladderbook   Nov 2008 68 Posts I see. If I am factoring a RSA key would it help if I know the E?
 2008-11-24, 23:42 #8 ladderbook   Nov 2008 2×3 Posts 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.
2008-11-25, 00:20   #9
jrk

May 2008

44716 Posts

Quote:
 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.

2008-11-25, 01:36   #10
bsquared

"Ben"
Feb 2007

23×163 Posts

Quote:
 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()).

2008-11-25, 13:59   #11
jasonp
Tribal Bullet

Oct 2004

1101111001112 Posts

Quote:
 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

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 9 2016-12-21 21:22 R.D. Silverman Cunningham Tables 16 2016-01-23 22:16 ET_ Factoring 39 2006-05-11 18:27 AntonVrba Factoring 7 2005-12-06 22:02 dsouza123 Software 12 2003-08-21 18:38

All times are UTC. The time now is 00:18.

Tue Mar 28 00:18:59 UTC 2023 up 221 days, 21:47, 0 users, load averages: 1.31, 1.03, 1.03