/**
 * 
 */

/**
 * @author sven
 *
 */

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

public class KryptArith {
	char bottomChar='~';
	char topChar='!';
	int bottomInt=(int) bottomChar;
	int topInt=(int) topChar;
	
	public BigInteger modInv(BigInteger a, BigInteger b)
	{
		BigInteger r1 = new BigInteger("0");
		BigInteger r2 = new BigInteger("1");
		BigInteger a_new = new BigInteger("0");
		BigInteger b_new = new BigInteger("0");
		BigInteger r1_new = BigInteger.ZERO;
		BigInteger r2_new = BigInteger.ZERO;
		
		while (b.compareTo(BigInteger.ONE) != 0)
		{
			a_new=b;
			try
			{
				b_new=a.mod(b);
			}
			catch (Exception e)
			{
				System.out.println("No Inverse "+e);
				//System.exit(1);
				return BigInteger.ZERO.subtract(BigInteger.ONE);
			}
			r1_new = r2;
			r2_new=r1.subtract(r2.multiply(a.divide(b)));
			a=a_new;
			b=b_new;
			r1=r1_new;
			r2=r2_new;
		}	
		return r2;
	}
	public int modInv(int a, int b) throws Exception
	{
		int r1 = 1;
		int r2 = 0;
		int r1_new = 1;
		int r2_new = 0;
		int a_new = 0;
		int b_new = 0;

		while (b_new != 1)
		{
			a_new=b;
			/*try
			{
				b_new=a % b;
			}
			catch (Exception e)
			{
				//System.out.println("No Inverse "+e);
				//System.exit(1);
				return -1;
			}*/
			b_new=a % b;
			r1_new = r2;
			r2_new = r1 - ((a / b) * r2);
			a=a_new;
			b=b_new;
			r1=r1_new;
			r2=r2_new;
		}
		
		return r2;
	}
	public int gcd(int a, int b)
	{
		if (b==0) return a;
		   return gcd(b,a%b);
	}
	public BigInteger gcd(BigInteger a, BigInteger b)
	{
		if (b.compareTo(BigInteger.ZERO) == 0) return a;
		   return gcd(b,a.mod(b));
	}
	public static int gen8bitPrim() {
		Random rnd = new Random();
		return BigInteger.probablePrime(8, rnd).intValue();
	}
}