This should be a comment, but I can't post them, sorry. To follow up the above: Prof. Elkies is of course right about the $O(n^2)\,$ complexity of the basic algorithm, but it should be possible to get large constant-factor speedups with better implementation:

First of all there's probably 10x-50x available just by rewriting the program in C using the naive algorithm, and running on a multi-core processor, depending on available hardware. Let's say 25x on an 8-core AMD processor.

There might be another 2x(?) using Montgomery's representation (from cryptography) to get rid of most of the integer division operations in the modular exponentials. Actually maybe a lot more than 2x.

Finally, combining the above (I'm less sure of this) it might be possible to run on a graphics accelerator giving 100x or more.

Assuming 50x (perhaps using two or three computers) that would give 250000*6 minutes / 1440 minutes/day = about 3 weeks, which is above my guess of a "few days" but I think still feasible if someone was really interested. I'm surprised by how many upvotes this thread got.

9more comments