import java.math.BigInteger;
import java.util.*;
import java.security.*;

// Uses pollard's rho method
// see http://de.wikipedia.org/wiki/Pollard-Rho-Methode (German)

public class Practical14_efactors {

	public static BigInteger[] gcd(BigInteger a, BigInteger b) {
		
			/*
			 * Euclids' algorithm
			 * 
			 * gcd(9,140) = 1 (greatest common divisor)
			 * 
			 *  a		b 	c	 d 
			 *  140 = 	9 * 15 + 5
			 * 
			 *  a=b		b=d   c=a/b		a-b*c 
			 *  9	=	5   * 1			 + 4
			 *  5   =   4   * 1  		 + 1 <-- gcd(9,140)
			 *  4   =   1   * 4  		 + 0
			 * 
			 */
			
			Vector myvector = new Vector();
			
			BigInteger c = new BigInteger("0");
			BigInteger d = new BigInteger("0");
			BigInteger gcd_a_b = new BigInteger("0");
		
			BigInteger q = new BigInteger("0");
			BigInteger r = new BigInteger("0");
			BigInteger s = new BigInteger("0");
			BigInteger t = new BigInteger("0");

			BigInteger previous_q = new BigInteger("0");
			BigInteger previous_s = new BigInteger("0");
			BigInteger previous_previous_s = new BigInteger("0");
			BigInteger previous_t = new BigInteger("0");
			BigInteger previous_previous_t = new BigInteger("0");
			BigInteger minus_one = new BigInteger("-1");
			
			BigInteger mr_x = new BigInteger("0");
			BigInteger mr_y = new BigInteger("0");
			
			if (a.compareTo(BigInteger.ZERO) == 0) a = BigInteger.ONE;
			if (b.compareTo(BigInteger.ZERO) == 0) b = BigInteger.ONE;
			
			//System.out.print("a	b	c	d");
			//System.out.print("	");
			//System.out.println("q	r	s	t");
			
			if (a.compareTo(BigInteger.ZERO) == -1) a = minus_one.multiply(a);
			if (b.compareTo(BigInteger.ZERO) == -1) b = minus_one.multiply(b);
		
			int ctr = 0;

			if (b.compareTo(BigInteger.ONE) == 0) {
				
				gcd_a_b = b;
			
			} else {
				
				do {
					
					if (ctr == 0) {
							
						s = BigInteger.ONE;
						t = BigInteger.ZERO;
						
					}
		
					if (ctr == 1) {
							
						s = BigInteger.ZERO;
						t = BigInteger.ONE;
						
					}
						
					if (ctr > 1) {
							
						s = minus_one.multiply(previous_q);
						s = s.multiply(previous_s);
						s = s.add(previous_previous_s);
						t = minus_one.multiply(previous_q);
						t = t.multiply(previous_t);
						t = t.add(previous_previous_t);
		
					}
		
					q = c;
									
					c = a.divide(b);
					d = a.subtract(b.multiply(c));
		
					r = a;
				
					/*
					System.out.print(a);
					System.out.print("	");
					System.out.print(b);
					System.out.print("	");
					System.out.print(c);
					System.out.print("	");
					System.out.print(d);
					System.out.print("	");
					System.out.print(q);
					System.out.print("	");
					System.out.print(r);
					System.out.print("	");
					System.out.print(s);
					System.out.print("	");
					System.out.print(t);
					System.out.print(" ");
					System.out.println(" ");
					*/	
						
					a = b;
					b = d;
					ctr++;
					previous_q = q;
					previous_previous_s = previous_s;
					previous_s = s;
					previous_previous_t = previous_t;
					previous_t = t;
		
				} while (d.compareTo(BigInteger.ZERO) == 1);
	
				gcd_a_b = a;
					
				q = c;
				r = a;
		
				s = minus_one.multiply(previous_q);
				s = s.multiply(previous_s);
				s = s.add(previous_previous_s);
		
				t = minus_one.multiply(previous_q);
				t = t.multiply(previous_t);
				t = t.add(previous_previous_t);
					
				mr_x = s;
				mr_y = t;
					
				/*
				System.out.print("			 	");
				System.out.print(q);
				System.out.print("	");
				System.out.print(r);
				System.out.print("	");
				System.out.print(s);
				System.out.print("	");
				System.out.print(t);
				System.out.print(" ");
				System.out.println(" ");
				System.out.println(" ");
				System.out.println(gcd_a_b);
				System.out.println(mr_x);
				System.out.println(mr_y);
				*/
				
			} 
			
			if (a.compareTo(b) == 0) gcd_a_b = a;
							
			myvector.add(gcd_a_b);
			
			return (BigInteger[]) myvector.toArray(new BigInteger[] {});		
			
	}
	
	public static BigInteger function_xy(BigInteger x, BigInteger modulus) {
		
		BigInteger result = new BigInteger("0");
		BigInteger twelve = new BigInteger("12");

		//result = x.multiply(x).subtract(BigInteger.ONE).mod(modulus);	
		result = x.multiply(x).add(twelve).mod(modulus);
		return result;
		
	}
	
	public static BigInteger expm(BigInteger m, BigInteger a, BigInteger b) {

		BigInteger result = new BigInteger("1");
		BigInteger zwei = new BigInteger("2");
		BigInteger base = new BigInteger("0");
		
		base = a;
		
		while (b.compareTo(BigInteger.ONE) == 1) {
			
			if (b.mod(zwei).compareTo(BigInteger.ONE) == 0) {
				
				result = result.multiply(base);
				base = base.multiply(base).mod(m);
				
			} else {

				base = base.multiply(base).mod(m);
				
			}
			
			b = b.divide(zwei); 
						
		}
		
		if (b.mod(zwei).compareTo(BigInteger.ONE) == 0) {
			
			result = result.multiply(base).mod(m);
			base = base.multiply(base).mod(m);
			
		} else {

			base = base.multiply(base).mod(m);
			
		}

		return result;
			
	}
	
	public static BigInteger myexp(BigInteger a, BigInteger b) {

		BigInteger result = new BigInteger("1");
		
		while (b.compareTo(BigInteger.ZERO) != 0) {
			
			result = result.multiply(a);
			b = b.subtract(BigInteger.ONE);
				
		}
		
		return result;
			
	}

	public static BigInteger gen_a(BigInteger x) {
		
		BigInteger new_a = new BigInteger(x.bitLength()-1,new SecureRandom());
		BigInteger two = new BigInteger("2");
		
		if (new_a.compareTo(two) <= 0) return Practical14_efactors.gen_a(x); 
		
		return new_a;
		
	}
	
	public static boolean mr(BigInteger x, BigInteger t) {
		
		BigInteger d = new BigInteger("0");
		BigInteger a = new BigInteger("0");
		BigInteger b = new BigInteger("0");
		BigInteger two = new BigInteger("2");
		BigInteger s = new BigInteger("0");
		BigInteger s_ctr = new BigInteger("0");
		BigInteger r = new BigInteger("0");
		boolean result = false;
		
		while (s_ctr.compareTo(BigInteger.valueOf(x.bitLength())) <= 0) {
		
			if (x.subtract(BigInteger.ONE).mod(Practical14_efactors.myexp(two,s_ctr)).compareTo(BigInteger.ZERO) == 0) {

				s = s_ctr;
				
			}	
				
			s_ctr = s_ctr.add(BigInteger.ONE);
			
		}
		
		d = x.subtract(BigInteger.ONE).divide(Practical14_efactors.myexp(two,s));
		
		a = Practical14_efactors.gen_a(x);
		
		while (t.compareTo(BigInteger.ZERO) != 0) {

			if (Practical14_efactors.expm(x,a,d).compareTo(BigInteger.ONE) == 0) {
				
				a = Practical14_efactors.gen_a(x);
				
			} else {
				
				while (r.compareTo(s.subtract(BigInteger.ONE)) <= 0) {
			
					b = Practical14_efactors.myexp(two,r).multiply(d);
					
					if (Practical14_efactors.expm(x,a,b).compareTo(x.subtract(BigInteger.ONE)) == 0) {
						
						result = true;
						a = Practical14_efactors.gen_a(x);
						
					} 
					
					r = r.add(BigInteger.ONE);
				
				}
		
			}	
				
			t = t.subtract(BigInteger.ONE);
			
		}	
			
		return result;
		
	}
		
	public static Vector efactors(BigInteger number) {
		
		Vector myvector = new Vector();
		BigInteger temp_sum_a = new BigInteger("0");
		BigInteger temp_sum_b = new BigInteger("0");
		BigInteger product_temp_sums = new BigInteger("0");
		BigInteger a = new BigInteger("0");
		BigInteger b = new BigInteger("0");
		BigInteger c = new BigInteger("2");
		BigInteger five = new BigInteger("15");
		BigInteger result = new BigInteger("0");
		BigInteger two = new BigInteger("2");
		BigInteger temp1 = new BigInteger("0");
		BigInteger temp2 = new BigInteger("0");
		BigInteger iterations = new BigInteger("20");
		boolean has_factors = false;

		BigInteger rand_x = new BigInteger("1");
		BigInteger rand_y = new BigInteger("1");

		// is number prime?
		if (Practical14_efactors.mr(number,iterations) == true) {
			
			myvector.add(number);
			myvector.add(BigInteger.ONE);
			
		} else {
			
			// Not prime
		
			// Divisble by 2?
	
			while(number.mod(two).compareTo(BigInteger.ZERO) == 0) {
					
				System.out.println("Number: "+number);
				number = number.divide(two);
				myvector.add(two);
					
			}	
			
			a = Practical14_efactors.function_xy(rand_x,number);
			b = Practical14_efactors.function_xy(rand_y,number);
			b = Practical14_efactors.function_xy(b,number);
			temp_sum_a = a.subtract(b);
	
			/*
			System.out.print("A 1: "+a);
			System.out.print(" B 1: "+b);
			System.out.print(" A-B 1: "+temp_sum_a);
			System.out.print(" gcd(a,b): "+Practical4_efactors.gcd(a,b)[0]);
			System.out.println("");
			*/
				
			do {
				
				a = Practical14_efactors.function_xy(a,number);
				b = Practical14_efactors.function_xy(b,number);
				b = Practical14_efactors.function_xy(b,number).mod(number);
								
				temp_sum_b = a.subtract(b);
				product_temp_sums = temp_sum_a.multiply(temp_sum_b);
					
				/*
				System.out.print("A "+c+": "+a);
				System.out.print(" B "+c+" (b): "+b);
				System.out.print(" A-B "+c+": "+temp_sum_b);
				System.out.print(" gcd(a,b): "+Practical4_efactors.gcd(product_temp_sums,number)[0]);
				System.out.println("");
				*/
				
				product_temp_sums = temp_sum_a.multiply(temp_sum_b);
								
			} while (Practical14_efactors.gcd(product_temp_sums,number)[0].compareTo(BigInteger.ONE) != 1);
					
			myvector.add(Practical14_efactors.gcd(product_temp_sums,number)[0]);
			myvector.add(number.divide(Practical14_efactors.gcd(product_temp_sums,number)[0]));

		}	
				
		return myvector;
		
	}
			
	public static void main(String[] args) {
	
		//BigInteger n = new BigInteger("646725328143948472764927636489459626273646725328143948472764927636489459626273");
		//BigInteger n = new BigInteger("2411");
		//BigInteger n = new BigInteger("16061993");
		BigInteger n = new BigInteger("2411");
		int ctr = 1;
				
		System.out.println("Factors of "+n+":");
		System.out.println("=============================");
		
		for (Enumeration el = Practical14_efactors.efactors(n).elements(); el.hasMoreElements();) {
			
			System.out.println(+ctr+": "+el.nextElement());
			ctr++;
		
		}
		
	}

}