mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2005-09-20, 06:19   #12
ppo
 
ppo's Avatar
 
Aug 2004
italy

7116 Posts
Default

Quote:
Originally Posted by cheesehead
Suppose it's true. It wouldn't speed up anything, because one still has to compute all the S(i) mod M values leading up to S(n-3) in order to test whether S(n-3) = 2^((n+1)/2) mod M. And that's exactly what the L-L test already does (except that it continues one more step to compute S(n-2) mod M). There's no time savings.
yes, I know that, but I was only asking if someone has proved such assumption to be true, or false
thanks , pierpaolo
ppo is offline   Reply With Quote
Old 2005-09-20, 06:35   #13
ppo
 
ppo's Avatar
 
Aug 2004
italy

113 Posts
Default new name

thanks for the new name
I could even accept "useless math threads", but I could not accept to have this very nice reply
Quote:
Originally Posted by cheesehead
Oh, please continue coming up with those "random" ideas! Your next one could be something novel that will work. Many improvements that have been incorporated in our search have been ideas that no one thought of before. And even when a suggestion turns out to have been already thought-of, many GIMPSters will try to respond in a way that helps further your understanding.
moved to a forum named "cranks"

by the way, I think that an additional rule is absolutely necessary:
people should have the right to ask for removal of posts they have made

thanks to all of you for listening. Pierpaolo
ppo is offline   Reply With Quote
Old 2005-09-21, 05:07   #14
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

160248 Posts
Default

Quote:
Originally Posted by ppo
yes, I know that, but I was only asking if someone has proved such assumption to be true, or false
thanks , pierpaolo
Right. I got mixed up. Sorry.

Last fiddled with by cheesehead on 2005-09-21 at 05:15
cheesehead is offline   Reply With Quote
Old 2006-01-04, 02:16   #15
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5·701 Posts
Default

Quote:
Originally Posted by cheesehead
(*sigh*) If we try to save the full, unmodded values of the S(i) so that we could backtrack as you suggest (or, in another attempted speedup, just perform the mods with different modulus), we will find that after just a small number (less than 1000) of iterations, the S(i) values become so large that the entire known universe is not large enough to store them. (Exercise: Calculate the number of digits in S(1000) if no mod is performed at each step. Compare that to the number of particles in the known universe!)

But when we perform the modulos to keep the S(i) sizes manageable, we lose information necessary to correctly backtrack (or to re-use the S(i) with a different modulus).

A classic time vs. space tradeoff.
Excuse me if this has been covered, but you're talking about "classical" computers. But what about quantum computers? A 500 qubit quantum computer could, theoretically, simulate 2^500 states at once. This would mean that, although you wouldn't necessarily be able to do it in one fell swoop, you might be able to go forward, say, a thousand iterations at a time in a Lucas-Lehmer test.

And factoring could go a ton higher, too.
jasong is offline   Reply With Quote
Old 2006-01-04, 02:41   #16
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×599 Posts
Default

Quote:
Originally Posted by jasong
Excuse me if this has been covered, but you're talking about "classical" computers.
I don't think any of my conclusions about the proposed L-L speedup assume or require non-quantum computation. The key limitation is imposed by the size of the numbers, and quantum computing won't change that. In the context of this thread's topic, "speed up" refers to number of computational steps, not units of time.

Quote:
But what about quantum computers? A 500 qubit quantum computer could, theoretically, simulate 2^500 states at once. This would mean that, although you wouldn't necessarily be able to do it in one fell swoop, you might be able to go forward, say, a thousand iterations at a time in a Lucas-Lehmer test.
Have you overlooked that most unmodded S(i) values have many more than 500 bits? That in fact they rapidly approach, then exceed, having as many bits as the number of particles in the universe? Where does that number of qubits reside?

Quote:
And factoring could go a ton higher, too.
Yes, factoring can benefit from quantum computing. But that doesn't help the Lucas-Lehmer test.

Last fiddled with by cheesehead on 2006-01-04 at 02:54
cheesehead is offline   Reply With Quote
Old 2006-01-04, 02:43   #17
ColdFury
 
ColdFury's Avatar
 
Aug 2002

14016 Posts
Default

Quote:
Originally Posted by jasong
Excuse me if this has been covered, but you're talking about "classical" computers. But what about quantum computers? A 500 qubit quantum computer could, theoretically, simulate 2^500 states at once. This would mean that, although you wouldn't necessarily be able to do it in one fell swoop, you might be able to go forward, say, a thousand iterations at a time in a Lucas-Lehmer test.

And factoring could go a ton higher, too.
No, that's a gross simplification of how Quantum Computers work. They can't magically do a thousand iterations at once, since each iteration still depends on the previous. What you could do is run a lot of parallel iterations which don't depend on each other. This would not allow you to speed up the LL test. Moreover extracting the result is very very hard.

One could in principle use Shor's Algorithm to factor numbers, though you would need a lot of q-bits.

There's a reason there's so few algorithms for quantum computers, they're very very hard to design because of the constraints a QC imposes.

QCs do not magically speed up any task you throw at them, only very specific kinds of tasks.
ColdFury is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
maximum theoretical speed of LL test w/o bandwidth limitations? ixfd64 Hardware 30 2012-03-05 06:16
Different Speed in different OS's Dubslow Software 11 2011-08-02 00:04
TF speed Unregistered Information & Answers 10 2011-07-27 12:34
what speed should I be seeing for my PII266MHz? there_is_no_spoon Hardware 1 2004-04-07 20:50

All times are UTC. The time now is 21:38.

Mon Nov 30 21:38:06 UTC 2020 up 81 days, 18:49, 2 users, load averages: 2.15, 2.28, 2.32

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.