20051025, 16:15  #1 
Jun 2003
1579_{10} Posts 
Shor's Factoring Algorithm  does it even work?
http://www.answers.com/main/ntquery;...2_1&sbid=lc02a
Is there any merit to this method? It look like crap to me. The classical method in no way is polynomial time. The site claims that 15 was factored on a quantum computer using this method. What do you think? Citrix Posted in msl section 
20051025, 16:18  #2 
Jun 2003
1,579 Posts 
More crap:
http://www.answers.com/main/ntquery;jsessionid=2g1j7jrn1rbn8?method=4&dsid=2222&dekey=Jones%27s+period+proxy+algorithm&gwp=8&curtab=2222_1&sbid=lc02a&linktext=Jones's%20period%20proxy%20algorithm don't know why anyone would post something like this. Last fiddled with by Citrix on 20051025 at 16:19 
20051025, 16:49  #3  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
17·619 Posts 
Quote:
The IBM achievement is real: they really did factor 15 on a quantum computer. The algorithm becomes expected polynomial time if the periodfinding subroutine is fast enough. No fast classical algorithm for period finding is known, but the variant run on a quantum computer is sufficiently fast to make the overall algorithm run in expected polynomial time. What is your specific complaint about the presentation? That is, what precisely leads you to the judgement "The classical method in no way is polynomial time."? Note that I was careful always to say "expected polynomial time". Choosing a random number allows for the possibilty that you may pick a very long sequence of useless values. However, as long as the probability of you being so unlucky is small enough the overall algorithm can be expected to run in polynomial time. Paul 

20051025, 17:21  #4 
Jun 2003
1,579 Posts 
If you read the classical part of algorithm 1 above, it looks not in polynomial time. Give me a counter example for a random number.if yout hink the above is not true. Since the classical part is not in P, then the authors should not claim the algorithm is in p.
Citrix 
20051025, 17:25  #5  
Nov 2003
2^{2}×5×373 Posts 
Quote:
make such a judgment. You can barely do basic algebra. Shor's algorithm is correct and it works. 15 has indeed been factored on a 4qubit quantum computer. 

20051025, 17:31  #6  
Nov 2003
2^{2}×5×373 Posts 
Quote:
Although I have not looked at the details, the basic idea is correct. If one represents 1/N as a repeating decimal, AND the length of the recurrence is small (very tiny) relative to N, then this method can factor N. The reason it works is that if the period is tiny, then so are the primes dividing N. However, its run time is proportional to the value of the primes dividing N and thus is essentially equivalent to trial division. It requires about the same amount of arithmetic. Maybe one day you will stop making pronouncements about subjects that you do not understand..... But I doubt it. I suggest that you stop making pronouncements and go study some number theory. 

20051025, 18:55  #7 
Jun 2003
1,579 Posts 
I never said it did not work. What I said was that the algorithm is not polynomial as it is claimed.
@R.D. Silverman Before you say others do not know how to do algebra, please learn how to read. Citrix Last fiddled with by Citrix on 20051025 at 19:00 
20051025, 19:14  #8 
Jun 2003
1,579 Posts 
Shors algorithm says that for a pseudo random number a, find a^x=a^(x+r )mod n
where n is the number to be factored. How do you do this on an ordinary computer for a large number? I don't think the algorithm is p? If r could be found easily then all numbers can be factored in p! Citrix 
20051025, 19:29  #9  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
17·619 Posts 
Quote:
I repeat but with emphasis this time: what is your specific complaint about the classical part ot the algorithm? That is, present your analysis. "it looks not in polynomial time" is not an analysis. At best it is an unsupported observation. Paul 

20051025, 19:35  #10  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10523_{10} Posts 
Quote:
15 is a 4bit number, certainly, but I believe the IBM built a 7qubit machine, using NMR with an organic molecule containing 7 nuclei with spin >0 and in chemically distinct environments. Working purely from memory (meaning I'm too lazy to look it up at this instant), I believe that Schor's algorithm requires 2N1 qubits to factor an Nbit integer. Paul 

20051025, 19:39  #11 
Jun 2003
1579_{10} Posts 
Take the RSA number for example or a Cunningham number n, then find x and r such that
a^x=a^(x+r) (mod n) for a=101 and where 2*r>n. if you can solve this in P then factoring is in P, why do you need quantum computers? This is the part I do not get Citrix Last fiddled with by Citrix on 20051025 at 19:42 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Alternativelygifted factoring algorithm  Prime95  Miscellaneous Math  72  20151026 00:14 
Shor's Algorithm  flouran  Math  3  20091027 09:31 
Prime Factoring Algorithm  Visu  Math  66  20080512 13:55 
Faster Factoring Algorithm?  Citrix  Factoring  6  20071223 11:36 
A new prime factoring algorithm?  Visu  Factoring  22  20061109 10:43 