20081119, 23:28  #1 
Nov 2008
6_{10} 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.

20081120, 00:09  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{3}×7×163 Posts 
On a hundred smalltomedium jobs, I've found that you generally need
10 hrs for a SNFS150 100 hrs for a SNFS180 1000 hrs for a SNFS210 ... well, and obviously ... 1 hr for a SNFS120 Maybe twice that for a 32bit 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 GNFS150 will take as long as a SNFS210, about 1000 hrs. Cheers, Serge 
20081120, 03:02  #3 
Tribal Bullet
Oct 2004
110110100001_{2} Posts 
Sorry about the pessimistic estimate I sent via email...it used to be that you really did need a year for a 512bit RSA key.

20081120, 03:20  #4 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{3}·7·163 Posts 
Sorry to err on the optimistic side, too.
I've later thought that you should additionally account for: 1) you may mean 156digit number (e.g. for an RSA key) and this is not the same as 150digit. But even if it is 150digit... 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 ~40005000 cpu hours for a 150digit number, divided by 2 cpus = ~100 calendar days. For a 156digit number, ~200 calendar days (same 2 cpus) ~ a CPUyear. 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. 
20081120, 07:37  #5 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2^{2}×1,433 Posts 
why has no one suggested using ggnfs

20081120, 13:35  #6 
Tribal Bullet
Oct 2004
6641_{8} 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.

20081124, 23:39  #7 
Nov 2008
6_{8} Posts 
I see. If I am factoring a RSA key would it help if I know the E?

20081124, 23:42  #8 
Nov 2008
110_{2} 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. 
20081125, 00:20  #9  
May 2008
2105_{8} Posts 
Quote:


20081125, 01:36  #10  
"Ben"
Feb 2007
2·17·97 Posts 
Quote:
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()). 

20081125, 13:59  #11 
Tribal Bullet
Oct 2004
3×1,163 Posts 
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

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factor a 108digit number  sweety439  Factoring  9  20161221 21:22 
New 70 digit factor  R.D. Silverman  Cunningham Tables  16  20160123 22:16 
62digit prime factor of a Mersenne number  ET_  Factoring  39  20060511 18:27 
160 digit factor found of 366 digit (PRP1)  AntonVrba  Factoring  7  20051206 22:02 
Shortest time to complete a 2^67 trial factor (no factor)  dsouza123  Software  12  20030821 18:38 