What type of an algorithm does Mlucas use?
It uses the well-known Lucas-Lehmer test for Mersenne numbers, which involves selecting an initial seed number (typically 4, but other values, such as 10, also work), then repeatedly squaring and subtracting 2, with the result of each squaring being reduced modulo M(p), the number under test. This square/subtract-2 step is done exactly p-2 times. If the result (modulo M(p)) is zero, M(p) is prime. For an excellent and much more in-depth discussion of the Lucas-Lehmer test and many other prime-related topics, please visit Chris Caldwell’s web page on Mersenne numbers. • 2) Where does the code spend most of its time? Since the numbers being tested (and hence the intermediate residues in the LL test) are so large that they typically must be distributed across several hundred thousand computer words, by far the most time-consuming part of the LL test is the modular squaring. • 3) How does the code accomplish the squaring? For a large integer occupying N computer words, a simple digit-by-di
