Re:2^74207281-1 is Prime
by pbsd on Tuesday January 19, 2016 @09:07PM
(#10935595)
This sort of thing is comparable to sending humans to the Moon. In and of itself, there's not much of a point to it; but the technology you develop to get there has a tendency to become useful in other, perhaps more useful, areas.
In the case of the Mersenne prime hunt, you need the fastest integer multiplication algorithms (and concrete implementations) you can. Fast integer multiplication is a big part of several useful number-theoretic algorithms. An interesting (to me) application is, for example, to check whether a number is only divisible by small primes. This is an integral part of the most efficient integer factorization algorithms known, and one way to do it is with a product tree followed by a remainder tree [1]. This would be unacceptably slow without quasilinear-time multiplication algorithms.
In the case of the Mersenne prime hunt, you need the fastest integer multiplication algorithms (and concrete implementations) you can. Fast integer multiplication is a big part of several useful number-theoretic algorithms. An interesting (to me) application is, for example, to check whether a number is only divisible by small primes. This is an integral part of the most efficient integer factorization algorithms known, and one way to do it is with a product tree followed by a remainder tree [1]. This would be unacceptably slow without quasilinear-time multiplication algorithms.
[1] https://cr.yp.to/lineartime/multapps-20080515.pdf