6. Legendre Symbol and Jacobi Symbol

We first define Legendre Symbol for odd primes, then generalize it to composite numbers, which is Jacobi Symbol.

6.1. Knowledge required

6.2. Legendre Symbol

6.2.1. Definition

\(p\) is an odd prime number. For any integer \(a \geq 0\), Legendre Symbols

\[\begin{split}L(\frac{a}{p}) = \begin{cases}0 & if ~a \equiv 0~mod~p\\1& if~a~is~QR~mod~p\\-1& if~a~is~QNR~mod~p\end{cases}.\end{split}\]

  1. \(a^{(p-1)/2}\equiv 1~mod~p\) holds iff \(a\) is \(QR~mod~p\) see Quadratic Residue Problem;

  2. \(a = pk\) then \(a^{(p-1)/2} \equiv 0~mod~p\);

  3. \(a^{p-1} \equiv 1~mod~p\) but \(a^{(p-1)/2}\equiv -1 ~mod~p\) if \(a\) is \(QNR~mod~p\). (IMPORTANT)

6.2.2. Theorem

\(p\) is an odd prime, \(L(\frac{a}{p}) \equiv a^{(p-1)/2}~mod~p\)

We know that \(a^{p-1}\equiv 1~mod~p\), so the square root of \(a^{p-1}\) can only be \(\pm 1\). We have a \(O(log^3 p)\) algorithm to compute the Legendre Symbol.

6.3. Jacobi Symbol

\(n\) is an odd positive integer with prime factorization

\[n = \prod_{i=1}^k p_i^{e_i}.\]

Jacobi Symbol

\[(\frac{a}{n}) = \prod_{i=1}^k L(\frac{a}{p_i})^{e_i}\]

6.3.1. Example

\(n = 9975 = 3\times5^2\times7\times19\) and \(a=6278\)

\[\begin{split}(\frac{6278}{9975}) =& L(\frac{6278}{3})L(\frac{6278}{5})^2L(\frac{6278}{7})L(\frac{6278}{19})\\=&L(\frac{2}{3})L(\frac{3}{5})^2L(\frac{6}{7})L(\frac{8}{19})\\=&(-1)(-1)^2(-1)(-1)=-1\end{split}\]

6.3.2. Pseudo Prime

Recall that, the Euler Theorem says if \(n\) is an odd prime, then \(x\) is \(QR~mod~n\) iff \(x^{(p-1)/2} \equiv 1~mod~p\). But what if \(n\) is not an odd prime?

If we can find an \(a\) and an \(n\) such that \((\frac{a}{n}) \equiv a^{(n-1)/2}~mod~n\), \(n\) is a pseudo-prime to base \(a\)!

For example, \((\frac{10}{91}) = -1 \equiv 10^{45}~mod~91\).

If \(n\) is an odd composite number, then \(n\) is an Euler Pseudo Prime (EPP) to base \(a\) for always half of the integers \(a \in [1, n-1]\). This leads to Solovay-Strassen primality test.

6.3.3. Properties for Jacobi Symbol

  1. If \(n\) is an odd integer and \(m_1 \equiv m_2~mod~n\), then \((\frac{m_1}{n}) = (\frac{m_2}{n})\).

\[\begin{split}(\frac{2}{n}) = \begin{cases}+1& if~n\equiv \pm1~mod~8\\-1& if~n\equiv \pm3~mod~8\end{cases}\end{split}\]

  1. \((\frac{m_1m_2}{n}) = (\frac{m_1}{n})(\frac{m_2}{n})\). If \(m=2^kt\) and \(t\) is odd, then \((\frac{m}{n})=(\frac{2}{n})^k(\frac{t}{n})\).

  2. \(m\) and \(n\) are odd integers, then

\[\begin{split}(\frac{m}{n}) = \begin{cases}-(\frac{n}{m})& if~m\equiv n\equiv 3~mod~4\\(\frac{n}{m})& o.w.\end{cases}\end{split}\]

Example:

\[(\frac{7411}{9283}) = -(\frac{9283}{7411})= -(\frac{1872}{7411})= -(\frac{2}{7411})^4(\frac{117}{7411}) =-(\frac{117}{7411})=-(\frac{7411}{117})=-(\frac{40}{117})=-(\frac{2}{117})^3(\frac{5}{117}) = (\frac{5}{117})=(\frac{117}{5})=(\frac{2}{5})=-1\]

The complexity reduces from \(O(\log^3n)\) to \(O(\log n) \times O(\log^2n)\)

6.4. Solovay-Strassen

To check whether \(n\) is prime or not, randomly choose an integer \(a \in [1, n-1]\). If \((\frac{a}{n}) \equiv a^{(n-1)/2}~mod~n\), then \(n\) may be a prime, if not \(n\) is definitely a composite.

6.5. Blum Integer

A composite integer is called Blum Integer if \(n=pq\) where \(p\) and \(q\) are distinct prime numbers satisfying \(p\equiv q\equiv 3~mod~4\).

6.5.1. Theorem

For a Blum integer \(n\) the followings hold:

  1. \((\frac{-1}{p})(\frac{-1}{q}) = -1\) then \((\frac{-1}{n})=-1\);

  2. For \(y \in \mathbb{Z}_n^*\), if \((\frac{y}{n})=1\), then either \(y \in QR_n\) or \(-y \in QR_n\). Don’t confuse Jacobi Symbol with Legendre Symbol here.

  3. For any \(y \in QR_n\), it has four square roots \(u, -u, v, -v\). They satisfy the following properties

  • \((\frac{u}{p})=1\) and \((\frac{u}{q})=1\) i.e. \(u \in QR_n\)

  • \((\frac{-u}{p})=-1\) and \((\frac{-u}{q})=-1\), then \(u\) is a pseudo square mod \(n\), i.e. \((\frac{u}{n})=1\)

  • \((\frac{v}{p})=-1\) and \((\frac{v}{q})=+1\)

  • \((\frac{-v}{p})=+1\) and \((\frac{-v}{q})=-1\)

  1. Function \(f(x)=x^2~mod~n\) is a permutation of \(QR_n\);

  2. For \(y \in QR_n\), exactly one square root of \(y\) with Jacobi symbol \(1\) is less then \(n/2\).