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

Re: Baillie-PSW

Expand Messages
  • paulunderwooduk
    ... This agrees with: http://www.d.umn.edu/~jgreene/baillie/Baillie-PSW.html but page 18 of:
    Message 1 of 17 , Sep 2, 2002
    • 0 Attachment
      --- In primenumbers@y..., "djbroadhurst" <d.broadhurst@o...> wrote:
      > Paul:
      > > if f|x^f-x => f is Baillie-PSW
      > > probable prime (where f=x^3-x-1)
      > As far as I can tell, the Baillie-PSW test
      > was restricted to n = 2 or 3 (mod 5).
      > What do you do in the other 50% of the cases?
      This agrees with:
      http://www.d.umn.edu/~jgreene/baillie/Baillie-PSW.html
      but page 18 of:
      http://www.hipilib.de/prime/primality-tests-on-commutator-curves.ps.gz
      tells a different story.
      Paul
    • djbroadhurst
      Paul: What do you say about n=41*61*101=1 mod 5 ? By me, 2^n=2 mod n and lucasU(1,-1,n-1)=0 mod n. So it is 2-PrP (also 2-sPrP, I believe) and is a Fibonacci
      Message 2 of 17 , Sep 2, 2002
      • 0 Attachment
        Paul: What do you say about n=41*61*101=1 mod 5 ?
        By me, 2^n=2 mod n
        and lucasU(1,-1,n-1)=0 mod n.
        So it is 2-PrP (also 2-sPrP, I believe)
        and is a Fibonacci pseudoprime, according
        to Crandall-Pomerance book.
        Baillie-PSW exclude it, because n=1 mod 5.
        What would you do with it, please?
        David (at speed, error prone!)
      • paulunderwooduk
        ... Oh! I am going to use 5 rounds of Miller Rabin instead! I am way out of my depth with Lucas sequences. At least with the M-R there less that 1 in 1024
        Message 3 of 17 , Sep 2, 2002
        • 0 Attachment
          --- In primenumbers@y..., "djbroadhurst" <d.broadhurst@o...> wrote:
          > Paul: What do you say about n=41*61*101=1 mod 5 ?
          > By me, 2^n=2 mod n
          > and lucasU(1,-1,n-1)=0 mod n.
          > So it is 2-PrP (also 2-sPrP, I believe)
          > and is a Fibonacci pseudoprime, according
          > to Crandall-Pomerance book.
          > Baillie-PSW exclude it, because n=1 mod 5.
          > What would you do with it, please?
          > David (at speed, error prone!)
          Oh! I am going to use 5 rounds of Miller Rabin instead!
          I am way out of my depth with Lucas sequences.
          At least with the M-R there less that 1 in 1024 chance of missing the
          first counterexample.
          Thanks for you help!
          paul
        • djbroadhurst
          Oh dear, Paul, it seems that 252601=41*61*101 turned you off Fermat-Lucas when n^2=1 mod 5. FYI, I shall post 49,285 such double-pseudoprimes (I think, but no
          Message 4 of 17 , Sep 2, 2002
          • 0 Attachment
            Oh dear, Paul, it seems that 252601=41*61*101
            turned you off Fermat-Lucas when n^2=1 mod 5.

            FYI, I shall post 49,285 such double-pseudoprimes
            (I think, but no checking has been done!)
            in the files area.

            I hope someone will check that these
            are all 2-sPrP and Fibonacci-PrP.

            I was amazed by how prolific they appear to be.

            None is congruent to 2 or 3 (mod 5),
            so no $620 cigar, of course!

            [goes to post file..]

            OK .... file is (I hope)

            http://groups.yahoo.com/group/primenumbers/files/pseudo/52paul.txt

            > 2-sPrP Fibonacci pseudoprimes to 52 bits

            Thanks to Jason, for the 2-sPrP part.

            Can someone check this bestiary, please?

            David (about to disappear on another trip)
          Your message has been successfully submitted and would be delivered to recipients shortly.