mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2009-05-29, 05:01   #12
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

248210 Posts
Default

Quote:
Originally Posted by Shaopu Lin View Post
There is another ecm implementation which is available from http://www.cs.toronto.edu/~cvs/dlog/.
How fast is is - compared to GMP-ECM?
Andi47 is offline   Reply With Quote
Old 2009-05-29, 06:51   #13
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

Quote:
Originally Posted by Andi47 View Post
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
10metreh is offline   Reply With Quote
Old 2009-06-04, 05:49   #14
Shaopu Lin
 
Shaopu Lin's Avatar
 
Jul 2004

24×3 Posts
Default

There is another quadratic sieve implementation which is called basicqs and available from http://code.google.com/p/basicqs.
Shaopu Lin is offline   Reply With Quote
Old 2009-06-06, 02:26   #15
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

B4016 Posts
Default

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
ATH is online now   Reply With Quote
Old 2009-06-06, 12:39   #16
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

584510 Posts
Default

Quote:
Originally Posted by ATH View Post
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).
rogue is offline   Reply With Quote
Old 2009-09-03, 05:29   #17
Shaopu Lin
 
Shaopu Lin's Avatar
 
Jul 2004

24·3 Posts
Default

Another gnfs implementation, called kmGNFS, is available from http://kmgnfs.cti.gr/kmGNFS/Home.html.
Shaopu Lin is offline   Reply With Quote
Old 2009-11-30, 17:54   #18
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,271 Posts
Default

Potentially a CUDA implementation of QS. I wonder if he was successful, and if he will make his implementation public.
bsquared is offline   Reply With Quote
Old 2010-03-16, 10:13   #19
msft
 
msft's Avatar
 
Jul 2009
Tokyo

61010 Posts
Default

To factor a Fermat number F_n = 2^(2^n)+1.
http://www.perfsci.com/free-software.asp#giantint
msft is offline   Reply With Quote
Old 2010-03-16, 18:46   #20
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2×3×13×61 Posts
Default

Quote:
Originally Posted by msft View Post
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
ET_ is offline   Reply With Quote
Old 2010-10-01, 11:24   #21
siew
 
Oct 2009

32·7 Posts
Default

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.
siew is offline   Reply With Quote
Old 2010-10-01, 12:38   #22
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

67078 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Links to Factoring Projects rogue Factoring 20 2014-11-19 01:08
Links to Factoring Programs rogue Factoring 32 2009-09-17 11:40
factoring programs henryzz Factoring 6 2007-09-19 13:47
looking for Fermat factoring programs ixfd64 Factoring 1 2005-09-08 12:13
any good GNFS factoring programs? ixfd64 Factoring 1 2004-04-27 09:41

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

Wed Aug 5 20:12:02 UTC 2020 up 19 days, 15:58, 2 users, load averages: 1.61, 1.63, 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.