// Quadratic Sieve 
//
//	Overview: This object will attempt to factor a number using the
//		  quadratic sieve algorithm. If I have time I will
//		  implement the large prime variation.
//
//	Created on 5/9/1997 by Steve Beattie
//---------------------------------------------------------------------
//http://www.cse.ogi.edu/~beattie/QuadraticSieve/QuadSieve.java

import java.math.BigInteger;
import java.io.*;
import java.util.*;
import java.text.*;

public class QuadSieve {
	
	Date time1, time2, time3, time4, time5, time6;
	long total = 0;
	BigInteger number;		// the number to factor
	BigInteger num_sqrtf; 	// floor of the square root of the number
	int logRefine;
	DecimalFormat form = new DecimalFormat("0.000");

	QuadSieve(BigInteger numToFactor, int fBaseSize, int logRef) {

		time1 = new Date();
		//number = new BigInteger(numToFactor);
		number = numToFactor;
		System.out.println("Number to sieve is: " + number);
		num_sqrtf = sqrt_floor(number);
		logRefine = logRef;

		FactorBase factorBase = new FactorBase(number, num_sqrtf, fBaseSize);
		Sieve sieve = new Sieve(number, num_sqrtf, factorBase, logRef, true);

		time2 = new Date();
		total = time2.getTime() - time1.getTime();
		System.out.println("Init time: " + formatTime(total));

		factorBase.solveQC();
		time3 = new Date();
		total = time3.getTime() - time2.getTime();
		System.out.println("Solving QC: " + formatTime(total));

		sieve.sieving();
		time4 = new Date();
		total = time4.getTime() - time3.getTime();
		System.out.println("Sieve: " + formatTime(total));

		System.out.println("Creating and Reducing Matrix...");
		Matrix matrix = new Matrix(sieve.Records, factorBase.baseSize);
		matrix.GaussianElimination();
		time5 = new Date();
		total = time5.getTime() - time4.getTime();
		System.out.println("Matrix Manipulation: " + formatTime(total));

		System.out.println("Computing factor...");
		BigInteger result = sieve.compute(matrix);
		time6 = new Date();

		total = time6.getTime() - time5.getTime();
		System.out.println("Time to compute factor: " + formatTime(total));

		if (result.equals(BigInteger.valueOf(1)) ||
			result.equals(number)) {
			System.out.println("\nFactorization failed!!");
		} else {
			BigInteger otherFactor = number.divide(result);
			System.out.println("\nTwo factors of  " + number + " are: ");
			System.out.println("Sieved factor = " + result);
			System.out.println("Other factor  = " + otherFactor);
			System.out.print("Checking correctness... ");
			if (number.equals(result.multiply(otherFactor)))
				System.out.println("Answer is correct!!");
			else
				System.out.println("Something went wrong!!");
		}
		System.out.println();
		
	}

	public static void main(String argv[]){

		boolean done = false;
		BigInteger number;
		int factorBaseSize;
		int logRefinement;
		QuadSieve quadSieve;
		char ans;

		while (!done) {
			System.out.println("Please enter the number to factor:");
			number = getBigInteger();
			System.out.println("Please enter the size of the factor base:");
			factorBaseSize = getInt();
			System.out.println("Please enter the log refinement [-15,15]:");
			logRefinement = getInt();
			quadSieve = new QuadSieve(number, factorBaseSize, logRefinement);
			System.out.print("Try another factorization (y/n)?");
			ans = getChar();
			if ((ans != 'y') && (ans != 'Y'))
				done =true;
			System.out.println();
		}
	}

	public BigInteger sqrt_floor(BigInteger num) {
		// Assuming num is positive...
		// Algorithm taken from "C++ Math Class Library" by Scott N Gerard
		// Uses Newton-Rhapson algorithm to solve this

		int length = num.bitLength();
		int w = (length + 1)/2;
		BigInteger ri = new BigInteger(num.toString());
		BigInteger si = new BigInteger("0");
		BigInteger ti = si.setBit((2*w) - 2);

		BigInteger tmp;

		//System.out.println("Sqrt_floor: " + length + " " + w);
		//System.out.println("Sqrt_floor: " + ri + " " + si + " " + ti);

		for (int i = w; i > 0; i--){
			// tmp = ri - (si + ti)
			tmp = ri.subtract(si.add(ti));
			if (tmp.signum() < 0) {
				// yi = 0
				// ri = ri;
				// si = si/2
				si = si.shiftRight(1);
			} else {
				// yi = 1
				// ri = ri - (si + ti)
				// si = si/2 + ti
				ri = tmp;
				si = (si.shiftRight(1)).add(ti);
			}
			// ti = ti/4
			ti = ti.shiftRight(2);
		}
		return si;
	}

	private static BigInteger getBigInteger() {
		byte b[] = new byte[32000];
		byte c[];
		BigInteger h = BigInteger.valueOf(0);
		boolean done = false;
		while (!done)
			try {
				int nbytes = System.in.read(b ,0, 32000);
				c = new byte[nbytes - 1];
				for (int i = 0; i < (nbytes - 1); i++)
					c[i] = b[i];
				h = new BigInteger(new String(c));
				done = true;
			} catch (IOException e) {
			} catch (NumberFormatException e) {
				System.out.println("Invalid number! Please try again:");
				done = false;
			}
		return h;
	}	

	private static int getInt() {
		byte b[] = new byte[32];
		byte c[];
		int h = 0;
		boolean done = false;
		while (!done)
			try {
				int nbytes = System.in.read(b ,0, 32);
				c = new byte[nbytes - 1];
				for (int i = 0; i < (nbytes - 1); i++)
					c[i] = b[i];
				h = (Integer.valueOf(new String(c))).intValue();
				done = true;
			} catch (IOException e) {
			} catch (NumberFormatException e) {
				System.out.println("Invalid number! Please try again:");
				done = false;
			}
		return h;
	}	

	private static char getChar() {
		byte b[] = new byte[32];
		byte c[];
		char h = ' ';
		try {
			int nbytes = System.in.read(b ,0, 32);
			c = new byte[1];
			c[0] = b[0];
			h = (new String(c)).charAt(0);
		} catch (IOException e) {
		}
		return h;
	}

	private String formatTime(long time) {

		if (time < 60000) 
			return form.format(((double) time)/1000.0) + " seconds";
		else if (time < 3600000) 
			return form.format(((double) time)/60000.0) + " minutes";
		return form.format(((double) time)/3600000.0) + " hours";
		// No, I don't even want to contemplate days....
	}

}

class Sieve {
	// This class performs the actual sieving

	static int BLOCKSIZE = 50000;	// Size of blocks to sieve in
	//static int BLOCKSIZE = 50;	// Size of blocks to sieve in
	static BigInteger MAXBOUND = new BigInteger("10000000");	
									// Maximum bound of large primes
	static int EXTRA_ROWS = 10;		// How many more rows than columns
									// we should have.

	// Some nice constants to save a little time.
	static BigInteger ZERO = new BigInteger("0");
	static BigInteger ONE = new BigInteger("1");
	public static double log2 = Math.log(2);

	BigInteger number;		// Number to factor
	BigInteger num_sqrtf;	// Floor of the square root of number
	FactorBase fBase; 		// My factor base structure
	int logRefine;			// Log refinement factor
	boolean useLrgPrimes; 	// 

	int c;				// Approximate log of num_sqrtf
	BigInteger c1;		// Coefficient in Pomerance's polynomial
	BigInteger c2;		// Coefficient in Pomerance's polynomial
	BigInteger ufp;		// Unfactored portion
	BigInteger big_j;	// BigInteger version of (inv + j)

	int SumLogF[];		// logarithm array to sieve over. 
	int CloseEnuf;			// Fudge factor -- if the value in SunLogF
							// goes below this, then perform trial
							// division.
	int factorcount = 0;	// Keeps track of the number of numbers I've
							// tried to factor.
	int withFBcount = 0;	// Keeps track of the number of factors
							// using just the factor base
	int withLPcount = 0;	// Keeps track of the number of factors
							// using large primes.
	BigInteger bound;		// Bound of large primes.

	public Vector fRecords;	// Keeps track of numbers that factor
							// completely over the factor base
	public Vector Records;	// Keeps track of the factorizations of fRecords
	Hashtable lrgPrimes;	// Keeps track of large primes (need quick
							// lookup)
	int MaxExponents = 1;	// Keeps track of the maximum number of
							// entries that can be in a matrix row.


	Sieve(BigInteger n, BigInteger n_sqrtf, FactorBase factorbase, 
						int logRef, boolean useLrgPrimeMethod){

	// Class Constructor
		FBaseItem tmpRec;	//	Temp storage	

		number = n;
		num_sqrtf = n_sqrtf;
		fBase = factorbase;
		logRefine = logRef;
		useLrgPrimes = useLrgPrimeMethod;
		fRecords = new Vector(fBase.baseSize + EXTRA_ROWS);
		Records = new Vector(fBase.baseSize + EXTRA_ROWS);

		//c = 1 + (number.bitLength()/2);
		c = (number.bitLength()/2);
		// c1 = (floor(sqrt(n))^^2 - n
		c1 = (num_sqrtf.multiply(num_sqrtf)).subtract(number); 
		// c2 = floor(sqrt(n)) * 2
		c2 = num_sqrtf.shiftLeft(1);
		//
		// Pomerance's equation (2.2 in the paper factoring):
		// f(x) = (x + floor(sqrt(n))^^2 - n
		//      = x^^2 + 2x(floor(sqrt(n)) + (floor(sqrt(n)))^^2 - n
		//		= x^^2 + x(c2) + c1
		//		= x(x + c2) + c1
		//

		//System.out.println("Sieve: c = " + c + " c1 = " + c1 + " c2 = " + c2);

		BigInteger fbProduct = ONE; // Initialize the factor base product.
		for(int i = 1; fbProduct.compareTo(number) < 0; i++) {
			tmpRec = fBase.elementAt(i);
			fbProduct = fbProduct.multiply(tmpRec.bigPrime);
			MaxExponents++;
		}
		System.out.println("Maximum Number of Records in a Row: " + MaxExponents);

		if (useLrgPrimes) {
			lrgPrimes = new Hashtable(fBase.baseSize*2, (float) 0.75);
			double tmp = (double) (fBase.elementAt(fBase.baseSize - 1)).prime;
			tmp = Math.pow(tmp, 1.5); 
			bound = MAXBOUND.min(BigInteger.valueOf((long) tmp));
			System.out.println("Sieve: large prime bound is " + bound);
		}
	}


	public void sieving(){
		boolean positive = true;	// Direction we are heading in
		int k = 0;					// Number of blocks sieved
		long inv;					// Initial Value

		CloseEnuf = logRefine + (fBase.elementAt(fBase.baseSize - 1)).logp;

		PrintHeaders();

		while (fRecords.size() < (fBase.baseSize + EXTRA_ROWS)) {

			//System.out.println("Records: " + fRecords.size());
			
			inv = k * BLOCKSIZE;
			InitSumLogF(k, inv);

			SieveBlock(positive, k, inv);

			TrialDivision(positive, inv);
			
			if (((k + 1) % 10 == 0) && !positive) {
				PrintProgress(k+1);
			}

			if (positive) {		// Set to negative
				positive = false;
			} else {		// increment block count and set to positive
				k++;
				positive = true;
			}

		}

		// Print summary of information
		PrintSummary(k);
	}

	private void PrintHeaders() {

		System.out.println();
		System.out.println("----- Sieving " + number + " -----");
		System.out.print  ("# Blocks \t");
		System.out.print  ("# Success\t");
		System.out.print  ("# Tries  \t");
		if (useLrgPrimes) {
			System.out.print  ("# withFB \t");
			System.out.print  ("# withLP \t");
		}
		System.out.println();
		System.out.print  ("-------- \t");
		System.out.print  ("---------\t");
		System.out.print  ("-------  \t");
		if (useLrgPrimes) {
			System.out.print  ("-------- \t");
			System.out.print  ("-------- \t");
		}
		System.out.println();
	}

	private void PrintProgress(int k) {
		
		System.out.print("  " + k + "\t\t  ");
		System.out.print(fRecords.size() + "\t\t  ");
		System.out.print(factorcount);
		if (useLrgPrimes) {
			System.out.print("\t\t  " + withFBcount);
			System.out.print("\t\t  " + withLPcount);
		}
		System.out.println();
	}

	private void PrintSummary(int k){

		PrintProgress(k);
		System.out.println();
		if (useLrgPrimes) {
			System.out.print("The original factor base size:    ");
			System.out.println(fBase.origSize);
			System.out.print("The end factor base size:         ");
			System.out.println(fBase.baseSize);
			System.out.print("The number of unused large primes:");
			System.out.println(lrgPrimes.size()); 
		}
	}


	private void InitSumLogF(int k, long inv) {

		if (k == 0) {
			SumLogF = new int[BLOCKSIZE + 1];
			for (int j = 1; j <= BLOCKSIZE; j++) {
				SumLogF[j] = c + (int) (Math.log((double) (j + inv)) / log2);
				//if (j % 97 == 0) System.out.println(j + "\t" + (SumLogF[j]-c));
			}
		} else {
			int amount = c + (int) (Math.log((double) inv) / log2);
			for (int j = 1; j <= BLOCKSIZE; j++) {
				SumLogF[j] = amount;
				//if (j % 97 == 0) System.out.println(j + "\t" + SumLogF[j]);
			}
		}
	}

	private void SieveBlock(boolean positive, int k, long inv) {
		int start = 1, i, j, j_1, j_2, pval_1, pval_2;
		FBaseItem tmp;

		tmp = fBase.elementAt(start);
		if (tmp.prime == 2) {
			if (positive) {
				for (j = (int) (2 - ((inv + 2 - tmp.a_1) % 2)); 
												j <= BLOCKSIZE; j += 2){
					SumLogF[j] -= tmp.logp;
					//System.out.println(j + "\t" + SumLogF[j]);
				}
			} else {
				for (j = (int) (2 - ((inv + 2 + tmp.a_1) % 2)); 
												j <= BLOCKSIZE; j += 2){
					SumLogF[j] -= tmp.logp;
					//System.out.println(j + "\t" + SumLogF[j]);
				}
			}
			start = 2; 
		}

		if (positive) {
			for (i = start; i < fBase.origSize; i++){
				tmp = fBase.elementAt(i);
				//System.out.println(i + "\t" + tmp.prime + "\t" + tmp.logp);
				for (j = (int) (tmp.prime - 
								  ((inv + tmp.prime - tmp.a_1) % tmp.prime)); 
										j <= BLOCKSIZE; j += tmp.prime) {
					SumLogF[j] -= tmp.logp;
				}
				for (j = (int) (tmp.prime - 
								  ((inv + tmp.prime - tmp.a_2) % tmp.prime)); 
										j <= BLOCKSIZE; j += tmp.prime) {
					SumLogF[j] -= tmp.logp;
				}
			}
		} else {	// negative
			for (i = start; i < fBase.origSize; i++){
				tmp = fBase.elementAt(i);
				//System.out.println(i + "\t" + tmp.prime + "\t" + tmp.logp);
				for (j = (int) (tmp.prime - ((inv + tmp.a_1) % tmp.prime)); 
										j <= BLOCKSIZE; j += tmp.prime) {
					SumLogF[j] -= tmp.logp;
				}
				for (j = (int) (tmp.prime - ((inv + tmp.a_2) % tmp.prime)); 
										j <= BLOCKSIZE; j += tmp.prime) {
					SumLogF[j] -= tmp.logp;
				}
			}
		}
	}
	
	private void TrialDivision(boolean positive, long inv){
		int i, k;
		int count;
		Vector record;
		FBaseItem tmp;
		BigInteger[] bigTmps;
		boolean done;

		for (int j = 1; j <= BLOCKSIZE; j++) {
				//System.out.println("Comparing " + j + ": " 
				//							+ SumLogF[j] +" to  " + CloseEnuf);
			if (SumLogF[j] <= CloseEnuf) {
				// big_j = BigInteger(inv + j)
				big_j = BigInteger.valueOf((long) inv + j);
				//record = new Vector(fBase.baseSize/20);
				record = new Vector(MaxExponents);
				//
				// Pomerance's equation (2.2 in the paper "Factoring"):
				// f(x) = (x + floor(sqrt(n))^^2 - n
				//      = x^^2 + 2x(floor(sqrt(n)) + (floor(sqrt(n)))^^2 - n
				//		= x^^2 + x(c2) + c1
				//		= x(x + c2) + c1
				//
				// c1 = (floor(sqrt(n))^^2 - n
				// c2 = floor(sqrt(n)) * 2
				//
				if (positive) {
					// ufp = c1 + (big_j * (big_j + c2))
					ufp = c1.add(big_j.multiply(big_j.add(c2)));
					// There is no factor of -1 in ufp
				} else {
					// ufp = c1 + (big_j * (big_j - c2))
					ufp = c1.add(big_j.multiply(big_j.subtract(c2)));
					// ufp is negative
					// record factor of -1 and change ufp to positive
					record.addElement(new FactorRecord(0, 1));
					ufp = ufp.negate();
				}
				//System.out.println("Found: " + ufp);
				//System.out.println("Working on: inv=" + inv + "\tj=" + j
				//					+ "\tc1=" + c1 + "\tc2=" + c2);

				// BaseTrialDivision

				for (i = 1;(i < fBase.baseSize) && (ufp.compareTo(ONE)>0);i++){
					done = false;
					tmp = fBase.elementAt(i);
					count = 0;
					while (!done) {
						//bigTmps = ufp.divideAndRemainder(tmp.bigPrime);
						//if ((bigTmps[1]).equals(ZERO)) {
						if (ZERO.equals(ufp.mod(tmp.bigPrime))) {
							count++;
							ufp = ufp.divide(tmp.bigPrime);
							//ufp = bigTmps[0];
							//System.out.print("bigTmps: " + bigTmps[1] + " ");
							//System.out.println("ufp: " + ufp + " ");
						} else {
							done = true;
						}
					}
					if (count != 0)
						record.addElement(new FactorRecord(i, count));
				}

				if (ufp.equals(ONE)) {
					// if inv+j divides over FB, add it to fRecords and
					// Records
					fRecords.addElement(big_j);
					Records.addElement(record);
					//System.out.println("TrialDivision: Found: " + big_j);
					withFBcount++;
				} else {
					if (useLrgPrimes && (ufp.compareTo(bound) <= 0)) {
						//System.out.println("Potential large prime: " + ufp);
						UseLrgPrime(ufp, big_j, record);
					}
				}
				// Whether we were successful or not, we tried to
				// factor a number over the factor base, so increment
				// our counter.
				factorcount++;
			}
		}
	}

	private void UseLrgPrime(BigInteger ufp, BigInteger inv_j, Vector record) {
		
		Integer ufp_int = new Integer(ufp.intValue());
		LrgPrimeRecord lrgp = (LrgPrimeRecord) lrgPrimes.get(ufp_int);
		if (lrgp == null) {
			// ufp is not in the table of large primes, so add
			//System.out.println("Adding to table: " + ufp);
			lrgp = new LrgPrimeRecord(ufp_int.intValue(), record, 1, inv_j);
			Object foo = lrgPrimes.put(ufp_int, lrgp);
			//if (foo != null) {
				//System.out.println("Sieve:Error putting large prime into table!");
			//}
		} else {

			// Add the record we're currently working on
			record.addElement(new FactorRecord(fBase.baseSize, 1));
			Records.addElement(record);
			fRecords.addElement(inv_j);

			lrgp.record.addElement(new FactorRecord(fBase.baseSize, 1));
			Records.addElement(lrgp.record);
			fRecords.addElement(lrgp.inv_j);

			// For debugging purposes...
			//lrgp.count++;
			//Object foo = lrgPrimes.put(ufp_int, lrgp);
			lrgPrimes.remove(ufp_int);

			// Add the prime to the factor base
			fBase.addLrgPrime(lrgp.prime);
			withLPcount += 2;
		}
	}
		
	public BigInteger compute(Matrix myMatrix) {
	// Compute tries to solve for factors using information from the
	// row-reduced matrix.

		int i = 0, k;
		boolean found = false;
		BigInteger result = ONE;
		BigInteger x, y, z;
		BigInteger temp;
		FactorRecord tmp;
		Vector record;
		int primePowers[];

		while ((i < (fBase.baseSize + EXTRA_ROWS)) && !isFactor(result)) {

			if (!myMatrix.rowIsNonZero.get(i)) {
				x = ONE;
				primePowers = new int[fBase.baseSize];

				for (int j = 0; j < (fBase.baseSize + EXTRA_ROWS); j++) {
					if (myMatrix.matrixTrc[i].get(j)) {
						temp = (BigInteger) fRecords.elementAt(j);
						// temp = sqrt(number) +- x[i]
						record = (Vector) Records.elementAt(j);
						tmp = (FactorRecord) record.elementAt(0);
						if (tmp.index == 0) { // -1 is always the first entry
							// -1 is a factor
							temp = num_sqrtf.subtract(temp);
						} else {
							temp = num_sqrtf.add(temp);
							primePowers[tmp.index] = primePowers[tmp.index] 
																+ tmp.exp;
						}
						x = temp.multiply(x);
						x = x.mod(number);
						for (k = 1; k < record.size(); k++) {
							tmp = (FactorRecord) record.elementAt(k);
							primePowers[tmp.index] = primePowers[tmp.index] 
																+ tmp.exp;
						}
					}
				}
				y = ONE;

				// Compute y using y[i]'s

				for (k = 1; k < (fBase.baseSize); k++) {
					if (primePowers[k] > 1) {
						//temp = BigInteger.valueOf(
						//				(fBase.elementAt(k)).prime);
						temp = 	(fBase.elementAt(k)).bigPrime;
						temp = temp.modPow(BigInteger.valueOf
													(primePowers[k]/2),
										   number);
					   	y = y.multiply(temp);
						y = y.mod(number);
					}	
				}

				z = x.add(y);

				// Find GCD (x+y, number)
				result = number.gcd(z);
			}
			i++;
		}
		return result;
	}

	private boolean isFactor(BigInteger result) {

		boolean isfactor = false;

		if (!((result.equals(ONE)) || result.equals(number)))
			isfactor = true;

		return isfactor;
	}
}


class FactorRecord {
	public int index;	// index into the factorBase of the prime
	public int exp;		// exponent of the prime

	FactorRecord(int p, int e) {
		index = p;
		exp = e;
	}
}

class LrgPrimeRecord {

	public int prime;		// the (int-sized) large prime
	public Vector record;	// the record of the factorization of it
	public int count;		// # times factorization occurs w/prime
	public BigInteger inv_j;	// inv + j

	LrgPrimeRecord(int p, Vector r, int c, BigInteger w) {
		prime = p;
		record = r;
		count = c;
		inv_j = w;
	}
}


class FactorBase {
	// This class contains the factor base for the quadratic sieve
	public Vector base;
	public int baseSize;
	public int origSize;
	BigInteger num;
	BigInteger num_sqrtf;

	FactorBase (BigInteger number, BigInteger number_sqrtf, int size){
		int i = 1, next = 0;
		Integer tmp;

		num = number;
		num_sqrtf = number_sqrtf;
		baseSize = size;
		origSize = size;
		base = new Vector(size);
		Vector primes = GetPrimes(size*4);
		base.addElement(new Integer(-1));
		
		while (i < baseSize){
			tmp = (Integer) primes.elementAt(next);
			//System.out.println("FactorBase: " + tmp);
			if (Legendre(number, tmp)){
				base.addElement(new FBaseItem(tmp.intValue()));
				//System.out.println(tmp.toString());
				i++;
			}
			next++;
		}
	}		

	public void addLrgPrime(int p) {

		base.addElement(new FBaseItem(p));
		baseSize++;
	}

	public void solveQC(){
		int nmodp;
		int nfloormodp;
		FBaseItem tmpbase;
		BigInteger bigTmp;
		int a;

		/*System.out.println("Prime" + "\t" + "nmodp" + "\t" + 
							   "sqrtmp" + "\t" + "a" + "\t" + 
							   "a_1" + "\t" + 
							   "a_2" + "\t" + "logp");*/

		for(int i = 1; i < baseSize; i++) { 
			/* solve loop */
			tmpbase = (FBaseItem) base.elementAt(i);
			bigTmp = new BigInteger(Integer.toString(tmpbase.prime));
			nmodp = (num.mod(bigTmp)).intValue();
			nfloormodp = (num_sqrtf.mod(bigTmp)).intValue();
			a = 0;
			while (nmodp != (a*a)%tmpbase.prime)
				a++;
			tmpbase.a_1 = (-nfloormodp + a + tmpbase.prime)%tmpbase.prime;
			tmpbase.a_2 = (-nfloormodp - a + (2*tmpbase.prime))%tmpbase.prime;

			// Do something here - I dunno what 
			if (tmpbase.a_1 == 0)
				tmpbase.a_1 = tmpbase.prime;
			if (tmpbase.a_2 == 0)
				tmpbase.a_2 = tmpbase.prime;

		 	/*System.out.println(tmpbase.prime + "\t" + nmodp + "\t" + 
							   nfloormodp + "\t" + a + "\t" + 
							   tmpbase.a_1 + "\t" + 
							   tmpbase.a_2 + "\t" + tmpbase.logp);*/
		}
	}		
		
	private boolean Legendre(BigInteger number, Integer prime) {
		int n, symbol = 1;
		int p = prime.intValue();

		n = (number.mod(new BigInteger(prime.toString()))).intValue();
		if (n == 0) {
			return false;
		} else {
			int tmp = 0;
			int count = 0;
			if (n < 0) {
			 	n = n * -1;
				if ((p % 4) == 3) {
					symbol = -1;
				}
			}
			while ((n % 2) == 0) {
				n = n / 2;
				count = 1 - count;
			}
			if ((count * ((p*p) - 1)) % 16 == 8) {
				symbol = symbol * -1;
			}
			while (n > 1){
				if ((((n - 1) * (p - 1)) % 8) == 4) {
					symbol = symbol * -1;
				}
				tmp = n;
				n = p % n;
				p = tmp;
				count = 0;
				while ((n % 2) == 0) {
					n = n / 2;
					count = 1 - count;
				}
				if ((count * ((p*p) - 1)) % 16 == 8) {
					symbol = symbol * -1;
				}
			}
			if (symbol == 1)
				return true;
			else
				return false;
		}
	}
		
	private Vector GetPrimes(int size){
	// Uses the sieve of Erotosthenes to generate primes

		int i, j;
		Vector temp = new Vector(size);
		int limit = size * 10;
		BitSet B = new BitSet(limit);

		for(i=2; i < limit; i++) {
			B.set(i);
		}

		for(j=2; (j*j) < limit; j++) {
			if (B.get(j)) {
				for(i = 2*j; i < limit; i = i + j){
					B.clear(i);
				} 		
			}
		}
		for (i=2; i < limit; i++){
			if (B.get(i)) {
				temp.addElement(new Integer(i));
				//System.out.println(Integer.toString(i) + "\n");
			}
		}
		return temp;
	}

	public FBaseItem elementAt(int i) {

		return (FBaseItem) base.elementAt(i);
	}
}

class FBaseItem {
	public int prime;
	public BigInteger bigPrime;
	public int a_1;
	public int a_2;
	public int logp;

	FBaseItem(int p) {
		prime = p;
		bigPrime = BigInteger.valueOf((long) p);
		a_1 = 0;
		a_2 = 0;

		// Calculate log p base 2
		logp = 1 + (int) (((Math.log((double) p)) / Sieve.log2) - 0.5); 

	}
}


class Matrix {
	// This class uses Gaussian Elimination to solve the factorization

	int numRow; 			// Number of rows in the matrices
	int numCol;				// Number of columns in the matrices

	BitSet matrix[];		// numRow X numCol matrix
	BitSet matrixTrc[];		// Trace matrix - to record matrix ops
							// numRow by numRow matrix
	BitSet rowIsNonZero;	// This bitset records whether or not the
							// row in the original matrix is nonzero.

	Matrix(Vector records, int numcol){

		numCol = numcol;
		//numRow = numCol + Sieve.EXTRA_ROWS;
		numRow = records.size();
		matrix = new BitSet[numRow];
		matrixTrc = new BitSet[numRow];
		rowIsNonZero = new BitSet(numRow);
		initMatrices(records);

	}

	
	private void initMatrices(Vector records) {

		int i, j;
		Vector record;
		FactorRecord recEntry;

		for(i = 0; i < numRow; i++) {
			record = (Vector) records.elementAt(i);
			matrix[i] = new BitSet(numCol);
			for(j = 0; j < record.size(); j++) {
				recEntry = (FactorRecord) record.elementAt(j);
				if ((recEntry.exp % 2) == 1)
					matrix[i].set(recEntry.index);
			}
			// Initialize the identity matrix
			matrixTrc[i] = new BitSet(numRow);
			matrixTrc[i].set(i);
		}
	}

	public void GaussianElimination() {

		int i, j;
		int column;
		int oldcol;
		boolean found;
		int row = 0;
		int oldrow = 0;
		int newrow = 0;

		for (column = 0; column < numCol; column++) {
			// Go through each column
			found = false;
			i = row;
			while ((i < numRow) && (!found)) { 	// Find next row with
												// set bit in this column
				if (matrix[i].get(column)) {
					newrow = i;
					rowIsNonZero.set(i);		// Mark this row
					found = true;
				}
				i++;
			}
			if (found) {	// if row has 1 in col, row reduce
				if (newrow > oldrow)
					swapRows(newrow, oldrow);
				row = oldrow + 1;
				addRows(row, oldrow, column);
				oldrow++;
			}
		}
	}

	private void swapRows(int newrow, int oldrow) {
		
		BitSet temp = matrix[newrow];
		matrix[newrow] = matrix[oldrow];
		matrix[oldrow] = temp;
		temp = matrixTrc[newrow];
		matrixTrc[newrow] = matrixTrc[oldrow];
		matrixTrc[oldrow] = temp;
		boolean tmpbit = rowIsNonZero.get(newrow);
		if (rowIsNonZero.get(oldrow))
			rowIsNonZero.set(newrow);
		else
			rowIsNonZero.clear(newrow);
		if (tmpbit)
			rowIsNonZero.set(oldrow);
		else
			rowIsNonZero.clear(oldrow);
	}

	private void addRows(int row, int oldrow, int column) {

		int i, j;

		for (i = row; i < numRow; i++) {
			if (matrix[i].get(column)) {
				// Add rows in matrix and matrixTrc
				matrix[i].xor(matrix[oldrow]);
				matrixTrc[i].xor(matrixTrc[oldrow]);
			}
		}
	}

	public void print() {
		
		for (int i = 0; i < numRow; i++){
			System.out.print(rowIsNonZero.get(i));
			System.out.print(matrix[i]);
			System.out.println(matrixTrc[i]);
		}
	}
}