17055Question on Miller-Rabin...
- Sep 25, 2005Hello everyone,
I have a question about the Miller-Rabin primality test. I was wondering,
what set of numbers are mathematically interesting to test with this
algorithm? I mean, when Jaeschke tested "all" numbers up to
341550071728321, did he test the even numbers also? Did he test all the
numbers that were divisible by 3, by 5, etc? In the "mathematical
community", is there some accepted lower limit where we can trial divide up
to x, and then start testing with Miller-Rabin?
I was wondering, if someone wanted to continue "the work", should all
numbers be tested, or should just the odds be tested, or what? I've
searched the internet for Jaeschke's original paper, which is in the
Mathematics of Computation volume 61 pages 915-926, but I've never seen
anyone quote exactly how he did his search, either algorithm wise, or
machine wise. If anyone knows these details, or maybe has a copy of the
paper to share, I would appreciate it very much.