Is there a more efficient way of proving a polynomial is primitive?

Question

I have found an impressive Java implementation of a $ℤ2$ Polynomial class in which there seems to be an efficient implementation of a test for reducibility (see isReducible).

I want to extend this to add a test for primitivity (a word is born?). I mean primitive as here where all polynomials of the form $(2^j+1)/p ≡ 1$ for all $0 < j < 2^d$ for a degree $d$ polynomial. I.e. the Polynomial Order is $2^d-1$.

Is there any optimisation I can use to do better than:

// The order of my poly.
BigInteger o = TWO.pow(degree().intValue()).subtract(BigInteger.ONE);
// Check for all 0 < j < o
for (BigInteger j = BigInteger.ONE; j.compareTo(o) < 0; j = j.add(BigInteger.ONE)) {
  // p = (x^j + 1)
  Polynomial p = ONE.shiftLeft(j).plus(ONE);
  if ( p.mod(this).isEmpty() ) {
    return false;
  }
}

For example - $x^6 + x^5 + x^4 + x^2 + 1$ is prime but not primitive because $(x^{21} + 1)/(x^6 + x^5 + x^4 + x^2 + 1) ≠ 1$. This takes an awful long time and it increases in line with $2^n$ for polynomials of degree $n$.

This may seem trivial on the face of it but consider that even at small degrees such as 12 we get $x^{12} + x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x + 1$ is prime but not primitive because it divides $x^{1365} + 1$.