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

Re: [PrimeNumbers] Re: Baillie-PSW

Expand Messages
  • Phil Carmody
    ... I nearly jumped on 0 ); ... until I noticed it had a do before it. (I m a } while man). The following looks dodgy:
    Message 1 of 17 , Sep 2, 2002
      --- paulunderwooduk <paulunderwood@...> wrote:
      > Dear members,
      >
      > I have uploaded a very quick gmp program to see if f|x^f-x => f is
      > Baillie-PSW probable prime (where f=x^3-x-1). Please check it is a
      > valid program.
      >
      > http://groups.yahoo.com/group/primeform/files/Probable%20Primes/cubic.c

      I nearly jumped on
      <<<
      while ( mpz_kronecker( d, f ) > 0 );
      >>>
      until I noticed it had a 'do' before it. (I'm a "} while" man).


      The following looks dodgy:

      int sign;

      sign = -1;
      do {
      mpz_add_ui( t, t, 2 );
      if ( sign == 1 ) sign = -1; else sign = 1;
      mpz_mul_ui( d, t, sign ); }
      while ( mpz_kronecker( d, f ) > 0 );


      'sign' isn't a '_ui', so I'm guessing that you're multiplying t by (2^32-1),
      rather than by -1 half of the time.


      Phil


      =====
      "The hottest places in Hell are reserved for those who, in
      times of moral crisis, preserved their neutrality."
      -- John F. Kennedy, 24 June 1963, claiming to quote Dante,
      to whom this has been incorrectly attributed ever since.

      __________________________________________________
      Do You Yahoo!?
      Yahoo! Finance - Get real-time stock quotes
      http://finance.yahoo.com
    • 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 2 of 17 , Sep 2, 2002
        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 3 of 17 , Sep 2, 2002
          --- 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 4 of 17 , Sep 2, 2002
            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 5 of 17 , Sep 2, 2002
              --- 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 6 of 17 , Sep 2, 2002
                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.