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

Re: new test for primes

Expand Messages
  • djbroadhurst
    ... Bernhard follows BPSW in combining a Fermat and Lucas test. His strong Fermat test has base a, where BPSW have base 2. His strong Lucas test has parameters
    Message 1 of 3 , May 26, 2010
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      "djbroadhurst" <d.broadhurst@...> wrote:

      > Here is rough-and-ready Pari-GP code for Bernhard's test:
      >
      > {bh(n)=local(a=2,t=0);if(n%2&&!issquare(n),
      > while(kronecker(a,n)!=-1,a++);
      > t=Mod(a,n)^((n-1)/2)+1==0;if(t,
      > t=lift(Mod(Mod(1,n)*(1+x),a-x^2)^n)==1-x));t;}

      Bernhard follows BPSW in combining a Fermat and Lucas test.
      His strong Fermat test has base a, where BPSW have base 2.
      His strong Lucas test has parameters (P,Q) = (2,1-a),
      where Selfridge suggested (P,Q) = (1,(1-a)/4) with
      a the first integer in the sequence
      5, -7, 9, -11, 13, -15 ... for which kronecker(a,n) = -1.

      I cannot see any reason why Bernhard's test should be
      any better or any worse than the BPSW test. Heuristically,
      we expect both to have an infinite number of pseudoprimes.
      Heuristically, we expect both to require a huge effort
      to find a single pseudoprime.

      David
    Your message has been successfully submitted and would be delivered to recipients shortly.