/*

 Written by

 Boufounos,Petros T    : petrosb@mit.edu
 Castagnola,Luciano    : luciano@mit.edu 
 Michalakis,Nikolaos   : nikos@mit.edu   

 October 11, 2001

 May be freely reproduced for educational or personal use
*/



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

public class FindInverse
{
    static BigInteger TWO=new BigInteger("2");
    static int TRIES = 256;
    
    public static void main(String args[])
    {
	if (args.length>1){
	    System.out.println("Usage: java FindInverse [<primelength>]");
	    System.exit(0);
	}else if(args.length==1){
	    int primelength = Integer.parseInt(args[0]);
	    runForLength(primelength);
	}else{
	    for(int i=1; i<17; i++){
		int length = i * 64;
		System.out.println("length:"+length);
		runForLength(length);
	    }
	}
    }

    public static void runForLength(int primelength){

	Random r = new Random();

	BigInteger prime = new BigInteger(primelength, 2048, r);

	BigInteger[] aarray = new BigInteger[TRIES];
	for(int i=0; i<aarray.length; i++){
	    aarray[i]= RandomBig(prime,r);
	}

	long st1=System.currentTimeMillis();
	for(int i=0;i<TRIES;i++) {
	    findInverse1(aarray[i],prime);
	}
	long et1=System.currentTimeMillis();	

	long st2=System.currentTimeMillis();
	for(int i=0;i<TRIES;i++) {
	    findInverse2(aarray[i],prime);
	}
	long et2=System.currentTimeMillis();	

	System.out.println("findInverse1, elapsed time (ms): "+ (et1-st1));
	System.out.println("findInverse2, elapsed time (ms): "+ (et2-st2));

    }
    
    // only works if p is really a prime!
    public static BigInteger findInverse1(BigInteger a, BigInteger p)
    {
	return a.modPow(p.subtract(TWO),p);
    }

    public static BigInteger findInverse2(BigInteger a, BigInteger p)
    {
	BigInteger[] tmp=Extended_Euclid(a,p);
	
	if(!tmp[0].equals(BigInteger.ONE)){
	    System.out.println("Our \"prime\" was composite!");
	}
	return tmp[1].mod(p);
    }
    
    static BigInteger[] Extended_Euclid(BigInteger a, BigInteger b)
    {
	BigInteger[] Result=new BigInteger[3];;

	if(b.equals(BigInteger.ZERO)) {
	    Result[0]=a;
	    Result[1]=BigInteger.ONE;
	    Result[2]=BigInteger.ZERO;
	    return Result;
	}
	
	BigInteger[] tmp;
	tmp=Extended_Euclid(b,a.mod(b));
	Result[0]=tmp[0];
	Result[1]=tmp[2];
	Result[2]=tmp[1].subtract(a.divide(b).multiply(tmp[2]));
	return Result;

    }

    public static BigInteger RandomBig(BigInteger p)
    {
	Random r = new Random();
	return RandomBig(p, r);
    }
    
    public static BigInteger RandomBig(BigInteger p, Random r)
    {
	BigInteger rndNum= new BigInteger(p.bitLength(), r);
	if(rndNum.compareTo(p)<0){
	    return rndNum;
	}else{
	    //If the number generated is larger than p, try again
	    return RandomBig(p, r);
	}
    }
	    
    //our implementation of modPow, slower than Java's
    public static BigInteger modPow(BigInteger a, BigInteger b, BigInteger m){
	if(b.equals(BigInteger.ZERO)){
	    return BigInteger.ONE;
	}else if(b.testBit(0)){
	    return(a.multiply(modPow(a,b.subtract(BigInteger.ONE),m)).mod(m));
	}else{
	    BigInteger t = modPow(a,b.shiftRight(1),m);
	    return t.multiply(t).mod(m);
	}
    }
}