import java.math.*;
import java.util.Scanner;
import java.util.ArrayList;
import java.io.PrintWriter;
import java.io.File;
import java.io.FileNotFoundException;



public class Cryptology_task1 {


	//Calculate BigInteger square root for number x
	public static BigInteger squareRoot(BigInteger x) {
	      BigInteger right = x, left = BigInteger.ZERO, mid;
	      while(right.subtract(left).compareTo(BigInteger.ONE) > 0) {
	            mid = (right.add(left)).shiftRight(1);
	            if(mid.multiply(mid).compareTo(x) > 0)
	                  right = mid;
	            else
	                  left = mid;
	      }
	      return left;
	}


	// Factorize number version ArrayList 02
	// Will return a matrix containing the primefactors (<B) and powers for a number n
	public static BigInteger[][] smallFactor(ArrayList<BigInteger> A, BigInteger n){
		ArrayList<ArrayList<BigInteger>> Xlist = new ArrayList<ArrayList<BigInteger>>(); //Vector of all primes in A, and their power

		BigInteger top = squareRoot(n);    //Upper limit for search
		int index = 0;

		while (A.get(index).compareTo(top) <= 0){	//While the current prime is smaller than sqrt(n)
			if (n.mod(A.get(index)).compareTo(BigInteger.valueOf(0)) == 0){    //If A(index) divides n

				ArrayList<BigInteger> temp = new ArrayList<BigInteger>();      //Create a row in Xlist containing the prime A(index)
				temp.add(A.get(index));
				temp.add(BigInteger.valueOf(1));
				Xlist.add(temp);

				BigInteger exponent = Xlist.get(index).get(1).add(BigInteger.valueOf(1));  //Define the next exponent
				while(n.mod(Xlist.get(index).get(0).pow(exponent.intValue())).compareTo(BigInteger.ZERO) == 0){ //If A^ext also divides n
			       	Xlist.get(index).set(1, exponent);                          //increase the power
			        exponent = exponent.add(BigInteger.valueOf(1));

				}

			    n = n.divide(Xlist.get(index).get(0).pow(Xlist.get(index).get(1).intValue()));  //Divide n by prime and it's power
		        if(n.compareTo(BigInteger.ONE) == 0){           // Break if all factors have been found
		            break;
		        }

			}
			else{  // If not divisor, set this row to 0
				ArrayList<BigInteger> temp = new ArrayList<BigInteger>();
				temp.add(BigInteger.valueOf(1)); // recent change
				temp.add(BigInteger.valueOf(0));
				Xlist.add(temp);
			}
		    index++;

		    if (index >= A.size()){ // If i is out of bounds, terminate
		        break;
			}
		}

		// If remainder exists, place it last
		if (n.compareTo(BigInteger.valueOf(1)) == 1){
			ArrayList<BigInteger> temp = new ArrayList<BigInteger>();
		    temp.add(n);
		    temp.add(BigInteger.valueOf(1));
		    Xlist.add(temp);
		}

		// Transform to matrix
		BigInteger[][] X = new BigInteger[Xlist.size()][2];
		for(int k = 0; k < Xlist.size(); k++){
			X[k][0] = Xlist.get(k).get(0);
			X[k][1] = Xlist.get(k).get(1);
		}

		return X;
	}

	//-------------------------------------------------------------------------------------------------------------
	//-------------------------------------------------------------------------------------------------------------
	public static void main(String[] args) {

		long startTime = System.nanoTime();  //Measure elapsed time for the program

		// Read primes from file ----------------------------------------------------------------------------------
		Scanner scan = null;
		try {
			scan = new Scanner(new File("prim_2_24.txt"));
		} catch(FileNotFoundException e){
			System.err.println("The file prim_2_24.txt could not be opened");
			System.exit(1);
		}

		ArrayList<BigInteger> lowPrimes = new ArrayList<BigInteger>();

		while(scan.hasNext()){
			lowPrimes.add(scan.nextBigInteger());
		}

		scan.close();



		// Quadratic sieve ----------------------------------------------------------------------------------------
		// Generate suitable candidates

		// Essential parameters
		// the number to factorize
		//BigInteger N = new BigInteger("323");      // for 323, B = 15 and L = 5 works fine
 		//BigInteger N = new BigInteger("307561");     // for 307561, B = 50 and L = 20 works fine
		//BigInteger N = new BigInteger("31741649");     // for 31741649, B = 50 and L = 20 works fine as well
		//BigInteger N = new BigInteger("3205837387");     // for 3205837387, B = 80 and L = 25 works fine
		//BigInteger N = new BigInteger("392742364277");     // for 392742364277, not working yet
		BigInteger N = new BigInteger("165895369126610396357353");     // for 165895369126610396357353, B =  and L =  works fine

		// original way to set parameters
		//BigInteger B = new BigInteger("1024");   // Smoothness parameter
		//int L = 100;                              // Not really L, but rather L - |F|, i.e the difference between the two
		//Boolean readSolution = true;			 // Do you want to calculate solution too?

			//Initialize
			//ArrayList<BigInteger> F = new ArrayList<BigInteger>();  //Factorbase

			//BigInteger tempPrime = lowPrimes.get(0);
			//int i = 0;
			//while(tempPrime.compareTo(B) <= 0){
				//F.add(tempPrime);
				//i++;
				//tempPrime = lowPrimes.get(i);
			//}


		// alternative way to set parameters
		BigInteger B = new BigInteger("1024");
		//BigInteger B = new BigInteger("128");
		int L = 10; // Not really L, but rather L - |F|, i.e the difference between the two
		Boolean readSolution = true;

		ArrayList<BigInteger> F = new ArrayList<BigInteger>();  //Factorbase

		BigInteger tempPrime = lowPrimes.get(0);
		int i = 0;
		while(i <= B.intValue()){
			F.add(tempPrime);
			i++;
			tempPrime = lowPrimes.get(i);
		}



		int width = F.size();
		int rlim = width + L;
		BigInteger [][] r = new BigInteger [rlim][2];
		int [][] M = new int [rlim][width];

		// Initiate r & M, by setting to 0
		for (int k = 0; k < rlim; k++){
			r[k][0] = BigInteger.valueOf(0);
			r[k][0] = BigInteger.valueOf(0);
			for (int j = 0; j < width; j++){
				M[k][j] = 0;
			}
		}

		i = 0;  // Will now be used as index for found rows
		Boolean flag = false;  // Break condition

		// Diagnostics data
		long test1 = 0;
		long test2 = 0;

		for (int k = 0; k < B.multiply(BigInteger.valueOf(2)).intValue(); k++){ //Might tweak the limit later

			if (flag){ // Exit loop if all the numbers have been generated
				break;
			}

			for (int j = 0; j < k; j++){ //My preferred way to implement it

				BigInteger rtemp = squareRoot(N.multiply(BigInteger.valueOf(k))).add(BigInteger.valueOf(j));  //generate candidate r
				BigInteger ytemp = rtemp.pow(2).mod(N);          // y = r^2 mod N

		        if(ytemp.compareTo(BigInteger.ONE) > 0){  // if ytemp > 1

		            BigInteger[][] Y = smallFactor(F,ytemp);  // Factorize ytemp

		            int len = Y.length;

		            test1++;

		            // test whether Y is implemented correctly
		            BigInteger testY = BigInteger.valueOf(1);

		            for(int a = 0; a < len; a++){
		            	if(Y[a][0].compareTo(BigInteger.ZERO) != 0){
		            		testY = testY.multiply(Y[a][0].pow(Y[a][1].intValue()));
		            	}

		            }

		            if(testY.compareTo(ytemp) == 0){
		            	test2++;
		            }


		            if(Y[len-1][0].compareTo(F.get(F.size() - 1)) <= 0){ // If no bigger prime factor is involved

		            	// Calculate new row
		            	int [] Mtemp = new int[width];
		            	//for(int a = 0; a < len; a++){
		            	for(int a = 0; a < width; a++){
		            		if(a < len){
		            			Mtemp[a] = Y[a][1].mod(BigInteger.valueOf(2)).intValue();// Place even and odd factors in row i of M
		            		}else{
		            			Mtemp[a] = 0;
		            		}

	                	}

		            	Boolean doub = true;
		            	int sumrows = 0;

		            	// Check for duplicate rows
		            	for(int t = 0; t < i; t++){ //
		            		sumrows = 0;
		            		for(int a = 0; a < width; a++){
		            			if(M[t][a] - Mtemp[a] != 0){  // If any element in row differs, they are not identical
		            				break;
		            			}
		            			else{
		            				sumrows++;
		            			}
		            		}
		            		if(sumrows == width){  // If all elements in a row are equal, there exists a duplicate, and Mtemp is discarded
		            			doub = false;
		            			break;
		            		}
		            	}


		                if (doub){ // If no duplicates, add to vector and matrix


		                    r[i][0] = rtemp;
		                	r[i][1] = ytemp;

		                	for(int a = 0; a < width; a++){
		                		M[i][a] = Mtemp[a];
		                	}



		                    i++;

		                    if (i > M.length - 1){  //If we have found all elements we need
		                        flag = true;
		                        break;
		            		}
		            	}
		            }
		        }
		    }
		}

		/*
		// Print the result
		System.out.println("The generated vector r and y, as well as the matrix M: ");
		for(int k = 0; k < rlim; k++){
			System.out.printf("%4d...%4d...%4d...", k, r[k][0], r[k][1]);
			for(int j = 0; j < width; j++){
				System.out.printf("%4d...", M[k][j]);
			}
			System.out.println();
		}*/

		//Print test results
		System.out.println("Test1: " + test1 + ", Test2 = " + test2);





		// Save result to .txt file
		PrintWriter NumberOut = null;

		try{
			NumberOut = new PrintWriter(new File("matrices.txt"));
		} catch (FileNotFoundException e){
			System.err.println("The file matrices.txt could not be opened");
			System.exit(1);
		}

		NumberOut.printf("%5d %5d%n", rlim, width);  // M N

		for(int k = 0; k < rlim; k++){
			for(int j = 0; j < width; j++){
				NumberOut.printf("%1d ", M[k][j]);
			}
			NumberOut.println();
		}


		NumberOut.close();

		long stopTime = System.nanoTime();
		long elapsedTime = (stopTime-startTime)/1000000; // Measure elapsed time in milliseconds
		System.out.println("Time to generate Matrix in milliseconds: " + elapsedTime);



		//----------------------------------------------------------------------------------------------------------------------
		// Down here we read solution from the GaussBin.exe run manually
		// Run with command: start "" "GaussBin.exe" matrices.txt matricesOut.txt (Note for self)

		if(readSolution){  // If we have solutions from GaussBin.exe

			startTime = System.nanoTime();  // Measure time for calculating the solution

			// open file
			scan = null;
			try {
				scan = new Scanner(new File("matricesOut.txt"));
			} catch(FileNotFoundException e){
				System.err.println("The file matricesOut.txt could not be opened");
				System.exit(1);
			}

			BigInteger nSol = new BigInteger(scan.nextLine()); //Number of solutions
			ArrayList<ArrayList<BigInteger>> solution = new ArrayList<ArrayList<BigInteger>>();
			Scanner scanRow = null;


			// Read the matrix from the file
			while(scan.hasNextLine()){
				String row = scan.nextLine();
				scanRow = new Scanner(row);
				ArrayList<BigInteger> temp = new ArrayList<BigInteger>();
				while(scanRow.hasNext()){
					BigInteger tempElement = new BigInteger(scanRow.next());
					temp.add(tempElement);

				}
				solution.add(temp);
				scanRow.close();
			}
			scan.close();

			// Convert the solutions to a matrix
			BigInteger[][] Solutions = new BigInteger[solution.size()][solution.get(0).size()];
			for(int k = 0; k < nSol.intValue(); k++){
				for(int j = 0; j < rlim; j++){
					Solutions[k][j] = solution.get(k).get(j);
				}
			}


			// Use the Solutions to factorize the number N ------------------------------------------------------
			i = 0;  //now number for current solution


			// Diagnostics data
			long passTest0 = 0;
			long passTest1 = 0;
			long passTest2 = 0;


			Boolean Success = false;
			BigInteger factor1 = null;
			BigInteger factor2 = null;

			while(!Success && i < nSol.intValue()){  // Until we find a solution or run out of possible solutions
				BigInteger productX = new BigInteger("1");  // One of the primefactors
				BigInteger productY = new BigInteger("1");  // Another of the primefactors


				/*
				// very basic test
				for(int j = 0; j < rlim; j++){
					if(Solutions[i][j].compareTo(BigInteger.ONE)== 0){  // if number is 1, we multiply with the row

						productX = productX.multiply(r[j][0]);			//multiply with r
						productY = productY.multiply(r[j][1]);			//multiply with y


						// modulo N
						productX = productX.mod(N);
						productY = productY.mod(N);

					}
				}*/



				BigInteger[][] factorY = new BigInteger[width][2];
				for(int k = 0; k < width; k++){
					factorY[k][0] = BigInteger.valueOf(1);
					factorY[k][1] = BigInteger.valueOf(0);
				}


				for(int j = 0; j < rlim; j++){
					if(Solutions[i][j].compareTo(BigInteger.ONE)== 0){  // if number is 1, we multiply with the row

						productX = productX.multiply(r[j][0]);						//multiply with r
						productY = productY.multiply(r[j][1]);						//multiply with y

						// lets try another way for productY
						BigInteger[][]Y = smallFactor(F,r[j][1]);
						BigInteger littleProd = BigInteger.valueOf(1);

						for(int k = 0; k < Y.length; k++){
							littleProd = littleProd.multiply(Y[k][0].pow(Y[k][1].intValue()));

							//if(littleProd.compareTo(r[j][1]) == 0){
								//passTest2++;
							//}


							//productY = productY.multiply(littleProd);  // kept as a reference

							if(factorY[k][0].compareTo(BigInteger.ONE) == 0){
								factorY[k][0] = Y[k][0];
							}
							factorY[k][1] = factorY[k][1].add(Y[k][1]);
						}

						// modulo N
						productX = productX.mod(N);
						productY = productY.mod(N);
						//passTest0++;
					}

				}


				// Now we try to construct productY from the factors
				BigInteger newproductY = BigInteger.valueOf(1);
				BigInteger bigProductY = BigInteger.valueOf(1);
				for(int k = 0; k < width; k++){

					// first I want to test it;


					bigProductY = bigProductY.multiply(factorY[k][0].pow(factorY[k][1].intValue()));
					bigProductY = bigProductY.mod(N);


					if(factorY[k][1].mod(BigInteger.valueOf(2)).compareTo(BigInteger.ZERO) == 0){
						factorY[k][1] = factorY[k][1].divide(BigInteger.valueOf(2));
					}else{
						System.out.println("Error, not divisible by 2");
					}

					if(factorY[k][0].compareTo(BigInteger.ZERO) != 0){
						newproductY = newproductY.multiply(factorY[k][0].pow(factorY[k][1].intValue()));
						newproductY = newproductY.mod(N);
					}

				}

				/*
				// check if they are equal
				if(((newproductY.pow(2)).mod(N)).compareTo(productY) == 0){
	//				System.out.println("Molto bene");
				}*/

				// modulo N
				//productX = productX.mod(N);
				//productY = productY.mod(N);



				i++;
				// Check N, it seems to change
				//if((productX.pow(2)).mod(N).compareTo((productY.pow(2)).mod(N)) == 0){ // see if X^2 mod n = Y^2 mod n
				if((productX.pow(2)).mod(N).compareTo((productY).mod(N)) == 0){ // see if X^2 mod n = Y^2 mod n
				//if((productX.pow(2)).mod(N).compareTo((newproductY.pow(2)).mod(N)) == 0){ // see if X^2 mod n = Y^2 mod n

					//BigInteger sqrtY = squareRoot(productY);

					//if(((sqrtY.pow(2)).mod(N)).compareTo(productY) == 0){
					//if((bigProductY.mod(N)).compareTo(productY) == 0){
					if(((newproductY.pow(2)).mod(N).compareTo(bigProductY.mod(N)) == 0) && bigProductY.mod(N).compareTo(productY) == 0){
						passTest2++;
					}

					passTest1++;
					//passTest2++;

					//factor1 = productX.subtract(productY).abs();
					factor1 = productX.subtract(newproductY).abs();

					//factor1 = productX.
					factor1 = factor1.gcd(N);
					if((factor1.compareTo(BigInteger.ONE) != 0) && (factor1.compareTo(N) != 0)){  // If factor 1 is not 1 or N
						factor2 = N.divide(factor1);   // We have found both factors
						Success = true;

						// Print solutions
						System.out.print(factor1);
						System.out.print(" ");
						System.out.println(factor2);
					}

				}

			}

			System.out.println("Pass test 0: " + passTest0 + " Pass test 1: " + passTest1 + " Pass test 2: " + passTest2);

			stopTime = System.nanoTime();
			elapsedTime = (stopTime-startTime)/1000000; // Measure elapsed time in milliseconds

			System.out.println("Time to generate primefactors in milliseconds: " + elapsedTime);

		}
	}
}