
#1
Nov805, 05:03 AM

P: 23

Franke et al. factored RSA640 using GNFS
RSA640 31074182404900437213507500358885679300373460228427275457201619488232064 40518081504556346829671723286782437916272838033415471073108501919548529 007337724822783525742386454014691736602477652346609 The Factors are 16347336458092538484431338838650908598417836700330\ 92312181110852389333100104508151212118167511579 and 19008712816648221131268515739354139754718967899685\ 15493666638539088027103802104498957191261465571 



#2
Nov805, 08:40 AM

Sci Advisor
PF Gold
P: 1,355

Do you have a link?




#3
Nov805, 10:08 AM

Sci Advisor
HW Helper
P: 1,123





#4
Nov805, 12:23 PM

Sci Advisor
HW Helper
P: 9,428

RSA640 factored
pardon me, but why is that interesting?




#5
Nov805, 12:51 PM

Sci Advisor
HW Helper
P: 1,996

It has mass appeal for a few reasons, anyone can understand the problem of factoring and it is related to cryptography, which is always popular. The RSA number factored represents the "most successful" applications of the known general algorithms, so there's also some interest in what the algorithms can actually do in practice (though arguably this is not nearly as interesting as the math behind the various algorithms themselves). It's also an indicator of how secure RSA itself is with moduli of a given size (though obviously no one would go to the trouble of factoring a number of this size to steal your grandma's cookie recipe, unless it's really good).



#6
Nov805, 03:24 PM

P: n/a

How does GNFS and QNFS work?




#7
Nov805, 03:34 PM

Sci Advisor
PF Gold
P: 1,355

Mr Wonk, sir:
It effects the practicality of choosing/not choosing RSA keys of a given size. If you are a professional programmer, you need to be aware of this stuff as well. Think of it as an attempt at making the direct deposit of your paycheck secure  or your ATM transactions secure. This was "640 bit security"  your paycheck is moved over the (ACH system in the US) wires to your bank account with at a maximum  "256 bit security". While shmoe is right that the math is interesting, the development of factorization algorithms can be fun too. 


#8
Nov805, 03:55 PM

P: n/a

I did a lil research on the net, and couldn't really find any thing particularly detailed on the subject (wikipedia as a good bit on it, but a lil more would be nice), or examples of it in use, so I was hoping that someone might be able to tell me somewhere where there is more info on the details, or even better, explain some of the details in this thread. Also, how do they develop these algorithms, where do they start?




#9
Nov805, 03:59 PM

Emeritus
Sci Advisor
PF Gold
P: 16,101

RSA with a 640bit prime does is not equivalent securitywise to other algorithms with 640bit cryptovariables.
For those who want to learn about these, you might want to start with this: http://en.wikipedia.org/wiki/Dixon's_algorithm 



#10
Nov805, 06:49 PM

Sci Advisor
HW Helper
P: 9,428

thank you.
isn't it relevant to know how long it took to factor this number, and how much computing power, i.e. time and money, to measure the feasibility of such a task by a run of the mill hacker? also notice that the factors are roughly the same size, which is a big clue to any would be factorer. 



#11
Nov805, 09:56 PM

Sci Advisor
P: 1,132

http://en.wikipedia.org/wiki/Integer_factorization
"As of 2005, the largest semiprime factored using generalpurpose methods as part of public research is RSA200, which is 663 bits long. This was done using a network of computers running in parallel between Christmas 2003 and May 2005, and used very approximately 75 years total computer time. The method used was the general number field sieve." It's not an unexpensive computation. I imagine that it's best if the factors have the same number of bits because it increases the possible number of combinations. Factors with similar number of digits actually make it harder, it's alot better than having a huge factor and another one of 4 digits. This way i just try all 10^4 combinations to find the smaller factor and easily obtain the other one. It's worthwhile to mention that a quantum computer would be able to factor any sized RSA number in one computation. As a matter of fact, with just 1000 qubits, the size of the RSA number could have more digits then there are particles in the universe and it wouldn't make a difference. I find that to be cool. [when i say 1 computation i mean constant # of computations O(1), which would take considerably less than a second] 



#12
Nov805, 11:56 PM

Emeritus
Sci Advisor
PF Gold
P: 16,101

Of course, it's bad to have them too close, but with numbers that big, just having a 1% difference between them is an unimaginably huge range!




#13
Nov905, 09:19 AM

Sci Advisor
HW Helper
P: 1,996

There's a nice survey article “A Tale of Two Sieves”, Notices of the AMS 43, no. 12 (1996), 1473–1485 by Pomerance that might be of interest to finchie_88 (and others). It can be found at the AMS website (you'll have to create an account which is free). There are plenty more resources online such as Menzies "Handbook of Applied Cryptography" which has the details of many factoring algorithms (though not the gnfs). 


Register to reply 
Related Discussions  
Can this trinomial be factored?  Precalculus Mathematics Homework  6  
RSA200 Factored  Linear & Abstract Algebra  13  
Largest n had been factored  Linear & Abstract Algebra  5 