World's most popular travel blog for travel bloggers.

[Answers] How to compute Jacobi symbol efficiently?

, , No Comments
Problem Detail: 

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.

Asked By : sashas

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54712

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback