Mod Inverse

modinv.java

	static int modinv(int a, int b)
	{
		int a0 = a;
		int b0 = b;
		
		int t0 = 0;
		int t = 1;
		int q = (int)Math.floor( a0 / b0 );
		
		int r = a0 - (q * b0);
		
		while( r > 0 )
		{
			int temp = (t0 - (q * t )) % a;
			t0 = t;
			t = temp;
			a0 = b0;
			b0 = r;
			q = (int)Math.floor(a0 / b0);
			r = a0 - (q * b0);
		}
		
		if( b0 != 1 )
			return -1;
		else
			return t;
	}