public static long witness(long a, long i, long n)

{
 long x,y;

   if (i == 0)
      return 1;

   x = witness(a, i/2, n);

   if ( x == 0 ) return x;       // n not prime

   y = ( x * x ) % n ;

   if ( y==1 && x != 1 && x!= n-1)
        return 0;                     // n not prime

   if ( i % 2 != 0 )
       y= ( a * y ) % n;

   return  y;             // n not prime if y != 1
}