mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-10-25, 19:43   #12
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

2·73·17 Posts
Default

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
xilman is online now   Reply With Quote
Old 2005-10-25, 19:47   #13
Citrix
 
Citrix's Avatar
 
Jun 2003

3×5×107 Posts
Default

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
Citrix is offline   Reply With Quote
Old 2005-10-25, 19:50   #14
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-10-25, 19:55   #15
Citrix
 
Citrix's Avatar
 
Jun 2003

3·5·107 Posts
Default

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.
Citrix is offline   Reply With Quote
Old 2005-10-25, 21:25   #16
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

3×277 Posts
Question

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?
Mystwalker is offline   Reply With Quote
Old 2005-10-25, 21:34   #17
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

9A316 Posts
Default

7 qubit is correct. The composite number 15 has 4 bits, and you need extra bits for the exponent, etc.

Alex
akruppa is offline   Reply With Quote
Old 2005-10-25, 21:57   #18
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Repรบblica de California

5×2,351 Posts
Default

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
ewmayer is offline   Reply With Quote
Old 2005-10-26, 03:42   #19
Citrix
 
Citrix's Avatar
 
Jun 2003

31058 Posts
Default

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
Citrix is offline   Reply With Quote
Old 2005-10-26, 05:12   #20
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

Done.

Alex
akruppa is offline   Reply With Quote
Old 2005-10-26, 05:36   #21
Peter Nelson
 
Peter Nelson's Avatar
 
Oct 2004

232 Posts
Default

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.
Peter Nelson is offline   Reply With Quote
Old 2005-10-26, 18:35   #22
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Repรบblica de California

101101111010112 Posts
Default

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.
ewmayer is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Alternatively-gifted factoring algorithm Prime95 Miscellaneous Math 72 2015-10-26 00:14
Shor's Algorithm flouran Math 3 2009-10-27 09:31
Prime Factoring Algorithm Visu Math 66 2008-05-12 13:55
Faster Factoring Algorithm? Citrix Factoring 6 2007-12-23 11:36
A new prime factoring algorithm? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”