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:
- 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) > 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.
