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

Improvement to strong pseudoprimality test

Expand Messages
  • richard_in_reading
    I have tweaked the strong fermat pseudoprimality test with two independent and (in retrospect) completely obvious improvements. For the 419500ish strong base 2
    Message 1 of 1 , Jun 12, 2009
      I have tweaked the strong fermat pseudoprimality test with two independent and (in retrospect) completely obvious improvements.

      For the 419500ish strong base 2 pseudoprimes less than 1e15, one improvement shows that 120936 (28.8%) of them are composite. This improvement requires only a tiny fraction more computation than a normal spsp test.

      The second improvement is independent of the first and involves some data which is often generated anyway in the run-up to doing an spsp test. It also has a small additional computational overhead compared to a normal spsp test. This improvement shows that about 45% of the strong base 2 pseudoprimes less than 1e15 are composite.

      The canny reader can probably work out what I have done from this post as it's so obvious. In the off-chance that someone hasn't already thought of it, I would dearly like to get a paper (or two!) in Math Comp and I was wondering if I adversely affect my chances of getting it published if I post the method in this forum first.

      Cheers guys!

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