--- In

primenumbers@yahoogroups.com, "WarrenS" <warren.wds@...> wrote:

> } //Step 4: Lehmer test main computation:

> A0 = 2; A1 = C;

> while(j>=0){

> es = e>>j;

> if(es&1){ //unlike for modular exponentiation, both the 0 and 1 cases take same time

> A0 = mulmod64(A0, A1, n); A0 = submod64(A0, C, n);

> A1 = mulmod64(A1, A1, n); A1 = submod64(A1, 2ULL, n);

> }else{ //hence any attempt (like for mod.exp.) to go to, e.g, radix-8, is pointless.

> A1 = mulmod64(A0, A1, n); A1 = submod64(A1, C, n);

> A0 = mulmod64(A0, A0, n); A0 = submod64(A0, 2ULL, n);

> }

> j--;

> }

> if( mulmod64(C, A0, n) != mulmod64(2, A1, n) ){ return(FALSE); }

> return(TRUE); //In place of this line, it also is

> //possible to add more code here which takes almost no extra time but

> //would improve the truth rate. But for 64-bit purposes we already get zero failures

> //so to hell with it.

> }

>

This is almost the test 3.6.7 from C&P, but I can't figure out how you are choosing D=P^2-4*Q. It could be similar to Selfridge's choice or Pomerance's choice or Pari-gp's ispsedoprime() test,

Paul