Actually, Bob's reply, though perhaps a bit more pointed than necessary, makes perfect sense to anyone who understands the basics of a oneway iterative procedure like the LL test. (I say "one way" because although it is theoretically possible to run it in reverse, that requires both modular square root taking, which is much harder than the modular squaring we use to proceed in the forward direction, and knowledge of the final value, which is impossible to attain without having first run the test in the forward direction.) Your example of trialdivision to test for factors is in no way analogous  in trialdividing to find a factor of N, you can easily calculate floor(sqrt(N)) and work backwards from that, if you like. Better still, you can precompute batches (or ranges) of trial divisors and assign each to a separate processor  the problem is trivially parallelizable. Generalize "meeting in the middle" to "testing all primes <= floor(sqrt(N))" and there you go.
In the LL test, we start with some appropriate initial value (e.g. 4), then do a bunch of squareandsubtracttwo steps. So far, no problem. But even if we could somehow run the test in reverse (add two, take square root) as fast as forward, what does "meeting in the middle mean" if we don't know the ending value from which we are supposed to run the "upper half" test in reverse? That's why your query is illposed.
Oh, and in response to your other point, "FFT" stands for "Fast Fourier Transform"  it's the algorithm we use to efficiently effect the largeinteger multiplies needed for bignumber primality testing.
Last fiddled with by ewmayer on 20051206 at 21:09
