/*
 * homework 2
 * the methods in this class are to deal with the questions in homework2
 * Hua Zhang
 * 06/27/2003
*/

// Note: Code for a version of Miller-Rabin will be posted shortly. Hua used the version written for Java.

import java.math.*;

public class hw2
{

	//invoke the methods one by one 
	public static void main(String[] args)
	{
		//Question1();
		//Question2();
		//Question31();
		//Question32();
		Question4();
		//Question5();
		//Question6();
		//Question7();
		//ExtraCredits();
	}
	
	//method to solve question1
	private static void Question1()
	{
		//Initialize BInt as 10 to the 20th
		BigInteger BInt = BigInteger.valueOf(10).pow(30);
		//number of possibly prime integers found
		byte bNum = 0;
		
		System.out.println("Question 1: The first five prime numbers greater than 10 to the power of 30:");
		//loop until we found 5 possibly prime integers
		while (bNum < 5)
		{
			//Call MillerRabin() to test BInt
			if ( MillerRabin(BInt)) 
			{
				bNum++;
				System.out.println(BInt);
			} 
			
			//increase BInt to Bint + 1
			BInt = BInt.add(BigInteger.ONE);
		}
	}
	
	//method to solve question1
	private static void Question2()
	{
		int i,j;
		i = 187072301;
		
		System.out.println("Question 2: The factors of 187072301:");
		j = 3;
		while (i > 1)
		{
			if (i % j == 0)
			{
				System.out.println(j);
				i = i / j;
			}
			else
			{
				j++;
			}
		}
	}
	
	//method1 to solve question3, find inverse
	private static void Question31()
	{
		int i,j,k;
		i = 25;
		j = 11;
		
		for (k=1;k<i;k++)
		{
			if ((j*k) % i == 1)
			{
				System.out.println(k);
				return;
			}
		}
	}

	//method2 to solve question3, Chinese Remainder Threom
	private static void Question32()
	{
		BigInteger a1 = BigInteger.valueOf(41);
		BigInteger a2 = BigInteger.valueOf(70);
		BigInteger a3 = BigInteger.valueOf(23);
		BigInteger m1 = BigInteger.valueOf(91);
		BigInteger m2 = BigInteger.valueOf(72);
		BigInteger m3 = BigInteger.valueOf(25);
		BigInteger M1 = m2.multiply(m3);
		BigInteger M2 = m1.multiply(m3);
		BigInteger M3 = m1.multiply(m2);
		BigInteger rM1 = M1.modInverse(m1);
		BigInteger rM2 = M2.modInverse(m2);
		BigInteger rM3 = M3.modInverse(m3);
		BigInteger M = m1.multiply(m2).multiply(m3); //m1*m2*m3
		BigInteger A; // the result
		
		//add up ai*ci, which is ai*Mi*rMi
		A = a1.multiply(M1).multiply(rM1);
		A = A.add(a2.multiply(M2).multiply(rM2));
		A = A.add(a3.multiply(M3).multiply(rM3));
		A = A.mod(M);
		
		//print out
		System.out.println();
		System.out.print("Question 3: x = ");
		System.out.print(A);
		System.out.print(" (mod ");
		System.out.print(M);
		System.out.println(")");
	}

	//method to solve question4
	//I solved this question by brute force, testing all g and x between 1 and 210
	private static void Question4()
	{
		//if g to the power of some x is i, set faHit[i] = true; 
		boolean faHit[] = new boolean[211];
		BigInteger g = BigInteger.valueOf(2);
		BigInteger biMod = BigInteger.valueOf(211);
		int i,j; //index
		int x=0; //x that we want to find
		int iNumber=0; //number of primitive roots found
				
		System.out.println();
		System.out.println("Question 4: Primitive roots and corresponding x:");
		//loop until g = 211
		while (!g.equals(BigInteger.valueOf(211)))
		{
			//Initialize faHit[] to false
			for (i=0;i<211;i++) faHit[i] = false;
			
			//raise g to the power of 1 to 210, update faHit[i] if i is hit
			//record x when 203 is hit
			for (i=1;i<211;i++) 
			{
				//calculate g^i mode 211
				j = g.pow(i).mod(biMod).intValue();
				faHit[j] = true;
				//if j is 203, record x 
				if (j == 203) x = i;
			}
			
			//check if all i, 0<i<193 are hit, break if not hit
			for (i=1;i<211;i++) if (!faHit[i]) break;
			
			//if all i are hit, g is a primitive root
			if (i == 211)
			{
				//increase the number of primitive roots found
				iNumber++;
				
				//print out g and x
				System.out.print("Primitive root: ");
				System.out.print(g);
				System.out.print(";		x=");
				System.out.println(x); 
			}
			
			//next g
			g = g.add(BigInteger.ONE);
		}
		//print out the number of primitive roots found
		System.out.print("Number of primitive roots found:	");
		System.out.println(iNumber);
	}