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

modulus must be a product of distinct primes of the form 4 + 3. If we are going to deal with

truly large integers, then we must take many things into consideration:
• We cannot send in the modulus

k

n as a parameter directly; rather, we must send in the

prime factorization n = pq . This is because factoring n when n has large prime factors is

an intractable problem. (We will discuss this more later.)
• We must test each factor of first to see if each one is a probable prime, using the isProb-

ablePrime() method of the BigInteger class. (This method of determining primality does
not involve attempted factoring and will execute quickly.) If the factor is probably prime,
we must also test whether it is congruent to 3 modulo 4. If either is not the case, our
method is unusable and we must throw an exception.
• We must check that no factor of the modulus

n

n is repeated; that is, the two primes p and

q must be unique if we are to use the Chinese Remainder Theorem to produce the solu-

tions. (CRT requires that the moduli be pairwise relatively prime; if any two moduli are
equal this condition is certainly violated.) If , we throw an exception.

• We must check the solutions we obtain. It is possible the quadratic congruence we are try-
ing to solve has, in fact, no solutions! Thus, any values we obtain must be checked against
the original congruence. If any solution fails to check, we must again throw an exception.
The method as we have outlined has many rules to follow, but if we take the proper pre-
cautions, this method can produce very satisfactory results. The code follows:

p = q

import java.math.BigInteger;
import java.security.SecureRandom;
public class BigIntegerMath {
//Define zero as a BigInteger; this is handy for comparisons
static final BigInteger ZERO=new BigInteger(“0”);
static final BigInteger ONE=new BigInteger(“1”);
static final BigInteger TWO=new BigInteger(“2”);
static final BigInteger THREE=new BigInteger(“3”);
static final BigInteger FOUR=new BigInteger(“4”);

//Other methods......

//Solves quadratic congruences ax^2+bx+c congruent to 0 mod n=pq
//Returns four solutions when they exist
public static BigInteger[] solveQuadratic(BigInteger a, BigInteger b, BigInteger

c,

BigInteger p, BigInteger q, int primeTolerance) {
//Check that the factors of the modulus are distinct
if (p.equals(q))
throw new IllegalArgumentException(“The modulus factors are not unique!”);
//Check that the factors are congruent to 3 modulo 4
BigInteger n=p.multiply(q);
if (!lnr(p.mod(FOUR),n).equals(THREE))