public static int jacobi(BigInteger A,BigInteger B){
  BigInteger a, b, v;
  long k=1;
  k=1;
  if (B.equals(ZERO)) {
    a=A.abs();
    return a.equals(ONE) ? 1 : 0;
  }
  if (!A.testBit(0) && !B.testBit(0)) {
    return 0;
  }
  a=A;
  b=B;
  if (b.signum() == -1) {
    b=b.negate();
    if (a.signum() == -1) {
      k=-1;
    }
  }
  v=ZERO;
  while (!b.testBit(0)) {
    v=v.add(ONE);
    b=b.divide(TWO);
  }
  if (v.testBit(0)) {
    k=k * jacobiTable[a.intValue() & 7];
  }
  if (a.signum() < 0) {
    if (b.testBit(1)) {
      k=-k;
    }
    a=a.negate();
  }
  while (a.signum() != 0) {
    v=ZERO;
    while (!a.testBit(0)) {
      v=v.add(ONE);
      a=a.divide(TWO);
    }
    if (v.testBit(0)) {
      k=k * jacobiTable[b.intValue() & 7];
    }
    if (a.compareTo(b) < 0) {
      BigInteger x=a;
      a=b;
      b=x;
      if (a.testBit(1) && b.testBit(1)) {
        k=-k;
      }
    }
    a=a.subtract(b);
  }
  return b.equals(ONE) ? (int)k : 0;
}

public static int jacobi ( BigInteger A , BigInteger B ) { BigInteger a , b , v ; long k = 1 ; k = 1 ; if ( B . equals ( ZERO ) ) { a = A . abs ( ) ; return a . equals ( ONE ) ? 1 : 0 ; } if ( ! A . testBit ( 0 ) && ! B . testBit ( 0 ) ) { return 0 ; } a = A ; b = B ; if ( b . signum ( ) == - 1 ) { b = b . negate ( ) ; if ( a . signum ( ) == - 1 ) { k = - 1 ; } } v = ZERO ; while ( ! b . testBit ( 0 ) ) { v = v . add ( ONE ) ; b = b . divide ( TWO ) ; } if ( v . testBit ( 0 ) ) { k = k * jacobiTable [ a . intValue ( ) & 7 ] ; } if ( a . signum ( ) < 0 ) { if ( b . testBit ( 1 ) ) { k = - k ; } a = a . negate ( ) ; } while ( a . signum ( ) != 0 ) { v = ZERO ; while ( ! a . testBit ( 0 ) ) { v = v . add ( ONE ) ; a = a . divide ( TWO ) ; } if ( v . testBit ( 0 ) ) { k = k * jacobiTable [ b . intValue ( ) & 7 ] ; } if ( a . compareTo ( b ) < 0 ) { BigInteger x = a ; a = b ; b = x ; if ( a . testBit ( 1 ) && b . testBit ( 1 ) ) { k = - k ; } } a = a . subtract ( b ) ; } return b . equals ( ONE ) ? ( int ) k : 0 ; }
computes the value of the jacobi symbol ( a | b ) . the following properties hold for the jacobi symbol which makes it a very efficient way to evaluate the legendre symbol < p > ( a | b ) = 0 if gcd ( a , b ) & gt ; 1 < br > ( - 1 | b ) = 1 if n = 1 ( mod 1 ) < br > ( - 1 | b ) = - 1 if n = 3 ( mod 4 ) < br > ( a | b ) ( c | b ) = ( ac | b ) < br > ( a | b ) ( a | c ) = ( a | cb ) < br > ( a | b ) = ( c | b ) if a = c ( mod b ) < br > ( 2 | b ) = 1 if n = 1 or 7 ( mod 8 ) < br > ( 2 | b ) = 1 if n = 3 or 5 ( mod 8 )
