平方剩余代码实现-526互联

def quadratic_residue_and_square_root(a, p):
    """
    计算模 p 下的平方剩余和平方根
    返回一个元组 (是否为平方剩余, 平方根1, 平方根2)
    """
    if not is_quadratic_residue(a, p):
        return (False, None, None)

    # 计算平方根
    x = pow(a, (p + 1) // 4, p)
    return (True, x, p - x)

def is_quadratic_residue(a, p):
    """
    判断 a 是否是模 p 的平方剩余
    """
    return pow(a, (p - 1) // 2, p) == 1

# 例子：计算模 17 下的平方剩余和平方根
p = 17

for a in range(p):
    result, root1, root2 = quadratic_residue_and_square_root(a, p)
    if result:
        print(f"模 {p} 下 {a} 的平方剩余是 True，平方根为 {root1} 和 {root2}")
    else:
        print(f"模 {p} 下 {a} 的平方剩余是 False")