jacobi static method

BigInt jacobi(BigInt a, BigInt n)

Calculates the Jacobi symbol (a/n) for given integers 'a' and 'n'.

The Jacobi symbol is defined for an odd positive integer 'n' and any integer 'a'.

Returns 0 if 'a' is congruent to 0 modulo 'n'. Returns 1 if 'a' is a quadratic residue modulo 'n'. Returns -1 if 'a' is a non-quadratic residue modulo 'n'.

Throws a JacobiError if 'n' is not an odd integer greater than or equal to 3.

Implementation

static BigInt jacobi(BigInt a, BigInt n) {
  if (!(n >= BigInt.from(3))) {
    throw const JacobiError("n must be larger than 2");
  }
  if (!(n % BigInt.two == BigInt.one)) {
    throw const JacobiError("n must be odd");
  }

  a = a % n;
  if (a == BigInt.zero) {
    return BigInt.zero;
  }
  if (a == BigInt.one) {
    return BigInt.one;
  }

  BigInt a1 = a, e = BigInt.zero;
  while (a1 % BigInt.two == BigInt.zero) {
    a1 = a1 ~/ BigInt.two;
    e = e + BigInt.one;
  }

  BigInt s = BigInt.one;

  if (e % BigInt.two == BigInt.zero ||
      n % BigInt.from(8) == BigInt.one ||
      n % BigInt.from(8) == BigInt.from(7)) {
    // s remains 1
  } else {
    s = BigInt.from(-1);
  }

  if (a1 == BigInt.one) {
    return s;
  }

  if (n % BigInt.from(4) == BigInt.from(3) &&
      a1 % BigInt.from(4) == BigInt.from(3)) {
    s = -s;
  }

  return s * jacobi(n % a1, a1);
}