Legendre + Jacobi Symbols

int jacobi(long a, long n) {
  a = ((a % n) + n) % n;
  int result = 1;
  while (a != 0) {
    while ((a & 1) == 0) {
      a /= 2;
      if (n % 8 == 3 || n % 8 == 5) result = -result;
    }
    long t = a; a = n; n = t;
    if (a % 4 == 3 && n % 4 == 3) result = -result;
    a %= n;
  }
  return n == 1 ? result : 0;
}