From d653147e5e1804577b0645f3c2a14d2e793ecd4b Mon Sep 17 00:00:00 2001
From: Christoph Fuerst <ch.fuerst@gmx.at>
Date: Mon, 3 Apr 2017 21:01:40 +0200
Subject: [PATCH] Divided sources into several files

---
 src/cryptoalgorithms.h |  27 ++++++++
 src/discrete_log.cpp   |  63 +++++++++++++++++
 src/factor_int.cpp     |  63 +++++++++++++++++
 src/factor_int2.cpp    |  39 +++++++++++
 src/primefactors.cpp   | 178 +------------------------------------------------
 src/tonelli.cpp        |  52 +++++++++++++++
 src/xGCD.cpp           |  26 ++++++++
 7 files changed, 272 insertions(+), 176 deletions(-)
 create mode 100644 src/cryptoalgorithms.h
 create mode 100644 src/discrete_log.cpp
 create mode 100644 src/factor_int.cpp
 create mode 100644 src/factor_int2.cpp
 create mode 100644 src/tonelli.cpp
 create mode 100644 src/xGCD.cpp

diff --git a/src/cryptoalgorithms.h b/src/cryptoalgorithms.h
new file mode 100644
index 0000000..86c82cc
--- /dev/null
+++ b/src/cryptoalgorithms.h
@@ -0,0 +1,27 @@
+/*
+ * cryptoalgorithms.h
+ *
+ *  Created on: 03.04.2017
+ *      Author: christoph
+ */
+
+#include <iostream>
+#include <cmath>
+#include <gmpxx.h>
+
+#ifndef CRYPTOALGORITHMS_H_
+#define CRYPTOALGORITHMS_H_
+
+void factor_int(mpz_class N, mpz_class* d, unsigned long& nooffactors, mpz_class *factors);
+
+void factor_int2(mpz_class N);
+
+int xGCD(long a, long b, long &x, long &y);
+
+void tonelli(long a, long g, long p);
+
+void discrete_log(long p, long g, long a);
+
+
+
+#endif /* CRYPTOALGORITHMS_H_ */
diff --git a/src/discrete_log.cpp b/src/discrete_log.cpp
new file mode 100644
index 0000000..9421ba8
--- /dev/null
+++ b/src/discrete_log.cpp
@@ -0,0 +1,63 @@
+/*
+ * discrete_log.cpp
+ *
+ *  Created on: 03.04.2017
+ *      Author: christoph
+ */
+
+#include <iostream>
+#include <cmath>
+#include "cryptoalgorithms.h"
+
+using namespace std;
+
+void discrete_log(long p, long g, long a)
+{
+   long m = -floor(-sqrt(p-1));
+   cout << "So far we got: m=" << m << endl;
+   long *A = new long[m];
+   long *b = new long[m];
+
+   A[0] = 1;
+   b[0] = a;
+
+   for(int i=1;i<m;i++)
+   {
+       A[i] = fmod(g*A[i-1],p);
+   }
+
+   cout << "So far we got: " << endl;
+   for(int i=0;i<m;i++)
+   {
+	  cout << "A[" << i << "] = " << A[i] << "; ";
+   }
+   cout << endl;
+
+   long gi, s;
+   xGCD(g,p,gi,s);
+   gi = gi%p;
+   cout << "We got: gi=" << gi << endl;
+
+   long gim = 1;
+
+   for(int i=0;i<m;i++)
+	   gim = ((gim * gi) %p);
+   cout << "We got: gim=" << gim << endl;
+
+   for(int i=0;i<m;i++)
+   {
+	   for(int j=0;j<m;j++)
+	   {
+		  if(A[j] == b[i])
+		  {
+              cout << "We got: i=" << i << " and j=" << j << endl;
+              cout << "This gives the discrete logarithm: " << i*m + j << endl;
+		  }
+	   }
+	   b[i+1] = b[i]*gim % p;
+   }
+
+
+}
+
+
diff --git a/src/factor_int.cpp b/src/factor_int.cpp
new file mode 100644
index 0000000..cfdd70d
--- /dev/null
+++ b/src/factor_int.cpp
@@ -0,0 +1,63 @@
+/*
+ * factor_int.cpp
+ *
+ *  Created on: 03.04.2017
+ *      Author: christoph
+ */
+
+#include <iostream>
+#include <cmath>
+#include <gmpxx.h>
+#include "cryptoalgorithms.h"
+
+using namespace std;
+
+/* Algorithm A from Knuth's Art of Computer Programm 2: Seminumerical Algorithms */
+/* page 380 */
+void factor_int(mpz_class N, mpz_class* d, unsigned long& nooffactors, mpz_class *factors)
+{
+	/* Step A1: initialize t = 0, k = 0, n = N */
+	unsigned long t=0;
+	unsigned long k=0;
+	mpz_class n = N;
+
+    mpz_class* p  = new mpz_class[n.get_ui()];
+
+	mpz_class q, r;
+
+	/* Step A2: n=1? */
+    while(n != 1)
+    {
+	    /* Step A3: q = floor(n/dk), r = n mod dk */
+		q = n/d[k];
+		r = n%d[k];
+
+		/* Step A4: r != 0 */
+		if(r != 0)
+		{
+			/* Step A6: Low quotient */
+			if(q > d[k])
+			{
+				k++;
+			}
+			else
+			{
+				p[t] = n;
+				n = 1;
+			}
+		}
+		else
+		{
+			/* Step A5: Factor found */
+			p[t] = d[k];
+			t++;
+			n = q;
+		}
+	}
+
+    for(size_t i=0;i<=t;i++)
+    	factors[i] = p[i];
+    nooffactors = t;
+
+}
+
diff --git a/src/factor_int2.cpp b/src/factor_int2.cpp
new file mode 100644
index 0000000..04ebef9
--- /dev/null
+++ b/src/factor_int2.cpp
@@ -0,0 +1,39 @@
+/*
+ * factor_int2.cpp
+ *
+ *  Created on: 03.04.2017
+ *      Author: christoph
+ */
+
+#include <iostream>
+#include <cmath>
+#include <gmpxx.h>
+#include "cryptoalgorithms.h"
+
+using namespace std;
+
+/* 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;
+}
+
+
diff --git a/src/primefactors.cpp b/src/primefactors.cpp
index b1a3306..d44616d 100644
--- a/src/primefactors.cpp
+++ b/src/primefactors.cpp
@@ -21,186 +21,12 @@ Finished building target: PrimeFactors
  */
 
 #include <iostream>
-#include <vector>
 #include <cmath>
 #include <gmpxx.h>
 
-using namespace std;
-
-/* Algorithm A from Knuth's Art of Computer Programm 2: Seminumerical Algorithms */
-/* page 380 */
-void factor_int(mpz_class N, mpz_class* d, unsigned long& nooffactors, mpz_class *factors)
-{
-	/* Step A1: initialize t = 0, k = 0, n = N */
-	unsigned long t=0;
-	unsigned long k=0;
-	mpz_class n = N;
-
-    mpz_class* p  = new mpz_class[n.get_ui()];
-
-	mpz_class q, r;
-
-	/* Step A2: n=1? */
-    while(n != 1)
-    {
-	    /* Step A3: q = floor(n/dk), r = n mod dk */
-		q = n/d[k];
-		r = n%d[k];
-
-		/* Step A4: r != 0 */
-		if(r != 0)
-		{
-			/* Step A6: Low quotient */
-			if(q > d[k])
-			{
-				k++;
-			}
-			else
-			{
-				p[t] = n;
-				n = 1;
-			}
-		}
-		else
-		{
-			/* Step A5: Factor found */
-			p[t] = d[k];
-			t++;
-			n = q;
-		}
-	}
-
-    for(size_t i=0;i<=t;i++)
-    	factors[i] = p[i];
-    nooffactors = t;
-
-}
-
-/* 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 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 << "Computed Solution: " << tmp << endl;
-}
-
-void discrete_log(long p, long g, long a)
-{
-   long m = -floor(-sqrt(p-1));
-   cout << "So far we got: m=" << m << endl;
-   long *A = new long[m];
-   long *b = new long[m];
-
-   A[0] = 1;
-   b[0] = a;
-
-   for(int i=1;i<m;i++)
-   {
-       A[i] = fmod(g*A[i-1],p);
-   }
-
-   cout << "So far we got: " << endl;
-   for(int i=0;i<m;i++)
-   {
-	  cout << "A[" << i << "] = " << A[i] << "; ";
-   }
-   cout << endl;
-
-   long gi, s;
-   xGCD(g,p,gi,s);
-   gi = gi%p;
-   cout << "We got: gi=" << gi << endl;
-
-   long gim = 1;
-
-   for(int i=0;i<m;i++)
-	   gim = ((gim * gi) %p);
-   cout << "We got: gim=" << gim << endl;
-
-   for(int i=0;i<m;i++)
-   {
-	   for(int j=0;j<m;j++)
-	   {
-		  if(A[j] == b[i])
-		  {
-              cout << "We got: i=" << i << " and j=" << j << endl;
-              cout << "This gives the discrete logarithm: " << i*m + j << endl;
-		  }
-	   }
-	   b[i+1] = b[i]*gim % p;
-   }
-
-
-}
+#include "cryptoalgorithms.h"
 
+using namespace std;
 
 int main(int argc, char** argv)
 {
diff --git a/src/tonelli.cpp b/src/tonelli.cpp
new file mode 100644
index 0000000..6d746bb
--- /dev/null
+++ b/src/tonelli.cpp
@@ -0,0 +1,52 @@
+/*
+ * tonelli.cpp
+ *
+ *  Created on: 03.04.2017
+ *      Author: christoph
+ */
+
+#include <iostream>
+#include <cmath>
+#include "cryptoalgorithms.h"
+
+using namespace std;
+
+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;
+	long* e = new long[s];
+
+	e[0] = 0;
+    xGCD(g,p,u,v);
+    gi = u%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((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 << "Computed Solution: " << tmp << endl;
+}
+
diff --git a/src/xGCD.cpp b/src/xGCD.cpp
new file mode 100644
index 0000000..afcc38c
--- /dev/null
+++ b/src/xGCD.cpp
@@ -0,0 +1,26 @@
+/*
+ * xGCD.cpp
+ *
+ *  Created on: 03.04.2017
+ *      Author: christoph
+ */
+
+#include <iostream>
+#include <cmath>
+
+using namespace std;
+
+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;
+}
+
+
-- 
2.1.4