Shor's Factoring Algorithm - does it even work?

[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

[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.

[xilman]

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

[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

[R.D. Silverman]

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.

[R.D. Silverman]

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.

[Citrix]

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

[Citrix]

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

[xilman]

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

[xilman]

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

[Citrix]

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