On 10 Sep 2001, at 14:47, Gareth Randall wrote:
>
> What is the entropic efficiency of our calculations?
Um. We're not even gaining information in the strict (information
theory) sense, since all Mersenne primes existed long before
anyone formulated the concept - yet we are certainly raising the
entropy of the universe as a whole by our activities. In that sense,
the entropic efficiency must be zero, though it's hard to see how
any other computing activity could be any different.
>
> Is it possible to say how much "work" must be performed in order to
> verify whether a number is prime? If it is, then how efficient are our
> methods in comparison? For instance, can it be shown that there is
> theoretically a better method, but one that no-one has discovered?
So far as Mersenne numbers are concerned (and some other types
of numbers, e.g. Fermat numbers, numbers for which Proth's
Theorem applies) there is AFAIK no theoretical work which would
show that the tests we're using are anything other than optimal.
Theoretically there should be ways to improve primality tests for
general numbers so that they are about as efficient as the LL test
is for a number of the same approximate size. At present the best
algorithms for general numbers (e.g. ECPP) are a great deal less
efficient than this; the largest number proved prime using ECPP is
about the hundredth root of 2^6972593-1 in magnitude.
Practical implementation of tests is a different matter. At present
the best multiplication algorithms are O(n log n) - which would in
itself be a huge surprise to anyone working in this field 50 years
ago - yet it appears that there may be scope to improve on this.
With suitable hardware (VVLW architectures) O(n) is possible.
Also, the possible advent of quantum computing may have a
substantial effect on the choice of algorithm.
Regards
Brian Beesley
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
