def search_non_residue(p):
    """Find a non residue of p between 2 and p
    
    Args:
        p: a prime number
        
    Returns:
        a integer that is not a quadratic residue of p
        or -1 if no such number exists 

    """
    for z in range(2, p):
        if pow(z, (p - 1) // 2, p) == p - 1:
            return z
    return -1