Mathematics

• Calculus is the mathematical study of change. [1]

Include Analysis...

• Algebra is the study of operations and their application to solving equations.

Include Fields, Rings, Equations...

• Number theory is the study of integers

Include prime numbers,rational numbers, algebraic numbers...

• Arithmetic is the older term for number theory, and now refers to the study of elementary operations.[2]
• Geometry is the study of shape,

Resources

• Linear Algebra Done Right, free book on linear algebra course.
• Linear Algebra Done Wrong, another free book with more rigorous approach.

Modular arithmetics

Find modular square roots

Let p a prime, and 1<=a<P, the problem is to find x s.t. x*x = a mod p.

Existence

• Excluding the case a = 0 (that has 0 as solution), the problem has a solution if the Legendre symbol for a and p is 1, ie. a^((p-1)/2) = 1 (mod p).

Solution

• https://www.rieselprime.de/ziki/Modular_square_root

• If p=2, trivial (x=a).
• If p=3 mod 4, x = ±a^((p+1)/4) mod p. Not all a have a sqrt. If a doesn't have (ie. x^2 != a), then in fact -a does have and we have x^2 == -a (this is because if a^((p-1)/2) is -1, then (-a)^((p-1)/2) is 1 because (p-1)/2 is odd, and computed value for x is the same for a or -a).
• If p=1 mod 8, a very smart method is given:

def modsqrt(a,p):
    assert(p%8 == 5)
    v = pow(2*a,(p-5)//8,p)
    i = 2*a*v*v % p           # This is sqrt of -1
    return a*v*(i-1) % p

In the method above, we can check that r^2 = a^2*v^2*(i^2 - 2*i + 1) = -2*i*a^2*v^2 = -i^2*a = a.

Again, not all integers have a square root.

• If p=3 mod 8, uses Shanks method (a Newton-Raphson like method).

• More on Tonelli-Shanks algorithm: https://mathoverflow.net/questions/52081/is-there-an-efficient-algorithm-for-finding-a-square-root-modulo-a-prime-power, https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm
• https://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python

• The Tonelli-Shanks algorithm in python.

def modular_sqrt(a, p):
    """ Find a quadratic residue (mod p) of 'a'. p
        must be an odd prime.

        Solve the congruence of the form:
            x^2 = a (mod p)
        And returns x. Note that p - x is also a root.

        0 is returned is no square root exists for
        these a and p.

        The Tonelli-Shanks algorithm is used (except
        for some simple cases in which the solution
        is known from an identity). This algorithm
        runs in polynomial time (unless the
        generalized Riemann hypothesis is false).
    """
    # Simple cases
    #
    if legendre_symbol(a, p) != 1:
        return 0
    elif a == 0:
        return 0
    elif p == 2:
        return 0
    elif p % 4 == 3:
        return pow(a, (p + 1) / 4, p)

    # Partition p-1 to s * 2^e for an odd s (i.e.
    # reduce all the powers of 2 from p-1)
    #
    s = p - 1
    e = 0
    while s % 2 == 0:
        s /= 2
        e += 1

    # Find some 'n' with a legendre symbol n|p = -1.
    # Shouldn't take long.
    #
    n = 2
    while legendre_symbol(n, p) != -1:
        n += 1

    # Here be dragons!
    # Read the paper "Square roots from 1; 24, 51,
    # 10 to Dan Shanks" by Ezra Brown for more
    # information
    #

    # x is a guess of the square root that gets better
    # with each iteration.
    # b is the "fudge factor" - by how much we're off
    # with the guess. The invariant x^2 = ab (mod p)
    # is maintained throughout the loop.
    # g is used for successive powers of n to update
    # both a and b
    # r is the exponent - decreases with each update
    #
    x = pow(a, (s + 1) / 2, p)
    b = pow(a, s, p)
    g = pow(n, s, p)
    r = e

    while True:
        t = b
        m = 0
        for m in xrange(r):
            if t == 1:
                break
            t = pow(t, 2, p)

        if m == 0:
            return x

        gs = pow(g, 2 ** (r - m - 1), p)
        g = (gs * gs) % p
        x = (x * gs) % p
        b = (b * g) % p
        r = m


def legendre_symbol(a, p):
    """ Compute the Legendre symbol a|p using
        Euler's criterion. p is a prime, a is
        relatively prime to p (if p divides
        a, then a|p = 0)

        Returns 1 if a has a square root modulo
        p, -1 otherwise.
    """
    ls = pow(a, (p - 1) / 2, p)
    return -1 if ls == p - 1 else ls

References

• Wikipedia
• Khan Academy