Register FAQ Search Today's Posts Mark Forums Read

2009-05-29, 05:01   #12
Andi47

Oct 2004
Austria

2·17·73 Posts

Quote:
 Originally Posted by Shaopu Lin There is another ecm implementation which is available from http://www.cs.toronto.edu/~cvs/dlog/.
How fast is is - compared to GMP-ECM?

2009-05-29, 06:51   #13
10metreh

Nov 2008

232210 Posts

Quote:
 Originally Posted by Andi47 How fast is is - compared to GMP-ECM?
Quote:
 It can be used to find factors as large as 100 bits in a matter of hours on a typical PC.
Of what size of input number?

Last fiddled with by 10metreh on 2009-05-29 at 06:52

 2009-06-04, 05:49 #14 Shaopu Lin     Jul 2004 24·3 Posts There is another quadratic sieve implementation which is called basicqs and available from http://code.google.com/p/basicqs.
 2009-06-06, 02:26 #15 ATH Einyen     Dec 2003 Denmark 3×977 Posts Maybe add links to sieving and primality proving programs? Sieving: NewPGen: http://primes.utm.edu/programs/NewPGen/ / http://jpenne.free.fr/NewPGen/ (twin primes, Sophie Germain, Cunningham Chain) Multisieve: http://primes.utm.edu/bios/page.php?id=449 / http://www.primzahlenarchiv.de/softw...isieve_gui.zip (Cullens/Woodalls, Generalized/Hyper/Near Cullens/Woodalls, factorials, multifactorials, primodials and more) Fermat: http://www.fermatsearch.org/Fermat_44_beta.zip (sieve for fermat factors F24 ~ F2000) FermFact: http://www.fermatsearch.org/FermFact-09b.zip (sieve for fermat factors F2000 ~ F500000) gcwsieve: http://primes.utm.edu/bios/page.php?id=1223 (Generalized Cullen/Woodall n*bn+-1 ) srsieve: http://www.geocities.com/g_w_reynolds/srsieve/ (k*b^n+c with fixed b,multiple fixed k,c and variable n) sr1sieve: http://www.geocities.com/g_w_reynolds/sr1sieve/ (specialised for sieving a single sequence k*b^n+/-1) sr2sieve: http://www.geocities.com/g_w_reynolds/sr2sieve/ (a sieve for multiple sequences k*b^n+/-1 and b^n+/-k) sr5sieve: http://www.geocities.com/g_w_reynolds/sr5sieve/ (sieve for the Sierpinski/Riesel Base 5 projects) AP26: http://www.geocities.com/g_w_reynolds/AP26/ (BOINC app for finding record length 26 arithmetic progression of primes) APTreeSieve: http://primes.utm.edu/bios/page.php?id=809 (arithmetic progressions k*b + a with arbitrary a, b) Primality Proving: Primo: http://www.ellipsa.eu/public/misc/downloads.html (ECPP algorithm for general numbers, no special form) Proth: http://primes.utm.edu/programs/gallot/ (k*2n+1 2n > k) LLR: http://primes.utm.edu/bios/page.php?id=431 (k*2n+/-1 2n > k) OpenPFGW (PrimeForm): http://primes.utm.edu/bios/page.php?lastname=PrimeForm / http://www.fermatsearch.org/pfgw_ver...gw_winpfgw.zip (probable prime tests of arbitrary expressions) GeneFer: http://galloty.chez.com/primes/pgm/ (large probable generalized Fermat primes) Last fiddled with by ATH on 2009-06-06 at 03:00
2009-06-06, 12:39   #16
rogue

"Mark"
Apr 2003
Between here and the

2·3·983 Posts

Quote:
 Originally Posted by ATH Maybe add links to sieving and primality proving programs? Sieving: NewPGen: http://primes.utm.edu/programs/NewPGen/ / http://jpenne.free.fr/NewPGen/ (twin primes, Sophie Germain, Cunningham Chain) Multisieve: http://primes.utm.edu/bios/page.php?id=449 / http://www.primzahlenarchiv.de/softw...isieve_gui.zip (Cullens/Woodalls, Generalized/Hyper/Near Cullens/Woodalls, factorials, multifactorials, primodials and more) Fermat: http://www.fermatsearch.org/Fermat_44_beta.zip (sieve for fermat factors F24 ~ F2000) FermFact: http://www.fermatsearch.org/FermFact-09b.zip (sieve for fermat factors F2000 ~ F500000) gcwsieve: http://primes.utm.edu/bios/page.php?id=1223 (Generalized Cullen/Woodall n*bn+-1 ) srsieve: http://www.geocities.com/g_w_reynolds/srsieve/ (k*b^n+c with fixed b,multiple fixed k,c and variable n) sr1sieve: http://www.geocities.com/g_w_reynolds/sr1sieve/ (specialised for sieving a single sequence k*b^n+/-1) sr2sieve: http://www.geocities.com/g_w_reynolds/sr2sieve/ (a sieve for multiple sequences k*b^n+/-1 and b^n+/-k) sr5sieve: http://www.geocities.com/g_w_reynolds/sr5sieve/ (sieve for the Sierpinski/Riesel Base 5 projects) AP26: http://www.geocities.com/g_w_reynolds/AP26/ (BOINC app for finding record length 26 arithmetic progression of primes) APTreeSieve: http://primes.utm.edu/bios/page.php?id=809 (arithmetic progressions k*b + a with arbitrary a, b) Primality Proving: Primo: http://www.ellipsa.eu/public/misc/downloads.html (ECPP algorithm for general numbers, no special form) Proth: http://primes.utm.edu/programs/gallot/ (k*2n+1 2n > k) LLR: http://primes.utm.edu/bios/page.php?id=431 (k*2n+/-1 2n > k) OpenPFGW (PrimeForm): http://primes.utm.edu/bios/page.php?lastname=PrimeForm / http://www.fermatsearch.org/pfgw_ver...gw_winpfgw.zip (probable prime tests of arbitrary expressions) GeneFer: http://galloty.chez.com/primes/pgm/ (large probable generalized Fermat primes)
Don't forget phrot. There will be a link to the latest PFGW in a week or so (and hopefully sooner).

 2009-09-03, 05:29 #17 Shaopu Lin     Jul 2004 3016 Posts Another gnfs implementation, called kmGNFS, is available from http://kmgnfs.cti.gr/kmGNFS/Home.html.
 2009-11-30, 17:54 #18 bsquared     "Ben" Feb 2007 2·5·7·47 Posts Potentially a CUDA implementation of QS. I wonder if he was successful, and if he will make his implementation public.
 2010-03-16, 10:13 #19 msft     Jul 2009 Tokyo 10011000102 Posts To factor a Fermat number F_n = 2^(2^n)+1. http://www.perfsci.com/free-software.asp#giantint
2010-03-16, 18:46   #20
ET_
Banned

"Luigi"
Aug 2002
Team Italia

476610 Posts

Quote:
 Originally Posted by msft To factor a Fermat number F_n = 2^(2^n)+1. http://www.perfsci.com/free-software.asp#giantint
I used giantint library before stumbling on GMP. giantint is (was?) a full C library, and is slower than GMP implementation.

Luigi

 2010-10-01, 11:24 #21 siew   Oct 2009 1111112 Posts Are there any simple tools to get p,q from D and N ?Or some good small hex calc that can do this work? Or applet.
 2010-10-01, 12:38 #22 jasonp Tribal Bullet     Oct 2004 3,529 Posts If you know the private exponent d in RSA, then there's no point in factoring the modulus (you know the secret that can decrypt the communications of others). Now, if you don't care about the factors of the modulus but just want d, there are number-theoretic attacks that can break a weak RSA key. CrypTool has implemented one of them.

 Similar Threads Thread Thread Starter Forum Replies Last Post rogue Factoring 20 2014-11-19 01:08 rogue Factoring 32 2009-09-17 11:40 henryzz Factoring 6 2007-09-19 13:47 ixfd64 Factoring 1 2005-09-08 12:13 ixfd64 Factoring 1 2004-04-27 09:41

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

Fri Sep 18 20:56:52 UTC 2020 up 8 days, 18:07, 1 user, load averages: 1.56, 1.53, 1.63