mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2008-11-19, 23:28   #1
ladderbook
 
Nov 2008

610 Posts
Default 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.
ladderbook is offline   Reply With Quote
Old 2008-11-20, 00:09   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23×7×163 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2008-11-20, 03:02   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

1101101000012 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2008-11-20, 03:20   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23·7·163 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2008-11-20, 07:37   #5
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22×1,433 Posts
Default

why has no one suggested using ggnfs
henryzz is offline   Reply With Quote
Old 2008-11-20, 13:35   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

66418 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2008-11-24, 23:39   #7
ladderbook
 
Nov 2008

68 Posts
Default

I see. If I am factoring a RSA key would it help if I know the E?
ladderbook is offline   Reply With Quote
Old 2008-11-24, 23:42   #8
ladderbook
 
Nov 2008

1102 Posts
Default

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.
ladderbook is offline   Reply With Quote
Old 2008-11-25, 00:20   #9
jrk
 
jrk's Avatar
 
May 2008

21058 Posts
Default

Quote:
Originally Posted by ladderbook View Post
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.
jrk is offline   Reply With Quote
Old 2008-11-25, 01:36   #10
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·17·97 Posts
Default

Quote:
Originally Posted by ladderbook View Post
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()).
bsquared is offline   Reply With Quote
Old 2008-11-25, 13:59   #11
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,163 Posts
Default

Quote:
Originally Posted by ladderbook View Post
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
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factor a 108-digit number sweety439 Factoring 9 2016-12-21 21:22
New 70 digit factor R.D. Silverman Cunningham Tables 16 2016-01-23 22:16
62-digit prime factor of a Mersenne number ET_ Factoring 39 2006-05-11 18:27
160 digit factor found of 366 digit (PRP-1) AntonVrba Factoring 7 2005-12-06 22:02
Shortest time to complete a 2^67 trial factor (no factor) dsouza123 Software 12 2003-08-21 18:38

All times are UTC. The time now is 03:58.

Wed Oct 28 03:58:24 UTC 2020 up 48 days, 1:09, 2 users, load averages: 1.86, 1.80, 1.76

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.