public static boolean passEulerCriterion(final BigInteger w) {  WeakReference obj = (WeakReference) knownPrimes.get(w); if (obj != null && w.equals(obj.get())) { if (DEBUG && debuglevel > 4)
public static boolean passEulerCriterion(final BigInteger bn)
  public static boolean passEulerCriterion(final BigInteger w)  {    // first check if it's already a known prime    WeakReference obj = (WeakReference) knownPrimes.get(w);    if (obj != null && w.equals(obj.get()))      {        if (DEBUG && debuglevel > 4)          {            debug("found in known primes");          }        return true;      }    BigInteger w_minus_one = w.subtract(ONE);    BigInteger e = w_minus_one;    // l is the 3 least-significant bits of e    int l = e.and(BigInteger.valueOf(7L)).intValue();    int j = 1; // Where to start in prime array for strong prime tests    BigInteger A;    int k;    if ((l & 7) != 0)      {        e = e.shiftRight(1);        A = TWO.modPow(e, w);        if ((l & 7) == 6)          { // bn == 7 mod 8, expect +1            if (A.bitCount() != 1)              {                if (DEBUG && debuglevel > 4)                  {                    debug(w.toString(16) + " fails Euler criterion #1...");                  }                return false; // Not prime              }            k = 1;          }        else          { // bn == 3 or 5 mod 8, expect -1 == bn-1            A = A.add(ONE);            if (!A.equals(w))              {                if (DEBUG && debuglevel > 4)                  {                    debug(w.toString(16) + " fails Euler criterion #2...");                  }                return false; // Not prime              }            k = 1;            if ((l & 4) != 0)              { // bn == 5 mod 8, make odd for strong tests                e = e.shiftRight(1);                k = 2;              }          }      }    else      { // bn == 1 mod 8, expect 2^((bn-1)/4) == +/-1 mod bn        e = e.shiftRight(2);        A = TWO.modPow(e, w);        if (A.bitCount() == 1)          {            j = 0; // Re-do strong prime test to base 2          }        else          {            A = A.add(ONE);            if (!A.equals(w))              {                if (DEBUG && debuglevel > 4)                  {                    debug(w.toString(16) + " fails Euler criterion #3...");                  }                return false; // Not prime              }          }        // bnMakeOdd(n) = d * 2^s. Replaces n with d and returns s.        k = e.getLowestSetBit();        e = e.shiftRight(k);        k += 2;      }    // It's prime!  Now go on to confirmation tests    // Now, e = (bn-1)/2^k is odd.  k >= 1, and has a given value with    // probability 2^-k, so its expected value is 2.  j = 1 in the usual case    // when the previous test was as good as a strong prime test, but 1/8 of    // the time, j = 0 because the strong prime test to the base 2 needs to    // be re-done.    //for (int i = j; i < SMALL_PRIME_COUNT; i++) {    for (int i = j; i < 13; i++)      { // try only the first 13 primes        A = SMALL_PRIME[i];        A = A.modPow(e, w);        if (A.bitCount() == 1)          {            continue; // Passed this test          }        l = k;        while (true)          {            //            A = A.add(ONE);            //            if (A.equals(w)) { // Was result bn-1?            if (A.equals(w_minus_one))              { // Was result bn-1?                break; // Prime              }            if (--l == 0)              { // Reached end, not -1? luck?                if (DEBUG && debuglevel > 4)                  {                    debug(w.toString(16) + " fails Euler criterion #4...");                  }                return false; // Failed, not prime              }            // This portion is executed, on average, once            //            A = A.subtract(ONE); // Put a back where it was            A = A.modPow(TWO, w);            if (A.bitCount() == 1)              {                if (DEBUG && debuglevel > 4)                  {                    debug(w.toString(16) + " fails Euler criterion #5...");                  }                return false; // Failed, not prime              }          }        // It worked (to the base primes[i])      }    if (DEBUG && debuglevel > 4)      {        debug(w.toString(16) + " passes Euler criterion...");      }    // store it in the known primes weak hash-map    knownPrimes.put(w, new WeakReference(w));    return true;  }