Factorization Techniques - Introduction to Cryptography with Java Applets - page 224

FIGURE 12.1

f(x)=x^2 - 300

300

200

100

r 0

-30 -20 -10 10 20 30

r 1

-100

-200

-300

placed it in the BigIntegerMath class. It makes use of the BigDecimal class, which allows
us to compute with arbitrarily large numbers using arbitrary precision.

public static BigInteger sqrt(BigInteger m) {
//Uses the Newton method to find largest integer whose square does not exceed m
//We search for a zero of f(x)=x^2-p ==> note that derivative f'(x)=2x

int diff=m.compareTo(ZERO);
//Throw an exception for negative arguments
if (diff<0) throw new IllegalArgumentException
(“Cannot compute square root of a negative integer!”);
//Return 0 in case m is 0
if (diff==0) return BigInteger.valueOf(0);

BigDecimal two=new BigDecimal(TWO);
//Convert the parameter to a BigDecimal
BigDecimal n=new BigDecimal(m);

//Begin with an initial guess-the square root will be half the size of m
//Make a byte array at least that long, & set bits in the high order byte
byte[] barray=new byte[m.bitLength()/16+1];
barray[0]=(byte)255;
//This is the first guess-it will be too high
BigDecimal r=new BigDecimal(new BigInteger(1,barray));