在给定 RSA n=p*q 的情况下使用 BigIntegers 的欧拉准则

Question

我正在尝试使用欧拉准则找出 (a/p) 是否是二次余数

我知道使用此方法应该只存在 3 个答案：1、0 或 -1

但是，当我使用 BigIntegers 在 Java 中实现这一点时，我得到了不同的结果。当我运行下面的代码时，我的 legendreSymbol 等于 104192021379649097919980 ，这不可能是正确的。我看过很多教程，所有的表达欧拉准则都是 a^((n-1)/2) mod n，这正是我在代码中计算它的方式。

我试图在网上寻找任何类似的实现，但我根本找不到。

我厌倦了将 n 分解为 p 和 q 并尝试对这些值使用欧拉准则，但其中一些结果仍然不是 0、1 或 -1

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);
    }

Answer 1

对于您所说的欧拉准则 a^((n-1)/2) mod n，n 必须是奇素数且与 n 互质。在您的代码中，您为 n 传递了 p*q ，这显然不是奇素数