Finding VERY large primes

[cheesehead]

Originally Posted by LaurV

Well, now if you would have so much space, why to store the "3^" and not to store the exponent only? I mean the product. The reason we need the "3^" and generally "b^" part is because the product is not reducible mod Mp (it is however reducible mod (f-1)(g-1) where f, g are the factors of Mp, which we don't know). So, if we have so much memory, we can store the product of all the powers to a high B1, and then take only a single exponentiation of 3 (or b) for each p, mod Mp and a single GCD at the end.

But your proposed "single exponentiation" will have to be performed via many modular multiplications, won't it? (AFAIK, one can't just do an FFT on the base and exponent to get exponentiation in one step.) And won't the total cost of those multiplications wind up being the same as in the way we now do it?

[LaurV]

Of course. I was talking only about storage. About the necessary time, well, it may be even more costly that you said, or it may be not. Because you need anyhow FFT for squaring and you will need a lot of squares at the end, for each bit in that large product. In the way as we are currently doing, primes can be paired to optimize the exponentiation, and taking the modulus each step reduces the number of squares too. If you compute and store the product before, there is no pairing and no optimization possible, but you only need to do exponentiation for each exponent p (no overload), so you may get away cheaper for a large set of p's. What do I mean, if you raise b at the power of 101 (7 bits number) mod 20 bits number, you do 6 squarings of 20 bits numbers. Then you raise the result at 103, another 6 squarings. If you multiply x=101*103=10403 and raise b^x, then this is 13 bits number, you still do 12 squares of a 20 bit number, can't get cheaper. Of course, you did an additional short multiplication for x, but if you have to test 100 p's, then you only did the overload once (like the trouble of finding that 103 is the interesting one after 101, for example, is part of the overload, and in the first case you have to do it 100 times).

Since I try to implement some p-1 algorithm I cooked this donut on all sides, and honestly I don't know which solution is the best.