> The Mersenne-related point is that QC might someday make nonfactorial
> primality testing (e.g. LUcas-Lehmer for Mersennes) obsolete because it
> would be quicker to directly search for all factors <= sqrt(number).
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).
(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).
> of each squaring step. In practice this appears to allow a number of
> given size to be modularly squared about 3-5 times faster than sans DWT.
True. That would mean the mersenne exponent would have to be sqrt(3)-sqrt(5)
times bigger than the proth exponent. This is one more reason why the prize
money is not a great idea. It just encourages more of the same type of searches,
rather than inovation in math as was intended. Anyone who would invent a method of
prime production probably would have done it anyway (regardless of the EFF prize),
and I think that the power of distributed computing has been demostrated.
Lucas
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
