mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-10-25, 16:15   #1
Citrix
 
Citrix's Avatar
 
Jun 2003

62516 Posts
Default 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
Citrix is offline   Reply With Quote
Old 2005-10-25, 16:18   #2
Citrix
 
Citrix's Avatar
 
Jun 2003

112·13 Posts
Default

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
Citrix is offline   Reply With Quote
Old 2005-10-25, 16:49   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

5·2,053 Posts
Default

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

112×13 Posts
Default

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
Citrix is offline   Reply With Quote
Old 2005-10-25, 17:25   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-10-25, 17:31   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-10-25, 18:55   #7
Citrix
 
Citrix's Avatar
 
Jun 2003

112×13 Posts
Default

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

112×13 Posts
Default

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
Citrix is offline   Reply With Quote
Old 2005-10-25, 19:29   #9
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

5·2,053 Posts
Default

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
xilman is online now   Reply With Quote
Old 2005-10-25, 19:35   #10
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

101000000110012 Posts
Default

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

157310 Posts
Default

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
Citrix 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 18:29.

Mon Sep 28 18:29:47 UTC 2020 up 18 days, 15:40, 1 user, load averages: 1.38, 1.68, 1.92

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