On 20 Oct 99, at 0:39, Lucas Wiman wrote:
> After a certain point, the LL test would become profitable again, if I understand
> correctly. That crossover point is 2^31-1 for Mersenne numbers (It would certainly
> be possible to prove the next mersenne prime be trial division, though the LL test
> would be *much* faster). Quantum computer might raise this crossover point into the
> billions of digits, but I believe that trial division would still be O(sqrt(n)),
> (with a very small constant, but it still increases with the sqrt), whereas
> the LL test is O(lg(n)) (it would also be sped up by quantum computing).
> Unless I'm missing something about quantum computing (and I probably am).
The thing which people tend to forget about quantum computing is
that, before you can read the result you're interested in, you need
to be able to read the state of the system. That implies that you
need as much physical memory in the system as there are possible
states in the quantum field you're computing.
Though this doesn't rule out quantum computing as a potential major
advance, the physical universe (or, at least, the fraction of the
universe occupied by a computer's memory) does still restrict the
size of the computation you can do in one "cycle".
So the order of the algorithm still does matter - once the solution
space is too big to fit into physical memory - which will happen
rather easily with number theoretic (and combinatorial) calculations.
> (please forgive any typos, this telnet app doesn't allow backspace charactors
> on my shell account. Does anyone know of a good telnet app for windows?)
> (I would think that it wouldn't be hard to make one, but apparently it is).
Try QVT/Term. Unfortunately not freeware, but it does do a good job.
Regards
Brian Beesley
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
