From 95801c6f95a78e8e4aeb702733c283dee82a3841 Mon Sep 17 00:00:00 2001
From: Christoph Fuerst <ch.fuerst@gmx.at>
Date: Mon, 27 Mar 2017 19:50:56 +0200
Subject: [PATCH] Implemented Tonellis Algorithm

---
 src/primefactors.cpp | 61 +++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 60 insertions(+), 1 deletion(-)

diff --git a/src/primefactors.cpp b/src/primefactors.cpp
index 45a1498..d4ad778 100644
--- a/src/primefactors.cpp
+++ b/src/primefactors.cpp
@@ -100,6 +100,58 @@ void factor_int2(mpz_class N)
 	cout << "Found prime-factors: " << (a-b)/2 << " and " << ((a+b-2)/2) << endl;
 }
 
+int xGCD(long a, long b, long &x, long &y) {
+    if(b == 0) {
+       x = 1;
+       y = 0;
+       return a;
+    }
+
+    long x1, y1, gcd = xGCD(b, a % b, x1, y1);
+    x = y1;
+    y = x1 - (a / b) * y1;
+    return gcd;
+}
+
+void tonelli(long a, long g, long p)
+{
+	long locpm1 = p-1;
+	long s=0, t=0;
+	long tmp, gi;
+	long u,v;
+
+	while((locpm1 % 2) == 0)
+	{
+		s++;
+		locpm1 /= 2;
+	}
+	t = locpm1;
+
+	cout << "Express p-1 = " << p-1 << " as 2^" << s << "*" << t << endl;
+	unsigned long* e = new unsigned long[s];
+
+	e[0] = 0;
+    xGCD(g,p,u,v);
+    gi = fmod(u,p)+p;
+    cout << "So far we got: t=" << t << " and s=" << 2 << " and gi=" << gi << endl;
+    for(long i=1;i<s;i++)
+    {
+       tmp = a*pow(gi,e[i-1]);
+       cout << "tmp: " << tmp << endl;
+       tmp = pow(tmp,(p-1)/pow(2,i+1));
+       cout << "tmp: " << tmp << endl;
+       if(fmod(tmp,p) != 1)
+    	   e[i] = pow(2,i)+e[i-1];
+       else
+    	   e[i] = e[i-1];
+    }
+    cout << "we got e:" << e[0] << " and " << e[1] << endl;
+    tmp = fmod(a*pow(gi,e[s-1]), p);
+    cout << "tmp: " << tmp << endl;
+    tmp = fmod(g*pow(tmp,(t+1)/2),p);
+    cout << "tmp: " << tmp << endl;
+}
+
 int main(int argc, char** argv)
 {
    if(argc == 1)
@@ -111,9 +163,10 @@ int main(int argc, char** argv)
 		   cout << "What do you want to do..." << endl;
 		   cout << "Algorithm A: Trial division" << endl;
 		   cout << "Algorithm C: Fermat like factorization" << endl;
+		   cout << "Algorithm D: Tonelli's Algorithm" << endl;
            cin >> input;
            cout << endl;
-	   }while((input != 'A') && (input != 'C') );
+	   }while((input != 'A') && (input != 'C') && (input != 'D') );
 
 	   switch(input)
 	   {
@@ -167,6 +220,12 @@ int main(int argc, char** argv)
 	   		   factor_int2(N);
 	   		   break;
 	   	   }
+	   	   case 'D':
+	   	   {
+	   		   cout << "Algorithm of Tonelli" << endl;
+	   		   tonelli(10,2,13);
+	   		   break;
+	   	   }
 	   	   default:
 	   		   break;
 	   }
-- 
2.1.4