[QUOTE=Shaopu Lin;175169]There is another ecm implementation which is available from [url]http://www.cs.toronto.edu/~cvs/dlog/[/url].[/QUOTE]

How fast is is - compared to GMP-ECM?

[quote=Andi47;175189]How fast is is - compared to GMP-ECM?[/quote]

[quote]It can be used to find factors as large as 100 bits in a matter of hours on a typical PC.[/quote]

Of what size of input number?

There is another quadratic sieve implementation which is called basicqs and available from [url]http://code.google.com/p/basicqs[/url].

Maybe add links to sieving and primality proving programs?

[U]Sieving:[/U]
NewPGen: [URL="http://primes.utm.edu/programs/NewPGen/"]http://primes.utm.edu/programs/NewPGen/[/URL] / [URL="http://jpenne.free.fr/NewPGen/"]http://jpenne.free.fr/NewPGen/[/URL] (twin primes, Sophie Germain, Cunningham Chain)
Multisieve: [URL="http://primes.utm.edu/bios/page.php?id=449"]http://primes.utm.edu/bios/page.php?id=449[/URL] / [URL="http://www.primzahlenarchiv.de/software/multisieve_gui.zip"]http://www.primzahlenarchiv.de/software/multisieve_gui.zip[/URL] (Cullens/Woodalls, Generalized/Hyper/Near Cullens/Woodalls, factorials, multifactorials, primodials and more)
Fermat: [URL="http://www.fermatsearch.org/Fermat_44_beta.zip"]http://www.fermatsearch.org/Fermat_44_beta.zip[/URL] (sieve for fermat factors F24 ~ F2000)
FermFact: [URL="http://www.fermatsearch.org/FermFact-09b.zip"]http://www.fermatsearch.org/FermFact-09b.zip[/URL] (sieve for fermat factors F2000 ~ F500000)
gcwsieve: [URL="http://primes.utm.edu/bios/page.php?id=1223"]http://primes.utm.edu/bios/page.php?id=1223[/URL] (Generalized Cullen/Woodall n*b[sup]n[/sup]+-1 )
srsieve: [URL="http://www.geocities.com/g_w_reynolds/srsieve/"]http://www.geocities.com/g_w_reynolds/srsieve/[/URL] (k*b^n+c with fixed b,multiple fixed k,c and variable n)
sr1sieve: [URL="http://www.geocities.com/g_w_reynolds/sr1sieve/"]http://www.geocities.com/g_w_reynolds/sr1sieve/[/URL] (specialised for sieving a single sequence k*b^n+/-1)
sr2sieve: [URL="http://www.geocities.com/g_w_reynolds/sr2sieve/"]http://www.geocities.com/g_w_reynolds/sr2sieve/[/URL] (a sieve for multiple sequences k*b^n+/-1 and b^n+/-k)
sr5sieve: [URL="http://www.geocities.com/g_w_reynolds/sr5sieve/"]http://www.geocities.com/g_w_reynolds/sr5sieve/[/URL] (sieve for the Sierpinski/Riesel Base 5 projects)
AP26: [URL="http://www.geocities.com/g_w_reynolds/AP26/"]http://www.geocities.com/g_w_reynolds/AP26/[/URL] (BOINC app for finding record length 26 arithmetic progression of primes)
APTreeSieve: [URL="http://primes.utm.edu/bios/page.php?id=809"]http://primes.utm.edu/bios/page.php?id=809[/URL] (arithmetic progressions k*b + a with arbitrary a, b)


[U]Primality Proving:[/U]
Primo: [URL="http://www.ellipsa.eu/public/misc/downloads.html"]http://www.ellipsa.eu/public/misc/downloads.html[/URL] (ECPP algorithm for general numbers, no special form)
Proth: [URL="http://primes.utm.edu/programs/gallot/"]http://primes.utm.edu/programs/gallot/[/URL] (k*2[sup]n[/sup]+1 2[sup]n[/sup] > k)
LLR: [URL="http://primes.utm.edu/bios/page.php?id=431"]http://primes.utm.edu/bios/page.php?id=431[/URL] (k*2[sup]n[/sup]+/-1 2[sup]n[/sup] > k)
OpenPFGW (PrimeForm): [URL="http://primes.utm.edu/bios/page.php?lastname=PrimeForm"]http://primes.utm.edu/bios/page.php?lastname=PrimeForm[/URL] / [URL="http://www.fermatsearch.org/pfgw_ver_12_win32_pfgw_winpfgw.zip"]http://www.fermatsearch.org/pfgw_ver_12_win32_pfgw_winpfgw.zip[/URL] (probable prime tests of arbitrary expressions)
GeneFer: [URL="http://galloty.chez.com/primes/pgm/"]http://galloty.chez.com/primes/pgm/[/URL] (large probable generalized Fermat primes)

[QUOTE=ATH;176155]Maybe add links to sieving and primality proving programs?

[U]Sieving:[/U]
NewPGen: [URL="http://primes.utm.edu/programs/NewPGen/"]http://primes.utm.edu/programs/NewPGen/[/URL] / [URL="http://jpenne.free.fr/NewPGen/"]http://jpenne.free.fr/NewPGen/[/URL] (twin primes, Sophie Germain, Cunningham Chain)
Multisieve: [URL="http://primes.utm.edu/bios/page.php?id=449"]http://primes.utm.edu/bios/page.php?id=449[/URL] / [URL="http://www.primzahlenarchiv.de/software/multisieve_gui.zip"]http://www.primzahlenarchiv.de/software/multisieve_gui.zip[/URL] (Cullens/Woodalls, Generalized/Hyper/Near Cullens/Woodalls, factorials, multifactorials, primodials and more)
Fermat: [URL="http://www.fermatsearch.org/Fermat_44_beta.zip"]http://www.fermatsearch.org/Fermat_44_beta.zip[/URL] (sieve for fermat factors F24 ~ F2000)
FermFact: [URL="http://www.fermatsearch.org/FermFact-09b.zip"]http://www.fermatsearch.org/FermFact-09b.zip[/URL] (sieve for fermat factors F2000 ~ F500000)
gcwsieve: [URL="http://primes.utm.edu/bios/page.php?id=1223"]http://primes.utm.edu/bios/page.php?id=1223[/URL] (Generalized Cullen/Woodall n*b[sup]n[/sup]+-1 )
srsieve: [URL="http://www.geocities.com/g_w_reynolds/srsieve/"]http://www.geocities.com/g_w_reynolds/srsieve/[/URL] (k*b^n+c with fixed b,multiple fixed k,c and variable n)
sr1sieve: [URL="http://www.geocities.com/g_w_reynolds/sr1sieve/"]http://www.geocities.com/g_w_reynolds/sr1sieve/[/URL] (specialised for sieving a single sequence k*b^n+/-1)
sr2sieve: [URL="http://www.geocities.com/g_w_reynolds/sr2sieve/"]http://www.geocities.com/g_w_reynolds/sr2sieve/[/URL] (a sieve for multiple sequences k*b^n+/-1 and b^n+/-k)
sr5sieve: [URL="http://www.geocities.com/g_w_reynolds/sr5sieve/"]http://www.geocities.com/g_w_reynolds/sr5sieve/[/URL] (sieve for the Sierpinski/Riesel Base 5 projects)
AP26: [URL="http://www.geocities.com/g_w_reynolds/AP26/"]http://www.geocities.com/g_w_reynolds/AP26/[/URL] (BOINC app for finding record length 26 arithmetic progression of primes)
APTreeSieve: [URL="http://primes.utm.edu/bios/page.php?id=809"]http://primes.utm.edu/bios/page.php?id=809[/URL] (arithmetic progressions k*b + a with arbitrary a, b)


[U]Primality Proving:[/U]
Primo: [URL="http://www.ellipsa.eu/public/misc/downloads.html"]http://www.ellipsa.eu/public/misc/downloads.html[/URL] (ECPP algorithm for general numbers, no special form)
Proth: [URL="http://primes.utm.edu/programs/gallot/"]http://primes.utm.edu/programs/gallot/[/URL] (k*2[sup]n[/sup]+1 2[sup]n[/sup] > k)
LLR: [URL="http://primes.utm.edu/bios/page.php?id=431"]http://primes.utm.edu/bios/page.php?id=431[/URL] (k*2[sup]n[/sup]+/-1 2[sup]n[/sup] > k)
OpenPFGW (PrimeForm): [URL="http://primes.utm.edu/bios/page.php?lastname=PrimeForm"]http://primes.utm.edu/bios/page.php?lastname=PrimeForm[/URL] / [URL="http://www.fermatsearch.org/pfgw_ver_12_win32_pfgw_winpfgw.zip"]http://www.fermatsearch.org/pfgw_ver_12_win32_pfgw_winpfgw.zip[/URL] (probable prime tests of arbitrary expressions)
GeneFer: [URL="http://galloty.chez.com/primes/pgm/"]http://galloty.chez.com/primes/pgm/[/URL] (large probable generalized Fermat primes)[/QUOTE]

Don't forget [URL="http://home.roadrunner.com/~mrodenkirch/"]phrot[/URL]. There will be a link to the latest PFGW in a week or so (and hopefully sooner).

Another gnfs implementation, called kmGNFS, is available from [url]http://kmgnfs.cti.gr/kmGNFS/Home.html[/url].

[URL=http://atlas-conferences.com/cgi-bin/abstract/cazn-03]Potentially a CUDA implementation of QS[/url]. I wonder if he was successful, and if he will make his implementation public.

To factor a Fermat number F_n = 2^(2^n)+1.
[URL="http://www.perfsci.com/free-software.asp#giantint"]http://www.perfsci.com/free-software.asp#giantint[/URL]

[QUOTE=msft;208521]To factor a Fermat number F_n = 2^(2^n)+1.
[URL="http://www.perfsci.com/free-software.asp#giantint"]http://www.perfsci.com/free-software.asp#giantint[/URL][/QUOTE]

I used giantint library before stumbling on GMP. giantint is (was?) a full C library, and is slower than GMP implementation.

Luigi

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.

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.