---
tags: vaje, kirv, jacobi, legendre
hackmd: https://hackmd.io/N2rdGiAUQ3iZ9q_W09mPbg
plugins: mathjax
---
# Cryptography and computer security - Tutorial 24.11.2020

---

## Jacobi symbols

### Exercise 1

Let <i>$p$</i> be an odd prime. How many quadratic residues are there in <i>$\mathbb{Z}_p$</i>?

----

* <i>$a$</i> is a quadratic residue in <i>$\mathbb{Z}_{p}$</i> when there exists <i>$x \in \mathbb{Z}^*_{p}$</i> such that <i>$a \equiv x^2 \pmod{p}$</i>
* <i>$x^2 - a \equiv 0 \pmod{p}$</i>
* when varying <i>$x$</i>, each value <i>$a$</i> appears twice
* since there are <i>$p-1$</i> numbers in <i>$\mathbb{Z}^*_{p}$</i>, there are <i>$(p-1)/2$</i> of quadratic residues in <i>$\mathbb{Z}_{p}$</i>
* also, there are <i>$(p-1)/2$</i> quadratic non-residues

---

### Exercise 2

For an integer <i>$a$</i> and an odd positive integer <i>$n = \prod_{i=1}^k p_i^{e_i}$</i>, define the *Jacobi symbol*:

$$
\left({a \over n}\right) = \prod_{i=1}^k \left({a \over p_i}\right)^{e_i} ,
$$

where

$$
\left({a \over p}\right) = \begin{cases}
0 & \text{if $a \equiv 0 \pmod{p}$,} \\
1 & \text{if $a$ is a quadratic residue modulo $p$, and} \\
-1 & \text{if $a$ is a quadratic non-residue modulo $p$}
\end{cases}
$$

is the *Legendre symbol*. Prove the following properties for the Jacobi symbol.

1. If <i>$m_1 \equiv m_2 \pmod{n}$</i>, then
$$
\left({m_1 \over n}\right) = \left({m_2 \over n}\right) .
$$

2. $$
\left({m_1 m_2 \over n}\right) = \left({m_1 \over n}\right) \left({m_2 \over n}\right) .
$$

----

Assuming <i>$a \in \mathbb{Z}^*_p$</i>:
* <i>$a^{p-1} \equiv 1 \pmod{p}$</i>
* <i>$a^{(p-1)/2} \equiv \left({a \over p}\right) \pmod{p}$</i>

1. $$
\begin{aligned}
\left({m_1 \over n}\right) &= \prod_{i=1}^k \left({m_1 \over p_i}\right)^{e_i} \\
&= \prod_{i=1}^k \left({m_2 \over p_i}\right)^{e_i} = \left({m_2 \over n}\right)
\end{aligned}
$$

2. $$
\begin{aligned}
\left({m_1 m_2 \over n}\right) &= 0 \Leftrightarrow \left({m_1 \over n}\right) = 0 \lor \left({m_2 \over n}\right) = 0 \\
\text{assuming } m_1, m_2 &\bot n: \\
\left({m_1 m_2 \over n}\right)
&= \prod_{i=1}^k \left({m_1 m_2 \over p_i}\right)^{e_i} \\
&= \prod_{i=1}^k \left(\left({m_1 \over p_i}\right) \left({m_2 \over p_i}\right)\right)^{e_i} \\
&= \prod_{i=1}^k \left({m_1 \over p_i}\right)^{e_i} \prod_{i=1}^k \left({m_2 \over p_i}\right)^{e_i} \\
&= \left({m_1 \over n}\right) \left({m_2 \over n}\right) \\[1ex]
\left({m_1 m_2 \over p}\right) &\equiv (m_1 m_2)^{(p-1)/2} \pmod{p} \\
&\equiv m_1^{(p-1)/2} m_2^{(p-1)/2} \pmod{p} \\
&\equiv \left({m_1 \over p}\right) \left({m_2 \over p}\right) \pmod{p}
\end{aligned}
$$

---

### Exercise 3

Using the properties above, and additionally

* $$
\left({2 \over n}\right) = \begin{cases}
1 & \text{if $n \equiv \pm 1 \pmod{8}$}, \\
-1 & \text{if $n \equiv \pm 3 \pmod{8}$} ,
\end{cases}
$$

and

* if <i>$m$</i> and <i>$n$</i> are odd positive integers, then

$$
\left({m \over n}\right) = \begin{cases}
-\left({n \over m}\right) & \text{if $m \equiv n \equiv 3 \pmod{4}$}, \\
\left({n \over m}\right) & \text{otherwise} ,
\end{cases}
$$

write an algorithm to evaluate Jacobi symbols. The algorithm should not do any factoring other than dividing out powers of two.

----

* <i>$\left({0 \over n}\right) = 0$</i>
* <i>$\left({1 \over n}\right) = 1$</i>

def jacobi(a, n):
    v = 1
    while True:
        a %= n # replace a by its remainder modulo n
        if a == 0:
            return 0
        s = 1 if n % 8 in [1, 7] else -1
        while a % 2 == 0:
            a //= 2
            v *= s
        if a == 1:
            return v
        if a % 4 == 3 and n %% 4 == 3:
            v *= -1
        a, n = n, a

---

### Exercise 4

Calculate <i>$\left({7411 \over 9283}\right)$</i>, <i>$\left({20964 \over 1987}\right)$</i> and <i>$\left({1234567 \over 11111111}\right)$</i>.

----

* [Computations](https://nbviewer.jupyter.org/github/jaanos/kirv/blob/master/notebooks/Jacobi.ipynb)