Making quadratic residue checks optional in sqrt_mod_prime

[JanisErdmanis]

The sort_mod_prime function includes an is_quadratic_residue check. This is good from a correctness point of view; however, in some applications, one already checks that input is a quadratic residue as a part of a larger algorithm; hence, having it there makes it redundant. Furthermore, when performance is of concern, the is_quadratic_residue check can slow things down significantly. Also mod function is not free with BigInt hence I propose adding a flag skip_checks:

function sqrt_mod_prime(a::Integer, p::Integer; skip_checks::Bool=false)
  
    if !skip_checks
        a = mod(a, p)
        is_quadratic_residue(a, p) || throw("$a is not a quadratic residue mod $p.")
    end

    if p % 2 == 0
        return a

    elseif p % 4 == 3
        return powermod(a, div(p + 1, 4), p)

    elseif p % 8 == 5
        d = powermod(a, div(p - 1, 4), p)

        if d == 1
            r = powermod(a, div(p + 3, 8), p)
        elseif d == p - 1
            r = mod(2 * a * powermod(4 * a, div(p - 5, 8), p), p)
        end

        return r

    # If p-1 is of the form 2^k*s for large k, use tonelli-shanks.
    # Here k is large if k > 100
    elseif mod(p - 1, 1267650600228229401496703205376) == 0
        return tonelli_shanks(a, p)

    # depends on size of k
    else
        return hoc_sqrt(a, p)
    end
end