Editing Jacobi symbol (section)

==Calculating the Jacobi symbol==

The above formulas lead to an efficient {{nowrap|[[Big O notation|''O'']](log ''a'' log ''b'')}}<ref>Cohen, pp. 29–31</ref> [[algorithm]] for calculating the Jacobi symbol, analogous to the [[Euclidean algorithm]] for finding the gcd of two numbers. (This should not be surprising in light of rule 2.)

# Reduce the "numerator" modulo the "denominator" using rule 2.
# Extract any even "numerator" using rule 9.
# If the "numerator" is 1, rules 3 and 4 give a result of 1. If the "numerator" and "denominator" are not coprime, rule 3 gives a result of 0.
# Otherwise, the "numerator" and "denominator" are now odd positive coprime integers, so we can flip the symbol using rule 6, then return to step 1.

In addition to the codes below, Riesel<ref>p. 285</ref> has it in [[Pascal (programming language)|Pascal]].
===Implementation in [[Lua (programming language)|Lua]]===
<syntaxhighlight lang="lua">
function jacobi(n, k)
  assert(k > 0 and k % 2 == 1)
  n = n % k
  t = 1
  while n ~= 0 do
    while n % 2 == 0 do
      n = n / 2
      r = k % 8
      if r == 3 or r == 5 then
        t = -t
      end
    end
    n, k = k, n
    if n % 4 == 3 and k % 4 == 3 then
      t = -t
    end
    n = n % k
  end
  if k == 1 then
    return t
  else
    return 0
  end
end
</syntaxhighlight>

=== Implementation in [[C++]] ===
<syntaxhighlight lang="c++">
// a/n is represented as (a,n)
int jacobi(int a, int n) {
    assert(n > 0 && n%2 == 1);
    // Step 1
    a = (a % n + n) % n; // Handle (a < 0)
    // Step 3
    int t = 0;   // XOR of bits 1 and 2 determines sign of return value
    while (a != 0) {
        // Step 2
        while (a % 4 == 0)
            a /= 4;
        if (a % 2 == 0) {
            t ^= n;  // Could be "^= n & 6"; we only care about bits 1 and 2
            a /= 2;
        }
        // Step 4
        t ^= a & n & 2;  // Flip sign if a % 4 == n % 4 == 3
        int r = n % a;
        n = a;
        a = r;
    }
    if (n != 1)
        return 0;
    else if ((t ^ (t >> 1)) & 2)
        return -1;
    else
        return 1;
}
</syntaxhighlight>