Re: [math-fun] Totally different/new simple probable-prime test... shows pseudoprimes are easy to factor

regarding the last point mentioned below, page 1402 of the baillie-wagstaff "lucas pseudoprimes" paper mentions this: if n is a psp base a, but not a strong psp base a, then we can factor n in the process doing the psp test base a. bob --- On Thu, 19 Jan 2012 11:23:48 -0500, Warren Smith wrote: .....

This also tells us something that is rather remarkable which I have not seen before: REMARKABLE FACT: Pseudoprimes (i.e. hard cases for our probable-prime test) are easy to factor.

One has to wonder what applications this may have...