How can I make this primality test algorithm faster?
Avoid dealing with BigDecimals at all costs - they are slow. I changed the formula to work with "twice the number", so my s is actually 2*s. Further keep the numbers in the loop small by "modding" the intermediate results, too. Finally I tried to simplify the syntax and the initial conditions for s a little bit.

import java.math.BigInteger;

public class WPT {

    private final static BigInteger _1 = BigInteger.ONE;
    private final static BigInteger _2 = _(2);
    private final static BigInteger _4 = _(4);

    public static BigInteger _(long n) {
        return BigInteger.valueOf(n);
    }

    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);

        BigInteger m = _(n);

        BigInteger s =
                (m.mod(_(4)).equals(_1)) ? _(3) :
                        (m.mod(_(6)).equals(_1)) ? _(11) :
                                (m.mod(_(12)).equals(_(11)) &amp;&amp;
                                        (m.mod(_(10)).equals(_1)) ||
                                        m.mod(_(10)).equals(_(9))) ? _(27) : _(33);
        BigInteger r = s;

        BigInteger W = _2.pow(n).add(_1).divide(_(3));

        int k = (n - 1) / 2;

        for (int i = 0; i &lt; k; i++) {
            BigInteger s2 = s.modPow(_2, W);
            BigInteger s4 = s2.modPow(_2, W);
            s = s4.subtract(s2.multiply(_4)).add(_2).mod(W);
        }

        System.out.println(s.equals(r) ? "prime" : "composite");
    }
}