mersenneforum.org My plan for RSA factoring distributed computing
 Register FAQ Search Today's Posts Mark Forums Read

2009-03-16, 20:57   #12
akruppa

"Nancy"
Aug 2002
Alexandria

246710 Posts

Quote:
 Originally Posted by stathmk I'm factoring a 119-digit number using Alpertron's web site.
How long do you expect this will take?

Quote:
 Originally Posted by stathmk I'll eventually have people sign up for ranges for the 119-digit number.
You can easily factor it by youself, if you bother to learn how.

Quote:
 Originally Posted by stathmk I'm still studying ECMNET and GGNFS. Now, instead of using Alpertron's web site to factor RSA-170, I'll have to use ECMNET http://www.loria.fr/~zimmerma/records/ecmnet.html
I strongly advise you against using that program.

Quote:
 Originally Posted by stathmk or GGFNS. It will be GGFNS for everything above RSA-170related.
FTFY.

Alex

 2009-03-16, 21:03 #13 alpertron     Aug 2002 Buenos Aires, Argentina 56916 Posts stathmk, the algorithm ECM only is useful to find factors less than say N^(1/3) where N is the composite to be factored. Since you know in advance that the factors will be about N^(1/2) the algorithm ECM is a bad choice because it is very slow. In this case you should switch to Quadratic Sieve variants (MPQS, SIQS) for composites with less than about 97 digits and GNFS with greater numbers. Doing otherwise is wasting computer power. For example, for RSA-99, you needed more than 6 months using ECM but you need less than 2 days to factor it using the same applet. Last fiddled with by alpertron on 2009-03-16 at 21:04
2009-03-16, 21:29   #14
bsquared

"Ben"
Feb 2007

3·1,193 Posts

Quote:
 Originally Posted by stathmk I'm factoring a 119-digit number using Alpertron's web site. I'll eventually have people sign up for ranges for the 119-digit number.
I think you'll find you won't get any help until you know what your talking about a bit more. No one will (should) contribute to a project unless it is sensible, and this is not. You need the right tool for the job, and although Alpertron's applet is a great tool, it is not right for this job for a number of reasons.

 2009-03-17, 07:05 #15 10metreh     Nov 2008 2·33·43 Posts You certainly don't know enough. In your first post, you suggested that ECPP might be a better way to factor RSA-170. It is a primality proving algorithm, so it can't factor numbers. And BTW: the largest factor ECM has ever found is 67 digits. I'm not bothering to explain about B1 because stathmk might, er, will not understand it. The homework is amounting to several years. ECM is never the fastest method to completely factor an RSA-like number. For very small numbers it's TF, for slightly larger numbers SQUFOF comes into the picture, then MPQS and SIQS, until GNFS becomes fastest around 98 (it depends on your processor) digits. I have done eight GNFSs in the 99 digit range, and even on my slow computer, they have not taken much longer than 12 hours. Last fiddled with by 10metreh on 2009-03-17 at 07:09
2009-03-17, 11:52   #16
akruppa

"Nancy"
Aug 2002
Alexandria

2,467 Posts

Quote:
 Originally Posted by 10metreh I'm not bothering to explain about B1 because stathmk might, er, will not understand it.
Do you?

Alex

2009-03-17, 16:37   #17
10metreh

Nov 2008

1001000100102 Posts

Quote:
 Originally Posted by akruppa Do you? Alex
Although I don't know much about ECM works, I do know about how different B1s are optimal for different factor sizes.

2009-03-17, 20:42   #18
xilman
Bamboozled!

"ð’‰ºð’ŒŒð’‡·ð’†·ð’€­"
May 2003
Down not across

24·13·53 Posts

Quote:
 Originally Posted by 10metreh Although I don't know much about ECM works, I do know about how different B1s are optimal for different factor sizes.
We'll take that as a "no" then.

Paul

2009-03-18, 08:42   #19
10metreh

Nov 2008

91216 Posts

Quote:
 Originally Posted by xilman We'll take that as a "no" then. Paul
If that's what you count as a "no", then yes. Goodbye to this thread from me.

Last fiddled with by 10metreh on 2009-03-18 at 08:48

2009-03-19, 15:44   #20
stathmk

Mar 2009
Indiana, United Stat

1100002 Posts
RSA-99 SIQS Factoring

Quote:
 Originally Posted by alpertron With the new version of my factoring applet it should take less than 2 days to factor RSA-99 using SIQS. ...
Less than 3 days.
Quote:
 Originally Posted by alpertron ... I appreciate you post the output from the applet after the factorization finishes.
RSA-99 defined at Paul Zimmermannâ€™s web site: http://www.loria.fr/~zimmerma/records/rsa.html

Output:

256724393281137036243618548169692747168133997830674574560564321074494892576105743931776484232708881
= 4868376167980921239824329271069101142472222111193 (SIQS) x
52733064254484107837300974402288603361507691060217

Number of divisors: 4

Sum of divisors:
256724393281137036243618548169692747168133997830732176000986786103572017879779101636280464145880292

Euler's Totient:
256724393281137036243618548169692747168133997830616973120141856045417767272432386227272504319537472

Moebius: 1

Sum of squares: a^2 + b^2
a = 12175212534695709288611430416170136303858055842409
b = 10415785760859596241587413801588904681228188231840

Factorization complete in 2d 10h 15m 20s
ECM: 124970 modular multiplications
Prime checking: 188226 modular multiplications
SIQS: 19324689 polynomials sieved
969366 sets of trial divisions
32346 smooth congruences found (1 out of every 175777839 values)
388728 partial congruences found (1 out of every 14626448 values)
37098 useful partial congruences

Timings:
Primality test of 2 numbers: 0d 0h 0m 0.4s
Factoring 1 number using SIQS: 14322d 7h 26m 8.9s

mult mod: 313196

2009-03-19, 16:03   #21
bsquared

"Ben"
Feb 2007

3×1,193 Posts

Quote:
 Originally Posted by stathmk Less than 3 days.RSA-99 defined at Paul Zimmermannâ€™s web site: http://www.loria.fr/~zimmerma/records/rsa.html
Congratulations! You just wasted a bunch of electricity!

Edit:
On the plus side, it's a nice test of the applet, which I'm sure Dario is greatful for.

Last fiddled with by bsquared on 2009-03-19 at 16:04

 2009-03-19, 17:40 #22 alpertron     Aug 2002 Buenos Aires, Argentina 5×277 Posts Not at all if compared with the first attempt of factoring RSA-99 which used more than 6 months of ECM. So this was a cheap way to learn what algorithm not to use. Anyway notice that the applet uses the single large prime variation of SIQS. I don't know if there is enough space in memory to store the congruences that include double large primes (notice that applets cannot write to hard disk because of security concerns). A relatively easy way to make the applet faster in multicore processors is to have 2 to 4 (depending on the CPU) threads sieving.

 Similar Threads Thread Thread Starter Forum Replies Last Post a1call Miscellaneous Math 8 2018-05-21 16:25 flouran Math 2 2009-11-21 05:30 garo Lounge 11 2004-09-01 03:31 GP2 Lounge 2 2003-12-03 14:13 jocelynl Math 2 2002-11-23 00:27

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

Wed Dec 1 03:36:36 UTC 2021 up 130 days, 22:05, 1 user, load averages: 1.46, 1.50, 1.65