//for cis3362
//By: Hua Zhang
//Date: November 20 2006

// Edited by Arup Guha on 11/30/07 for CIS 3362 Fall 07 Hmk7 Solutions

import java.math.*;
import java.util.*;

public class Homework7 {

	public static void main(String[] args) {
		question1();
		question2();
		question3();
		question4();
		question5();
	}

	private static void question1 () {
		
		// Set up p, q, and e.
		BigInteger p = new BigInteger("9123723991");
		BigInteger q = new BigInteger("2178212317");
		BigInteger e = new BigInteger("91247182832917");
		
		// Solve for phi(n).
		p = p.subtract(BigInteger.ONE);
		q = q.subtract(BigInteger.ONE);
		BigInteger phi = p.multiply(q);
		
		// d is just the appropriate modular inverse.
		BigInteger d = e.modInverse(phi);
		
		// Print these out.
		System.out.println("phi(n) = "+phi);
		System.out.println("d = "+d);
		
	}
	
	private static void question2 () {
		
		// Set up all of our variables.
		int n = 30991999;
		int x = (int)Math.sqrt(n)+1;
		int z = 1;
		double sqrt = 0;
		
		// Loop...
		while (true) {
			
			// Calculate the next value of z.
			z = x * x - n;
			sqrt = Math.sqrt(z);
			System.out.println(x + " : " + z + " : " + sqrt);
			x++;
			
			// If it's a perfect square, we've got the factorization!
			if (Math.abs(sqrt - (int)sqrt) < 0.0000001) break;
		}
	}
	
	private static void question3() {
		
		// Set up both of our e's.
		BigInteger e1 = new BigInteger("13249");
		BigInteger e2 = new BigInteger("14567");
		
		// This modular inverse is x.
		BigInteger x = e1.modInverse(e2);
		
		// y = (e1*x-1)/e2, by solving the equation for y.
		BigInteger negy = (e1.multiply(x).subtract(BigInteger.ONE)).divide(e2);
		
		// Print out the answers.
		System.out.println("x = "+x+" and y = -"+negy);
	}
	
	private static void question4() {
		
		Scanner stdin = new Scanner(System.in);
		
		// Get all the necessary information.
		System.out.println("Enter p.");
		BigInteger p = getNextPrime(stdin.next());
		System.out.println("Enter your generator.");
		BigInteger g = new BigInteger(stdin.next());
		System.out.println("Enter b.");
		BigInteger b = new BigInteger(stdin.next());
		System.out.println("Enter k.");
		BigInteger k = new BigInteger(stdin.next());
		
		// Calculate c1 and part of c2.
		BigInteger c1 = g.modPow(k, p);
		BigInteger c2 = b.modPow(k, p);
		
		// Here we get the message from the user.
		System.out.println("Please enter your message. It should be in between 1 and "+p);
		BigInteger m = new BigInteger(stdin.next());
		
		// Now, we can calculate the rest of the second ciphertext.
		c2 = c2.multiply(m);
		c2 = c2.mod(p);
		
		// Print out the two ciphertexts.
		System.out.println("The corresponding cipher texts are c1 = "+c1+" c2 = "+c2);
	}
	
	private static void question5() {
		
		// Set up the key and call the subset sum function to find the appropriate subset.
		int[] key = { 75076539, 15666230, 108665657, 64921578, 111920268, 92738675, 87964607, 101981004, 108705923, 10105117, 59440997, 99830777, 104405469, 1504209, 115059062, 99016263, 122955987, 74451021, 34594740, 69189480, 46507862, 72836178, 127749468, 48192207};
		System.out.println("The subset that adds to 738720866 is "+subsetSum(key, 738720866));
	}
	
	
	
	// Incrementally tries each BigInteger starting at the value passed
	// in as a parameter until one of them is tests as being prime.
	public static BigInteger getNextPrime(String ans) {
		
		BigInteger one = new BigInteger("1");
		BigInteger test = new BigInteger(ans);
		while (!test.isProbablePrime(99))
			test = test.add(one);
		return test;		
	}
	
	// If a subset of values sums to target, a String is returned which stores
	// the values that adds to target, separated by commas. Otherwise an empty
	// String is returned.
	public static String subsetSum(int[] values, int target) {
    	return subsetSumHelp("", values, values.length, target);
  	}

  	public static String subsetSumHelp(String sub, int[] values, int size, int target) {

    	// Empty set's elements sum to 0, so return our stored string.
    	if (target == 0)
      		return sub;

    	// Considering an empty set and our target is non-zero, so no luck.
    	if (size == 0)
      		return "";
   
    	// Try out NOT taking the element stored at values[size-1];
    	String answer = subsetSumHelp(sub, values, size-1, target);
    	
    	// If that didn't work, then try TAKING that value.
    	if (answer.equals(""))
    		return subsetSumHelp(sub+", "+values[size-1],values, size-1, target-values[size-1]);
    	
    	// Otherwise, the original answer works!
    	else
    		return answer;
 
  }

}