How to compute Jacobi symbol efficiently?

Question

How do I compute the Jacobi symbol $(N|A)$ efficiently?

In particular, for every odd $N, A$, define the Jacobi symbol $(A|N)$ as $\prod_i Q_{p_i}(A)$ where $p_1, \dots , p_k$ are all the (not necessarily distinct) prime factors of $N$ (i.e., $N =\prod_i p_i$), and where $Q_p(A)$ is defined as below (i.e., $Q_p(A)$ is the Legendre symbol $(A|p)$).

Arora and Barak claim that the Jacobi symbol is computable in time $O(\log A \cdot \log N)$. How do I see this? What algorithm can be used to compute the Jacobi symbol like this?

---

Motivation:

Sanjeev Arora and Barak sketch a proof that $PRIMES$ is in $BPP$. First they define a function $Q_N(A)$

$$Q_N(A) = \begin{cases} 0, & \text{if } \gcd(N,A) \ne 1, \\ 1, & \text{if } A \text{ is a quadratic residue modulo $N$} \\ -1, & \text{otherwise}. \end{cases}$$

Then they state the following properties:

1. For every odd prime $N$ and $A ∈ [N − 1]$, $QR_N (A) = A^{\frac{(N−1)}{2}} \pmod N$.
2. The Jacobi symbol is computable in time $O(\log A \cdot \log N)$.
3. For every odd composite $N$, $|\{A ∈ [N − 1] : gcd(N, A) = 1 \text{ and } (A|N) = A^{\frac{(N−1)}{2}}\}| \le \frac{1}{2}|\{A ∈[N − 1] : gcd(N, A) = 1\}|$

Then they give the corresponding algorithm :
Choose a random $1 \le A \le N$, if $gcd(N, A) > 1$ or $(A|N) = A^{\frac{(N−1)}{2}} \pmod N$ then output “composite”, otherwise output “prime”.

If all the above 3 properties hold then I can see that $PRIMES$ is in $BPP$, but I am unable to prove property 2, regarding the Jacobi symbol.

Answer 1

The Wikipedia article on the Jacobi symbol describes an efficient algorithm for calculating it which uses quadratic reciprocity and operates similarly to the GCD algorithm.