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