mersenneforum.org Shor's Factoring Algorithm - does it even work?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2005-10-25, 16:15 #1 Citrix     Jun 2003 159110 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
 2005-10-25, 16:18 #2 Citrix     Jun 2003 37·43 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 2005-10-25 at 16:19
2005-10-25, 16:49   #3
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

1157510 Posts

Quote:
 Originally Posted by Citrix 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
Looked ok to me, though I haven't studied in extreme detail.

The IBM achievement is real: they really did factor 15 on a quantum computer.

The algorithm becomes expected polynomial time if the period-finding 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

 2005-10-25, 17:21 #4 Citrix     Jun 2003 37·43 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
2005-10-25, 17:25   #5
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

11101010010002 Posts

Quote:
 Originally Posted by Citrix It look like crap to me.
Based upon your prior posts, I would have to say that you are not competent to
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
4-qubit quantum computer.

2005-10-25, 17:31   #6
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23·937 Posts

Quote:
 Originally Posted by Citrix 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.
Yes, it is clear that you have no clue why such a thing might be posted.

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.

 2005-10-25, 18:55 #7 Citrix     Jun 2003 37×43 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 2005-10-25 at 19:00
 2005-10-25, 19:14 #8 Citrix     Jun 2003 63716 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
2005-10-25, 19:29   #9
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

101101001101112 Posts

Quote:
 Originally Posted by Citrix 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
The classical part is in expected polynomial time if the quantum part runs fast enough. If, for example, the order finding runs in constant time irrespective of the size of N the proof is relatively straightforward. The classical GCDs all run in polynomial time and you need only show that a small (quantify this!) number of random trials need to be made. Then show how fast the order-finding algorithm must run if the entire algorithm is to run in expected polynomial time.

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

2005-10-25, 19:35   #10
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

264678 Posts

Quote:
 Originally Posted by R.D. Silverman Based upon your prior posts, I would have to say that you are not competent to 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 4-qubit quantum computer.
Are you sure about that?

15 is a 4-bit number, certainly, but I believe the IBM built a 7-qubit 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 2N-1 qubits to factor an N-bit integer.

Paul

 2005-10-25, 19:39 #11 Citrix     Jun 2003 37×43 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 2005-10-25 at 19:42

 Similar Threads Thread Thread Starter Forum Replies Last Post Prime95 Miscellaneous Math 72 2015-10-26 00:14 flouran Math 3 2009-10-27 09:31 Visu Math 66 2008-05-12 13:55 Citrix Factoring 6 2007-12-23 11:36 Visu Factoring 22 2006-11-09 10:43

All times are UTC. The time now is 07:55.

Mon Nov 28 07:55:36 UTC 2022 up 102 days, 5:24, 0 users, load averages: 0.99, 0.88, 0.82

Copyright ©2000 - 2022, 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.

โ  ยฑ โ รท ร ยท โ โ โฐ โ โ โ โ โ โค โฅ โฆ โง โจ โฉ โบ โป โผ โฝ โ โ โ โ ยฒ ยณ ยฐ
โ  โ ยฐ โ ~ โ โ โซ
โก โ โ โ โ โช โซ โโ โโ โ โ โ โ โง โจ โฉ โช โจ โ โ ๐ ๐ ๐ โฒ โณ
โ โ โ โฆ โฃ โฉ โช โ โ โ โ โ โ โ โ โ โ โ โ โ โ โค โ โ โ โต โถ โท โธ ๐
ยฌ โจ โง โ โ โ โ โ โ โ โ โ โด โต โค โฅ โข โจ โซค โฃ โฆ โฏ โฎ โฐ โฑ
โซ โฌ โญ โฎ โฏ โฐ โ โ ฮด โ โฑ โ โ
๐ข๐ผ ๐ฃ๐ฝ ๐ค๐พ ๐ฅ๐ฟ ๐ฆ๐๐ ๐ง๐ ๐จ๐ ๐ฉ๐๐ ๐ช๐ ๐ซ๐ ๐ฌ๐ ๐ญ๐ ๐ฎ๐ ๐ฏ๐ ๐ฐ๐ ๐ฑ๐ ๐ฒ๐ ๐ด๐๐ ๐ต๐ ๐ถ๐ ๐ท๐๐ ๐ธ๐ ๐น๐ ๐บ๐