mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-11-21, 10:18   #1
koders333
 

23·1,097 Posts
Question Same team factored RSA challenge numbers in recent time

J. Franke & his team factord all recent challenge(Rsa576, Rsa200 & Rsa640) numbers.

1)All three numbers are factored using GNFS.This is widely known algorithm.Why others can't factor challenge numbers?.
2)Is they follow any unpublished tricks in either Polynominal selection,sieving & matrix step?.
3)What is the cost of factoring?.& how much money spend for factoring & anticipated return ?.
4) Why NFSNET project not aims to solve RSA challenge numbers?
5)The main objective of prime factorization research is to predict secure key size for crpto systems which security is based on the hardness of factoring.In real time networks people are still using 128 bit RSA keys .Because they are having multilayer security using more than one cryptographic algorithm.So the prime factorization research are not impotant to industry.Whether this statement is true or not?.

Last fiddled with by koders333 on 2005-11-21 at 10:23
  Reply With Quote
Old 2005-11-21, 10:39   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

101000100110112 Posts
Default

Quote:
Originally Posted by koders333
J. Franke & his team factord all recent challenge(Rsa576, Rsa200 & Rsa640) numbers.

1)All three numbers are factored using GNFS.This is widely known algorithm.Why others can't factor challenge numbers?.
2)Is they follow any unpublished tricks in either Polynominal selection,sieving & matrix step?.
3)What is the cost of factoring?.& how much money spend for factoring & anticipated return ?.
4) Why NFSNET project not aims to solve RSA challenge numbers?
5)The main objective of prime factorization research is to predict secure key size for crpto systems which security is based on the hardness of factoring.In real time networks people are still using 128 bit RSA keys .Because they are having multilayer security using more than one cryptographic algorithm.So the prime factorization research are not impotant to industry.Whether this statement is true or not?.
1) Do you mean other groups or other algorithms?

2) Not as far as I know. Note that is a statement of ignorance. It is not a statement that they do not use unpublished methods.

3) Cost is very hard to estimate. The cost is almost certainly much more than the prize money gained from the factorizations. The power and environmental expenses to run almost a hundred machines for almost six months is noticeable. Six months is a noticeable fraction of the lifetime of the machines, so you need to pay that fraction of the purchase cost. A significant amount of time is used by highly skilled people (though not always highly paid!) is required to complete a bleeding-edge factorization. Those people expect to be paid, to have office space and facilities and so on.

4) Two reasons. The first is that they are too hard for our resources. The other is that prize money is given for a successful result. The administrative hassles in dealing with the prize money is a very real disincentive.

5) To the best of my knowledge, no-one is using 128-bit RSA keys for anything other than educational purposes. 128-bit symmetric encryption keys (e.g, for AES) are very widely used but that is an entirely different matter from RSA. My personal view is that integer factorization is not particularly important to industry in general (compared with the price of oil, for instance) but that it has some interest to the providers of cryptographic software.


Paul
xilman is online now   Reply With Quote
Old 2005-11-21, 13:50   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

1101110011002 Posts
Default

Quote:
Originally Posted by koders333
1)All three numbers are factored using GNFS.This is widely known algorithm.Why others can't factor challenge numbers?.
There are only a few teams that have a lot of computers and are not afraid to use NFS: Franke/Kleinjung, CWI, NFSNET, Aoki et. al. (Alex too, but maybe not for much longer?). Only the first team makes a point of going after RSA challenge numbers.

Everybody else who goes after RSA challenge numbers seems to think they can get by with more computers but less math. Is it any wonder that only Franke et. al. succeed?

Quote:
5)The main objective of prime factorization research is to predict secure key size for crpto systems which security is based on the hardness of factoring.In real time networks people are still using 128 bit RSA keys
The default public key size used by modern browsers, that is intended to avoid export restrictions from the US, is 512 bits. Aoki et. al. showed that it takes 100 modern machines about two months to factor a 512-bit modulus.

jasonp
jasonp is offline   Reply With Quote
Old 2005-11-21, 19:35   #4
sean
 
sean's Avatar
 
Aug 2004
New Zealand

22×5×11 Posts
Default

Quote:
Originally Posted by jasonp
The default public key size used by modern browsers, that is intended to avoid export restrictions from the US, is 512 bits. Aoki et. al. showed that it takes 100 modern machines about two months to factor a 512-bit modulus.

jasonp
In my experience using the Franke implementation of GNFS it would "only" take about 10 modern commodity machines to factor a 512-bit number in 2 months. For example, I factored 118!+1 C151 in 49 days using about 10 CPUs (some of which were only 1 GHz). Also, half the time was taken up with the linear algebra, mainly because I do not have a distributed block-Lanczos implementation.
sean is offline   Reply With Quote
Old 2005-11-21, 21:04   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

1039510 Posts
Default

Quote:
Originally Posted by sean
In my experience using the Franke implementation of GNFS it would "only" take about 10 modern commodity machines to factor a 512-bit number in 2 months. For example, I factored 118!+1 C151 in 49 days using about 10 CPUs (some of which were only 1 GHz). Also, half the time was taken up with the linear algebra, mainly because I do not have a distributed block-Lanczos implementation.
Six years ago we took only 7 months elapsed and 300-ish machines to factor a 512-bit key. "We" being CWI, Microsoft Research and a number of others, including at least one other(Jeff Gilchrist) who contributes to this forum.

If you use a value of 18 months for the exponent in Moore's law and assume no algorithmic improvements (a false assumption), factoring should be 16 (i.e., 2^{6/1.5}) times easier today. You should be able to conclude that factoring a 512-bit number ought to take around 75 machines running for 2 months.

The discrepancy between this estimate of 75 machines and Sean's of 10 is, in my opinion, largely due to algorithmic improvements. In particular, modern polynomial finding algorithms produce markedly better polynomials than were available in 1999. Roughly 1/3 of the difference is due to the fact that all 350 machines were not running continuously for the 7 months elapsed time.


Paul
xilman is online now   Reply With Quote
Old 2005-11-21, 21:12   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Question

Quote:
Originally Posted by xilman
Six years ago we took only 7 months elapsed and 300-ish machines to factor a 512-bit key. "We" being CWI, Microsoft Research and a number of others, including at least one other(Jeff Gilchrist) who contributes to this forum.

If you use a value of 18 months for the exponent in Moore's law and assume no algorithmic improvements (a false assumption), factoring should be 16 (i.e., 2^{6/1.5}) times easier today. You should be able to conclude that factoring a 512-bit number ought to take around 75 machines running for 2 months.

The discrepancy between this estimate of 75 machines and Sean's of 10 is, in my opinion, largely due to algorithmic improvements. In particular, modern polynomial finding algorithms produce markedly better polynomials than were available in 1999. Roughly 1/3 of the difference is due to the fact that all 350 machines were not running continuously for the 7 months elapsed time.


Paul
Didn't you use a line siever?
R.D. Silverman is offline   Reply With Quote
Old 2005-11-21, 21:16   #7
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

33·5·7·11 Posts
Default

Quote:
Originally Posted by R.D. Silverman
Didn't you use a line siever?
I personally used both a line siever and a lattice siever, with more significantly more effort coming from the latter.

I forget now exactly how much effort came from the CWI line siever and from Arjen Lenstra's lattice siever.


Paul
xilman is online now   Reply With Quote
Old 2005-11-21, 21:21   #8
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

33×5×7×11 Posts
Default

Quote:
Originally Posted by R.D. Silverman
Didn't you use a line siever?
More details from http://ftp.cwi.nl/herman/NFSrecords/RSA-155 where you will discover that quite a few of us used a lattice siever.

Paul
xilman is online now   Reply With Quote
Old 2005-11-22, 10:11   #9
koders333
 

1C4C16 Posts
Default

Quote:
Originally Posted by sean
In my experience using the Franke implementation of GNFS it would "only" take about 10 modern commodity machines to factor a 512-bit number in 2 months. For example, I factored 118!+1 C151 in 49 days using about 10 CPUs (some of which were only 1 GHz). Also, half the time was taken up with the linear algebra, mainly because I do not have a distributed block-Lanczos implementation.
is it possible to factor any 512 bit number using that implementation in same amout of time?.(either Time & resources are same for prime factorization of all 512 bit numbers or it will be depends upon the unknown prime factors)
My tutor says all prime factorization algorithms are intelligent brute force methods. is it true?
  Reply With Quote
Old 2005-11-22, 10:25   #10
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

33·5·7·11 Posts
Default

Quote:
Originally Posted by koders333
is it possible to factor any 512 bit number using that implementation in same amout of time?.(either Time & resources are same for prime factorization of all 512 bit numbers or it will be depends upon the unknown prime factors)
My tutor says all prime factorization algorithms are intelligent brute force methods. is it true?
GNFS takes about the same time to factor all numbers of the same size (other than prime powers, that is). There is a small amount of variation, but the differences are usually less than a factor of ten (and usually much less) in practice.

The statement made by your tutor is at best immensely misleading. The term "brute force" is not adequately defined. If it is used as shorthand for "division by all primes", then the statement is just plain wrong.


Paul
xilman is online now   Reply With Quote
Old 2005-11-23, 20:58   #11
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

22218 Posts
Default

Quote:
Originally Posted by xilman
Six years ago we took only 7 months elapsed and 300-ish machines to factor a 512-bit key. "We" being CWI, Microsoft Research and a number of others, including at least one other(Jeff Gilchrist) who contributes to this forum.
Ah the memories... Wow, was that 6 years ago already? And the software was all manual back then, manually selecting ranges, uploading results by FTP, etc...

Jeff.
Jeff Gilchrist is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Runs of factored numbers henryzz Factoring 8 2017-03-09 19:24
Factored vs. Completely factored aketilander Factoring 4 2012-08-08 18:09
longest time between prime ages in recent history jasong Puzzles 12 2007-12-30 14:59
Powerful Numbers programming challenge geoff Programming 31 2005-02-20 18:25
Odd Perfect numbers - a factoring challenge philmoore Factoring 63 2005-01-06 03:09

All times are UTC. The time now is 08:50.

Thu Dec 3 08:50:55 UTC 2020 up 5:02, 0 users, load averages: 2.15, 1.99, 1.59

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.