How to compute Jacobi symbol efficiently? 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, &amp; \text{if } \gcd(N,A) \ne 1, \\
  1, &amp; \text{if } A \text{ is a quadratic residue modulo $N$} \\ 
  -1, &amp; \text{otherwise}.
\end{cases}$$

Then they state the following properties:


For every odd prime $N$ and $A ∈ [N − 1]$, $QR_N (A) = A^{\frac{(N−1)}{2}}
\pmod N$.
The Jacobi symbol is computable in time $O(\log A \cdot \log N)$.
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) &gt; 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.
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.