View Single Post
Old 2005-12-06, 21:06   #7
ewmayer's Avatar
Sep 2002
Rep├║blica de California

101101001100102 Posts

Actually, Bob's reply, though perhaps a bit more pointed than necessary, makes perfect sense to anyone who understands the basics of a one-way 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 trial-division to test for factors is in no way analogous - in trial-dividing 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 square-and-subtract-two 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 ill-posed.

Oh, and in response to your other point, "FFT" stands for "Fast Fourier Transform" - it's the algorithm we use to efficiently effect the large-integer multiplies needed for big-number primality testing.

Last fiddled with by ewmayer on 2005-12-06 at 21:09
ewmayer is offline   Reply With Quote