> For the complete documentation index, see [llms.txt](https://security.andreasbreum.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://security.andreasbreum.com/cryptology/cryptohack/course-modular-arithmetic/mathematics-modular-math.md).

# Mathematics - Modular Math

## Quadratic Residues

*"We say that an integer `x` is a Quadratic Residue if there exists an `a` such that `a^2 = x mod p`. If there is no such solution, then the integer is a Quadratic Non-Residue.*

*If `a^2 = x` then `(-a)^2 = x`. So if `x` is a quadratic residue in some finite field, then there are always two solutions for `a`.*\
\
*`p = 29`*\
*`ints = [14, 6, 11]`"*

We can simply loop through all value for `a` from `0` to `p-1` and see if a solution exists

{% code overflow="wrap" lineNumbers="true" %}

```python
#!/usr/bin/env python3
p = 29
ints = [14, 6, 11]

for a in range(p):
    t = pow(a, 2, p)
    if t in ints:
        print(str(t) + " is quadratic Residue with a = " + str(a))
```

{% endcode %}

## Legendre Symbol

*"Before looking at Legendre's symbol, let's take a brief detour to see an interesting property of quadratic (non-)residues.*

*`Quadratic Residue * Quadratic Residue = Quadratic Residue`* 

*`Quadratic Residue * Quadratic Non-residue = Quadratic Non-residue`* 

*`Quadratic Non-residue * Quadratic Non-residue = Quadratic Residue`*

\
*Legendre's Symbol: `(a / p) ≡ a(p-1)/2 mod p` obeys:*\
*(a / p) = 1 if a is a quadratic residue and a ≢ 0 mod p*\
*(a / p) = -1 if a is a quadratic non-residue mod p*\
*(a / p) = 0 if a ≡ 0 mod p*

*Which means given any integer `a`, calculating `pow(a,(p-1)//2,p)` is enough to determine if `a` is a quadratic residue.*

*Now for the flag. Given the following 1024 bit prime and 10 integers, find the quadratic residue and then calculate its square root; the square root is your flag. Of the two possible roots, submit the larger one as your answer.*

*So Legendre's symbol tells us which integer is a quadratic residue, but how do we find the square root?! The prime supplied obeys `p = 3 mod 4`, which allows us easily compute the square root. The answer is online, but you can figure it out yourself if you think about Fermat's little theorem."*

When `p = 3 mod 4` then `a^((p+1)/4) mod p` is a square root of `a`

So, first we find the quadratic residue and then the square root.

{% code overflow="wrap" lineNumbers="true" %}

```python
#!/usr/bin/env python3

p = 1015240... #From the text file
ints = [2508184120...0985105257601565] #From the text file

for a in ints:
    if pow(a,(p-1)//2,p) == 1:
        print(pow(a,(p+1)//4, p))
```

{% endcode %}

## Modular Square Root

*"In Legendre Symbol we introduced a fast way to determine whether a number is a square root modulo a prime. We can go further: there are algorithms for efficiently calculating such roots. The best one in practice is called Tonelli-Shanks, which gets its funny name from the fact that it was first described by an Italian in the 19th century and rediscovered independently by Daniel Shanks in the 1970s.*\
\
*All primes that aren't 2 are of the form `p ≡ 1 mod 4` or `p ≡ 3 mod 4`, since all odd numbers obey these congruences. As the previous challenge hinted, in the `p ≡ 3 mod 4` case, a really simple formula for computing square roots can be* [*derived*](https://crypto.stackexchange.com/a/20994) *directly from Fermat's little theorem. That leaves us still with the `p ≡ 1 mod 4` case, so a more general algorithm is required.*\
\
*In a congruence of the form `r2 ≡ a mod p`, Tonelli-Shanks calculates `r`.*\
\
*Tonelli-Shanks doesn't work for composite (non-prime) moduli. Finding square roots modulo composites is computationally equivalent to integer factorization - that is, it's a hard problem.*\
\
*The main use-case for this algorithm is finding elliptic curve co-ordinates. Its operation is somewhat complex so we're not going to discuss the details, however, implementations are easy to find and Sage has one built-in.*\
\
*Find the square root of `a` modulo the 2048-bit prime `p`. Give the smaller of the two roots as your answer."*

The following implementation does the trick.

The function `legendre_symbol(a, p)` computes the Legendre symbol of `a` modulo `p`, using Euler's criterion. The function `tonelli_shanks(n, p)` finds a quadratic residue of `n` modulo `p`, assuming that `p` is prime. If `n` is not a quadratic residue modulo `p`, the function returns `None`.

## Chinese Remainder Theorem

*"The Chinese Remainder Theorem gives a unique solution to a set of linear congruences if their moduli are coprime.*\
\
*This means, that given a set of arbitrary integers `ai`, and pairwise coprime integers `ni`, such that the following linear congruences hold:*\
\
*Note "pairwise coprime integers" means that if we have a set of integers `{n1, n2, ..., ni}`, all pairs of integers selected from the set are coprime: `gcd(ni, nj) = 1`.*\
\
*x ≡ a1 mod n1*\
*x ≡ a2 mod n2*\
*...*\
*x ≡ an mod nn*\
\
*There is a unique solution `x ≡ a mod N` where `N = n1 * n2 * ... * nn`.*\
\
*In cryptography, we commonly use the Chinese Remainder Theorem to help us reduce a problem of very large integers into a set of several, easier problems.*\
\
*Given the following set of linear congruences:*\
\
*x ≡ 2 mod 5*\
*x ≡ 3 mod 11*\
*x ≡ 5 mod 17*\
\
*Find the integer `a` such that `x ≡ a mod 935`"*

This script will output x given a list of a's and n's.

`n = [5, 11, 17]` 

`a = [2, 3, 5]`

The script will output a number smaller than 935, which means that `x` is a solution for `a`

{% code overflow="wrap" lineNumbers="true" %}

```python
def chinese_remainder(n, a):
    # Compute the product of the moduli
    prod = 1
    for ni in n:
        prod *= ni

    # Compute the sum of the terms
    x = 0
    for ni, ai in zip(n, a):
        pi = prod // ni  # compute the product of the moduli except ni
        xi = pow(pi, -1, ni)  # compute the modular inverse of pi
        x += ai * xi * pi  # add the product to the sum

    # Return the solution modulo the product of the moduli
    return x % prod

# Test the function
n = [5, 11, 17]
a = [2, 3, 5]
print(chinese_remainder(n, a))
```

{% endcode %}

Also, I've created a solution that explains the steps a bit more clearly.

{% code overflow="wrap" lineNumbers="true" %}

```python
#!/usr/bin/env python3
import math

# Define the system of congruences
m = [5, 11, 17]
a = [2, 3, 5]

# Print the system of congruences
print("We can use the Chinese Remainder Theorem to find a unique solution X such that:")
for i in range(len(m)):
    print(f"x = {a[i]} mod {m[i]}")
print()

# Find M
M = math.prod(m)
print("First we find M, which is the product of all the moduli:")
print(f"M = {M}")
print()

# Calculate Mi
Mi = [M // mi for mi in m]
print("Next we calculate a list of Mi = M/mi for i in 1..r:")
for i in range(len(m)):
    print(f"M_{i+1} = {M} / {m[i]} = {Mi[i]}")
print()

# Calculate yi
y = [pow(Mi[i], -1, m[i]) for i in range(len(m))]
print("Then we calculate a list of yi = Mi^-1 mod mi for i in 1..r:")
for i in range(len(m)):
    print(f"y_{i+1} = {Mi[i]}^-1 mod {m[i]} = {y[i]}")
print()

# Calculate x
x = sum([a[i]*Mi[i]*y[i] for i in range(len(m))]) % M
print("Finally we can compute our x = sum of ai*Mi*yi mod M for i in 1..r:")
print(f"x = {x}")
print()

# Print the final equation
print("Thus we get the final equation as such:")
print(f"x = {x} mod {M} = {x} mod {math.prod(m)}")
```

{% endcode %}