Quadratic Congruences - Introduction to Cryptography with Java Applets - page 177

throw new IllegalArgumentException(p+” is not of form 4k+3!”);
if (!lnr(q.mod(FOUR),n).equals(THREE))
throw new IllegalArgumentException(q+” is not of form 4k+3!”);
//Check that the factors of the modulus are prime
if (!p.isProbablePrime(primeTolerance))
throw new IllegalArgumentException(p+” is not prime!”);
if (!q.isProbablePrime(primeTolerance))
throw new IllegalArgumentException(q+” is not prime!”);
//Create the array of solutions
BigInteger[] result=new BigInteger[4];
//Start forming the terms
BigInteger aInv=a.modInverse(n);
BigInteger pInv=p.modInverse(q);
BigInteger qInv=q.modInverse(p);
BigInteger twoInv=TWO.modInverse(n);
BigInteger term1=
aInv.multiply(twoInv.multiply(b).modPow(TWO,n).multiply(aInv).subtract(c));
BigInteger term2=twoInv.multiply(aInv).multiply(b);
BigInteger t1=
lnr(term1.modPow(p.add(ONE).divide(FOUR),n)
.subtract(term2).multiply(q).multiply(qInv),n);
BigInteger t2=
lnr(term1.modPow(q.add(ONE).divide(FOUR),n)
.subtract(term2).multiply(p).multiply(pInv),n);
BigInteger t3=
lnr(term1.modPow(p.add(ONE).divide(FOUR),n).negate()
.subtract(term2).multiply(q).multiply(qInv),n);
BigInteger t4=
lnr(term1.modPow(q.add(ONE).divide(FOUR),n).negate()
.subtract(term2).multiply(p).multiply(pInv),n);
//Form the solutions
result[0]=lnr(t1.add(t2),n);
result[1]=lnr(t1.add(t4),n);
result[2]=lnr(t3.add(t2),n);
result[3]=lnr(t3.add(t4),n);
//Check the solutions; if any are bad, throw an exception
BigInteger x;
for (int i=0;i<4;i++) {
x=result[i];
if (!lnr(a.multiply(x.multiply(x)).add(b.multiply(x)).add(c),n).
equals(ZERO))
throw new IllegalArgumentException(“Solution x=”+x+” does not check!”);
}
return result;
}
}