mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2006-02-24, 10:14   #1
koders333
 

3·617 Posts
Arrow Running time for GNFS

Now I am implementing GNFS algorithm in C++.
Anyone please tell me about the runnong time for GNFS algorithm to factor 128 bit numbers in a single machine.Is it possible to factor a 256 bit number using a single machine & how much time it will take for successful factorization?
  Reply With Quote
Old 2006-02-24, 14:38   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2·3·13·137 Posts
Default

Quote:
Originally Posted by koders333
Now I am implementing GNFS algorithm in C++.
Anyone please tell me about the runnong time for GNFS algorithm to factor 128 bit numbers in a single machine.Is it possible to factor a 256 bit number using a single machine & how much time it will take for successful factorization?
I suggest that you get hold of an existing GNFS implementation and answer those questions by experiment. A good search term for finding an implementation is "ggnfs".

I could tell you the answers but you will learn much more by following my advice.

Ok then --- the answers are:

a few seconds to a few minutes, depending on your hardware and the efficiency of your code;

yes;

a few minutes to a few hours, depending on your hardware and the efficiency of your code.



Paul
xilman is offline   Reply With Quote
Old 2006-02-24, 23:32   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

1101110100102 Posts
Default

Quote:
Originally Posted by koders333
Now I am implementing GNFS algorithm in C++.
Anyone please tell me about the runnong time for GNFS algorithm to factor 128 bit numbers in a single machine.Is it possible to factor a 256 bit number using a single machine & how much time it will take for successful factorization?
You can use pgnfs as a baseline (www.pgnfs.org). Note that it's a *really* basic implementation.

jasonp
jasonp is online now   Reply With Quote
Old 2006-02-27, 07:00   #4
koders333
 

11000110001012 Posts
Default

Quote:
Originally Posted by xilman
I suggest that you get hold of an existing GNFS implementation and answer those questions by experiment. A good search term for finding an implementation is "ggnfs".

I could tell you the answers but you will learn much more by following my advice.

Ok then --- the answers are:

a few seconds to a few minutes, depending on your hardware and the efficiency of your code;

yes;

a few minutes to a few hours, depending on your hardware and the efficiency of your code.



Paul
Thank You Paul.
Why we are still using 256 bit RSA keys in PGP(email security)?.
I think PGP is secured only because of SHA (signature algorithm). Is it correct?
Can we replace RSA with ECC?.
  Reply With Quote
Old 2006-02-27, 14:33   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×29×61 Posts
Default

Quote:
Originally Posted by koders333
Thank You Paul.
Why we are still using 256 bit RSA keys in PGP(email security)?.
I think PGP is secured only because of SHA (signature algorithm). Is it correct?
Can we replace RSA with ECC?.
(The international version of) PGP defaults to using 1024 bit Diffie Hellman, i.e. 1024 bit moduli with I think 160 bit keys, or 1024-bit RSA, or 1024-bit DSA. The default (exportable) security level in web browsers is 512-bit RSA, meaning the *factors* of the modulus are 256 bits long.

256 bits is a little over 80 digits. Msieve can do factorizations that size in about 20-25 minutes, so yes this size is not secure at all. But an RSA modulus is twice the size of its factors, and 512 bit factorizations are still hard.

SHA is the Secure Hash Algorithm, and is just a way to crunch arbitrary size messages down to a size where the entire message can be processed at once by whatever public key algorithm your copy of PGP is configured to use. Primarily it's there to prevent duplicate/forged data from being signed; it in no way affects the security of the signature process itself.

Maybe you should skim through Schneier's 'Applied Cryptography' if you have cryptographic applications in mind.

jasonp

Last fiddled with by jasonp on 2006-02-27 at 14:37
jasonp is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Estimating time needed for GNFS CRGreathouse Factoring 16 2014-03-10 03:40
Estimating time needed for GNFS CRGreathouse Factoring 0 2014-03-02 04:18
Cons of running LLR on laptop full time. Flatlander Hardware 21 2010-05-31 14:56
GNFS poly search time limit oddity Andi47 Msieve 13 2009-02-25 12:33
Running Prime95 only is a special time slot prehaeus Software 1 2004-04-22 21:54

All times are UTC. The time now is 20:28.

Mon May 17 20:28:52 UTC 2021 up 39 days, 15:09, 0 users, load averages: 2.53, 2.60, 2.81

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.