# 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, & \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.

• Ask about 1. and 3. on Math.SE, and reformulate your question here to focus on 2? (1. is a straightforward fact which can be proven using Legendre's theorem and the Chinese remainder theorem.)
– D.W.
Commented Mar 21, 2016 at 6:18
• Cross-posted on Math.SE: math.stackexchange.com/q/1706827/14578. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted.
– D.W.
Commented Mar 21, 2016 at 17:45