Cryptography and Computer Security

« nazaj

Cryptography and computer security - Tutorial 24.11.2020

---

Jacobi symbols

Exercise 1

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

---

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

---

Exercise 2

For an integer $a$ and an odd positive integer $n = \prod_{i=1}^k p_i^{e_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 $m_1 \equiv m_2 \pmod{n}$, 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 $a \in \mathbb{Z}^*_p$:

• $a^{p-1} \equiv 1 \pmod{p}$
• $a^{(p-1)/2} \equiv \left({a \over p}\right) \pmod{p}$

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 $m$ and $n$ 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.

---

• $\left({0 \over n}\right) = 0$
• $\left({1 \over n}\right) = 1$

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 $\left({7411 \over 9283}\right)$, $\left({20964 \over 1987}\right)$ and $\left({1234567 \over 11111111}\right)$.

---

• Computations

Ta stran je odprtokodna. Izboljšaj to stran.

Ta zapisek je dostopen tudi na HackMD.