mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Open Projects

Reply
 
Thread Tools
Old 2009-03-16, 20:57   #12
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Quote:
Originally Posted by stathmk View Post
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 View Post
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 View Post
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 View Post
or GGFNS. It will be GGFNS for everything above RSA-170related.
FTFY.

Alex
akruppa is offline   Reply With Quote
Old 2009-03-16, 21:03   #13
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22·3·5·23 Posts
Default

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
alpertron is offline   Reply With Quote
Old 2009-03-16, 21:29   #14
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

DFA16 Posts
Default

Quote:
Originally Posted by stathmk View Post
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.
bsquared is offline   Reply With Quote
Old 2009-03-17, 07:05   #15
10metreh
 
10metreh's Avatar
 
Nov 2008

44228 Posts
Default

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
10metreh is offline   Reply With Quote
Old 2009-03-17, 11:52   #16
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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

Alex
akruppa is offline   Reply With Quote
Old 2009-03-17, 16:37   #17
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

Quote:
Originally Posted by akruppa View Post
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.
10metreh is offline   Reply With Quote
Old 2009-03-17, 20:42   #18
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2×3×52×73 Posts
Default

Quote:
Originally Posted by 10metreh View Post
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
xilman is offline   Reply With Quote
Old 2009-03-18, 08:42   #19
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

Quote:
Originally Posted by xilman View Post
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
10metreh is offline   Reply With Quote
Old 2009-03-19, 15:44   #20
stathmk
 
stathmk's Avatar
 
Mar 2009
Indiana, United Stat

24·3 Posts
Thumbs up RSA-99 SIQS Factoring

Quote:
Originally Posted by alpertron View Post
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 View Post
... 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
stathmk is offline   Reply With Quote
Old 2009-03-19, 16:03   #21
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

357810 Posts
Default

Quote:
Originally Posted by stathmk View Post
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
bsquared is offline   Reply With Quote
Old 2009-03-19, 17:40   #22
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22×3×5×23 Posts
Default

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.
alpertron is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Etiquettes of Distributed Computing a1call Miscellaneous Math 8 2018-05-21 16:25
Massively distributed computing and factoring... flouran Math 2 2009-11-21 05:30
Distributed Computing Survey garo Lounge 11 2004-09-01 03:31
The difference between P2P and distributed computing and grid computing GP2 Lounge 2 2003-12-03 14:13
P-1 factoring as distributed computing jocelynl Math 2 2002-11-23 00:27

All times are UTC. The time now is 17:29.


Tue Oct 19 17:29:59 UTC 2021 up 88 days, 11:58, 0 users, load averages: 1.13, 1.22, 1.22

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.