Timing attack on SquareRoot.answer. It uses the timing attack to find the square, then hunts around the root.

Main.java

import square.SquareRoot;

import java.math.BigInteger;
import java.util.Date;

public class Main {

    public static long timeit(BigInteger n) {
        long begin = System.nanoTime();
        for (int i=0; i < 200; i++) {
            SquareRoot.answer(n);
        }
        long end = System.nanoTime();
        return (end - begin);
    }

    public static BigInteger findSqrt(BigInteger n) {
        BigInteger potentialRoot = new BigInteger("2");
        if (n.compareTo(potentialRoot) <= 0) {
            if (n.equals(BigInteger.ZERO)) {
                return n;
            } else {
                return BigInteger.ONE;
            }
        }
        potentialRoot = n.divide(potentialRoot);
        while (true) {
            BigInteger npotentialRoot = n.divide(potentialRoot).add(potentialRoot).shiftRight(1);
            if (potentialRoot.subtract(npotentialRoot).abs().compareTo(BigInteger.TEN) < 0) {
                for (int x = 10; x > -11; x--) {
                    BigInteger tst = potentialRoot.add(new BigInteger("" + x));
                    BigInteger tstP1 = tst.add(BigInteger.ONE);
                    if (tst.multiply(tst).compareTo(n) != tstP1.multiply(tstP1).compareTo(n)) {
                        return tst;
                    }
                }
            }
            potentialRoot = npotentialRoot;
        }
    }

    public static boolean isTooHigh(long tooBigTime, BigInteger mid) {
        long minTime = Long.MAX_VALUE;
        long midTime = 0;
        for (int i=1; i < 40; i++) {
            long t = timeit(mid);
            minTime = Math.min(midTime, t);
            midTime += t;
        }
        midTime /= 40;
        if ((midTime - minTime > tooBigTime / 4) || (midTime > 4 * tooBigTime && midTime < 7 * tooBigTime)) {
            // System.out.print("T");
            return isTooHigh(tooBigTime, mid);
        }
        return midTime <= 4 * tooBigTime;
    }

    public static void main(String[] args) throws InterruptedException {
        for (int i=1; i < 257; i++) {
            SquareRoot.answer(new BigInteger("" + i));
        }
        BigInteger high = new BigInteger("2").pow(20002);
        for (int i=1; i < 1000; i++) {
            timeit(high); // warm up jit
        }
        long tooBigTime = 0;
        while (true) {
            long minBigTime = Long.MAX_VALUE;
            tooBigTime = 0;
            for (int i=1; i < 10; i++) {
                long t = timeit(high);
                tooBigTime += t;
                minBigTime = Math.min(minBigTime, t);
            }
            tooBigTime /= 10;
            if (tooBigTime - minBigTime < tooBigTime / 8)
                break;
            System.out.println(tooBigTime + " " + minBigTime);
            for (int i=1; i < 1000; i++) {
                timeit(high); // warm up jit
            }
        }
        BigInteger low = new BigInteger("256");
        BigInteger hundred = new BigInteger("100");
        int ticklen = 0;
        while (high.compareTo(low.add(BigInteger.ONE)) > 0) {
            int spotlen = high.subtract(low).toString().length() / 100;
            if (spotlen != ticklen) {
                System.out.println(spotlen + " " + new Date());
                ticklen = spotlen;
            }
            if (high.subtract(low).compareTo(hundred) > 0) {
                BigInteger step = high.subtract(low).divide(BigInteger.TEN);
                BigInteger guess = high.subtract(step);
                while (guess.compareTo(low) > 0) {
                    if (isTooHigh(tooBigTime, guess) || isTooHigh(tooBigTime, guess.subtract(BigInteger.ONE))) {
                        high = guess;
                        guess = high.subtract(step);
                    } else {
                        low = guess;
                    }
                }
            } else {
                BigInteger mid = high.add(low).shiftRight(1);
                if (isTooHigh(tooBigTime, mid)) {
                    high = mid;
                } else {
                    low = mid;
                }
            }
        }
        BigInteger guess = findSqrt(low);
        for (int x = -100; x < 100; x++) {
            SquareRoot.answer(guess.add(new BigInteger("" + x)));
        }
    }
}