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

Re: Comparison of three tests - additional information

Expand Messages
  • djbroadhurst
    ... Pari-GP s ispseudoprime implements BPSW as follows: 1) trial division: if a factor, then composite, else 2) Fermat test: if fails, then composite, else
    Message 1 of 4 , Jan 23, 2011
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      "Brian" <btball@...> wrote:

      > I get identical results with BPSW & (Frobenius using method B*)
      > 115,788 nanoseconds (which also means that my system, using
      > python is about 100 times slower than David's using Pari/GP).

      Pari-GP's "ispseudoprime" implements BPSW as follows:
      1) trial division: if a factor, then composite, else
      2) Fermat test: if fails, then composite, else
      3) Lucas test: if fails then composite, else PRP.

      The timing:

      > {for(n=1,10,for(k=1,10^6,ispseudoprime(2^63+random(2^63)));
      > print1(gettime" "));}
      > 1198 1209 1222 1224 1219 1218 1220 1226 1226 1220

      benefits for the fact that only a fraction of the targets
      got to (2) and only a fraction of those to (3).

      Do you have the same logic?

      Best regards,

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