Fermat primality test
I still can't quite figure out the way to this algorithm =/. But, from the Java point of view, you can gain 9-10% by changing your loop to:

for (int i = 1; i &lt;= c; i ++) {
    BigInteger temp = s.pow(2);
    s = temp.pow(2).subtract(BigInteger.valueOf(4).multiply(temp)).add(BigInteger.valueOf(2)).mod(F);
}


...because the cached value can be used twice there.

Otherwise, the code is hard to read. It's not self explanatory nor commented and could be written in a better way - for a human to read, at least. But none of those changes would affect performance in any way.

EDIT: Additional 17% thanks to @Landei in comments.

for (int i = 1; i &lt;= c; i ++) {
    BigInteger temp = s.modPow(BigInteger.valueOf(2), F);
    s = temp.pow(2).subtract(BigInteger.valueOf(4).multiply(temp)).add(BigInteger.valueOf(2));
}
s = s.mod(F);


That takes advantage of modPow() method which can do pow().mod() in one step without much additional overhead. Since the mod is not necessary to have every time, it is enough to do it in temp (that actually propagates twice into the resulting expression) and enjoy the substantial speedup. You need to add one proper mod after the loop is done, though.