--- On Wed, 5/30/12, djbroadhurst <

d.broadhurst@...> wrote:

> "paulunderwooduk" <paulunderwood@> wrote:

>

> > Please see my draft paper

>

> http://www.mersenneforum.org/showpost.php?p=298027&postcount=44

> Like many good ideas, Paul's modular equation [*], above, is

> both simple and effective. I think that it might usefully be

> decoupled from the rest of the preprint in a short (and also

> matrix-free) note along the lines "Lucas tests with Fermat

> tests for free", with due reference to C&P's 2 + 1 selfridge

> Frobenius method, whose Fermat test was not for free.

Sounds pretty neat. One caveat with two-for-the-price-of-one deals is that the two bits you get back might not actually be independent of each other, so you'd not be getting full value for money. It applies to all the Grantham one too of course.

Note that generally mathematicians and computer scientists prefer their Big-Oh costs to refer to the size of the input, not the value of the input. So the cost of the FFT is O(d^(1+eps)), where d=lg(n), rather than O(n^(1+eps)).

Phil