## 24955Re: Infallible prime tests for n<2^64 and n<2^32, C code

Expand Messages
• Mar 17, 2013
--- 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
• Show all 7 messages in this topic