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

Re: Baillie-PSW

Expand Messages
  • djbroadhurst
    ... 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? David
    Message 1 of 17 , Sep 2, 2002
    • 0 Attachment
      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?
      David
    • paulunderwooduk
      ... This agrees with: http://www.d.umn.edu/~jgreene/baillie/Baillie-PSW.html but page 18 of:
      Message 2 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 3 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 4 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 5 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.