On 12 Nov 00, at 17:18, xqrpa wrote:
> The author goes on to write:
>
> "Even so, it is mathematics that will gain the most. "Right now, when we
> tackle problems without knowing the truth of the Riemann hypothesis, it's
> as if we have a screwdriver," says Sarnak. "But when we have it, it'll be
> more like a bulldozer." For example, it should lead to an efficient way of
> deciding whether a given large number is prime. No existing algorithms
> designed to do this are guaranteed to terminate in a finite number of
> steps. "
>
> Well, the L-L Test seems to be just such an algorithm.
Indeed - in fact, even trial factoring terminates in a finite number
of steps. It's just that the finite number of trials required rapidly
becomes impossibly large.
I suppose what the author is trying to get at is that, given the
truth of the Generalized Reimann Hypothesis (aka Extended Reimann
Hypothesis), the primality of an arbitary number can be established
by executing a relatively small number of Miller's Tests - Miller's
Test being a well-known test which establishes whether a number is a
strong pseudoprime to a given base.
However, for Mersenne numbers, the LL test is still much to be
preferred - the running time of a single Miller's Test is comparable
to the running time of a LL test, whilst the number of Miller's Tests
required to establish the primality of a number of the order of
10^1000000 is over 10 million million, even given the GRH. [The
required number is 2(log n)^2]
This gets way above my head, but, according to Riesel, the GRH is
needed to prove that there is a "small" non-residue of order q mod p
for every prime p. I suppose that this may possibly be provable
independently of the GRH.
Regards
Brian Beesley
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt
