From 16dc0911f1b80cdbfee11c7efc4fe0fbe5f6f74d Mon Sep 17 00:00:00 2001 From: Christoph Fuerst Date: Sun, 26 Mar 2017 11:18:08 +0200 Subject: [PATCH] Added algorithm Fermat factorization --- src/primefactors.cpp | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+) diff --git a/src/primefactors.cpp b/src/primefactors.cpp index 20c77bd..7de4e33 100644 --- a/src/primefactors.cpp +++ b/src/primefactors.cpp @@ -76,6 +76,30 @@ void factor_int(mpz_class N, mpz_class* d, unsigned long& nooffactors, mpz_class } +/* Algorithm C from Knuth's Art of Computer Programm 2: Seminumerical Algorithms */ +/* Fermat like factorization */ +/* page 387 */ +void factor_int2(mpz_class N) +{ + unsigned long a = (unsigned long)(2*sqrt(N.get_ui())+1); + unsigned long b = 1; + signed long r = (signed long)((unsigned long)(sqrt(N.get_ui()))*(unsigned long)(sqrt(N.get_ui()))-N.get_ui()); + + while(r!=0) + { + r = r+a; + a = a+2; + + while(r > 0) + { + r = r-b; + b = b+2; + } + + } + cout << "Found prime-factors: " << (a-b)/2 << " and " << ((a+b-2)/2) << endl; +} + int main() { mpz_class N; @@ -113,6 +137,8 @@ int main() cout << factors[i] << " "; cout << endl; + factor_int2(N); + return (0); } -- 2.1.4