Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • paulunderwooduk
    Mar 17, 2013
    • 0 Attachment
      --- 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