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

2005-10-25, 19:43   #12
xilman
Bamboozled!

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

2·73·17 Posts

Quote:
 Originally Posted by 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
Ah, a great light dawns!

You are quite correct in your observation. No algorithm is known to solve that problem in polynomial time on a classical computer.

However, such an algorithm is known for a quantum computer --- it is Schor's algorithm.

The article to which you refer specifically states that the order-finding subroutine is to be run on a quantum computer. In this situation the entire algorithm runs in polynomial time.

Looks like you thought that the entire algorithm had to be run on a classical machine.

Paul

 2005-10-25, 19:47 #13 Citrix     Jun 2003 3×5×107 Posts What does this mean "A reduction of the factoring problem to the problem of order-finding, which can be done on a classical computer. " -- How do you do this? Citrix
2005-10-25, 19:50   #14
akruppa

"Nancy"
Aug 2002
Alexandria

46438 Posts

Quote:
 Originally Posted by 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
On a conventional computer the algorithm is purely exponential-time. The idea is:

1. Choose some a
2. Compute a^n (mod N) for 1<=n<=k*N, with k large enough. This sequence is o-periodic, o=ord_N(a)
3. Do a Fourier transform on the sequence. Since it is o-periodic, the Fourier coefficients for the frequency o/(k*N) will dominate
4. Randomly choose a coefficient with probability according to its amplitude

On a conventional computer, steps 2 and 3 take \Omega(N) steps. On a quantum computer, you can put the all the exponent qubits into a
(1 1)
(1 -1) / sqrt(2) state, i.e. a 0 and 1 bit with 50% probability each, and exponentiate by that exponent. The result of this exponentiation is a superposition of all a^n. This superposition can be transformed with a Quantum Fourier Transform (QFT), giving you a state where the o/(k*N) frequency and its multiples dominate in amplitude. Measuring the state gives you one of these values. You can then recover o by a continued fraction expansion. The nice thing is that the exponentiation and the QFT can be done in time O(log(N)^2), iirc.

There are some catches that make the algorithm extremely tricky to actually implement, but the idea itself is sound.

I gave a presentation on this algorithm at the uni once. Quantum comuting is by far the weirdest I've seen yet. Mind-boggling does not begin to describe it. If you're interested in this, get Nielsen and Chuang: Quantum Computation and Quantum Information.

Note: the above is from memory, there probably are errors. I think I got the overall idea right, though.

Alex

Last fiddled with by akruppa on 2005-10-26 at 22:37 Reason: corrected Hadamard matrix, complexity

 2005-10-25, 19:55 #15 Citrix     Jun 2003 3·5·107 Posts Thankyou very much. This stuff is really interesting. It was my fault. I was too quick to judge the method. I just read the classical part and thought that, it had to be done before the quantum part.
2005-10-25, 21:25   #16
Mystwalker

Jul 2004
Potsdam, Germany

3×277 Posts

Quote:
 Originally Posted by R.D. Silverman 15 has indeed been factored on a 4-qubit quantum computer.
Just for clarification:
The article stated 7-qubits. Which one is correct?

 2005-10-25, 21:34 #17 akruppa     "Nancy" Aug 2002 Alexandria 9A316 Posts 7 qubit is correct. The composite number 15 has 4 bits, and you need extra bits for the exponent, etc. Alex
 2005-10-25, 21:57 #18 ewmayer ∂2ω=0     Sep 2002 Repรบblica de California 5×2,351 Posts I'm renaming this thread "Shor's Factoring Algorithm = Crap?" (I believe that captures the tone of the initial posting, but is more descriptive) and moving it to the regular Math section. Note that there is no 'c' in the spelling of Peter Shor's last name. Last fiddled with by ewmayer on 2005-10-25 at 21:58
 2005-10-26, 03:42 #19 Citrix     Jun 2003 31058 Posts Please remove the word crap from the title. It was a misunderstanding on my part. (Rename it quantum computing perhaps) Thankyou, Citrix Last fiddled with by Citrix on 2005-10-26 at 03:43
 2005-10-26, 05:12 #20 akruppa     "Nancy" Aug 2002 Alexandria 46438 Posts Done. Alex
 2005-10-26, 05:36 #21 Peter Nelson     Oct 2004 232 Posts Quantum computing and the Shor algorithm in particular is mentioned in "Crandall and Pomerance: Prime Numbers: A computational approach" in second edition its 8.5.2 "The Shor quantum algorithm for factoring" on p422. For second edition it may be slightly in need of revision (ie the IBM machine factoring 15 was in 2001) whereas they say "We stress that an appropriate machine has not been built". Perhaps someone could suggest to C&P that they could mention the IBM experiment. However they do say "but if it were the following algorithm IS EXPECTED TO WORK". In their presentation they do not give all the details of the algorithm. In their words "we have been intentionally brief in the final steps of the algorithm". They do point out that it could be done on conventional computers but in much longer time which would become unworkable, and it is quantum computers that offer opportunity to use it. I personally found the answers.com/wikipaedia treatment more complete and a little more readable.
2005-10-26, 18:35   #22
ewmayer
2ω=0

Sep 2002
Repรบblica de California

101101111010112 Posts

Quote:
 Originally Posted by akruppa Done.
Wuss.

I quote:

Quote:
 Originally Posted by Citrix Is there any merit to this method? It look like crap to me.

 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 10:13.

Mon Feb 6 10:13:03 UTC 2023 up 172 days, 7:41, 1 user, load averages: 1.20, 1.19, 1.08