基于BigInteger实现欧拉准则判断二次剩余时结果异常求助

问题描述 #

尝试用欧拉准则判断(a/p)是否为二次剩余，已知Legendre符号结果只能是1、0或-1，但用Java BigInteger实现后得到的legendreSymbol值为104192021379649097919980，不符合预期。代码严格按照a^((n-1)/2) mod n公式编写，尝试将n分解为素数p和q分别计算时，部分结果仍不符合要求。原代码如下：

public static void main(String args[]) {
        BigInteger p = new BigInteger("329398839493");
        BigInteger q = new BigInteger("500356734809");
        BigInteger n = p.multiply(q);

        
        BigInteger vote = new BigInteger("131187442706502465465362");

        
        if(isQuadraticResidue(vote, n)) System.out.println("Vote 1 = QR");
        else System.out.println("Vote 1 = QNR");
    }
    
    //Quadratic Reciprocity Eulers Criterion
    public static boolean isQuadraticResidue(BigInteger num, BigInteger n) {
        //https://en.wikipedia.org/wiki/Legendre_symbol
        //if the legendreSymbol = 1 then the number is a quadratic residue
        
        BigInteger exponent = n.subtract(BigInteger.ONE).divide(BigInteger.TWO);
        BigInteger legendreSymbol = num.modPow(exponent, n);
        System.out.println(legendreSymbol);

        return legendreSymbol.equals(BigInteger.ONE);
    }

问题原因 #

1. 欧拉准则适用范围错误：欧拉准则仅针对素数模生效，原代码中传入的n是两个素数的乘积（合数），此时对应的是Jacobi符号，直接套用欧拉准则公式会得到不符合预期的结果。
2. 模运算非负性未处理：Java的modPow返回结果为非负值，当理论结果为-1时，实际返回的是n-1（因为-1 ≡ n-1 mod n），原代码未识别这种等价情况。

解决方法 #

要判断num在模n=pq（p、q为素数）下是否为二次剩余，根据中国剩余定理，需同时满足num在模p和模q下均为二次剩余。修正后的代码如下：

public static void main(String args[]) {
    BigInteger p = new BigInteger("329398839493");
    BigInteger q = new BigInteger("500356734809");
    BigInteger n = p.multiply(q);

    BigInteger vote = new BigInteger("131187442706502465465362");

    boolean isQRModP = isQuadraticResiduePrime(vote, p);
    boolean isQRModQ = isQuadraticResiduePrime(vote, q);
    
    // 模n下是二次剩余当且仅当模p和模q下都是二次剩余
    if (isQRModP && isQRModQ) {
        System.out.println("Vote 1 = QR");
    } else {
        System.out.println("Vote 1 = QNR");
    }
}

// 针对素数模的欧拉准则实现
public static boolean isQuadraticResiduePrime(BigInteger num, BigInteger prime) {
    // num是prime的倍数时，Legendre符号为0，属于二次剩余
    if (num.mod(prime).equals(BigInteger.ZERO)) {
        return true;
    }
    
    BigInteger exponent = prime.subtract(BigInteger.ONE).divide(BigInteger.TWO);
    BigInteger result = num.modPow(exponent, prime);
    
    // 结果为1表示是二次剩余，为prime-1（等价于-1）则不是
    return result.equals(BigInteger.ONE);
}

关键说明 #

• 针对素数模单独实现欧拉准则，先判断num是否为素数的倍数，此时直接判定为二次剩余。
• 处理modPow返回prime-1的情况：该值等价于-1 mod prime，对应Legendre符号为-1，说明不是二次剩余。
• 模合数n下的二次剩余判断必须依赖中国剩余定理，需同时满足模每个素因子下都是二次剩余。

内容的提问来源于stack exchange，提问作者HygrowCarpets