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

2005-10-26, 19:36   #23
akruppa

"Nancy"
Aug 2002
Alexandria

2,467 Posts

Quote:
 Originally Posted by ewmayer Wuss.
Maybe. But Citrix explicitly asked for having that changed back, and I think the thread starter ought to have a say in how the thread should be titled...

Alex

 2006-10-22, 14:47 #24 crandles   53×163 Posts I gather the next number after 15 that could be factored is 21. I have heard of a quantum computer with 12 qubits with a claim this is the highest so far. How many qubits are needed to factor 21? If this is 12 or less has anyone done it?
 2006-11-18, 17:03 #25 proctor   186716 Posts A good reason shors is useless. O.k., so it requires 2N- 1 Qbits to work... Humm... Factoring a useful number (like rsa 1024) Would then require 2 * 2 ^ 1024 - 1 qbits. Correct me if i'm wrong, but if each atom could represent 1 qbit, there would still not be enough atoms in the universe for that. Let's say, on a more reasonable level, that every atom in that little IBM computer could be a qbit. That would make a billion billion (2^64) qbit computer. Which means it could find factors up to 2^63 - 1. A problem that can be done in under 1 second using trial division. See, the problem is that the complexity of the computer needed grows in linear time. The quantum computer actually needed to factor large numbers would be larger than the entirety of creation.
 2006-11-19, 23:30 #26 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts Wrong, it needs (at least) 2N-1 qubits to factor a number of N bits, so for RSA1024 the number of qubits would be (idealized) 2047. Due to technical difficulties, the number of qubits needed will be larger than than, but still a relatively small multiple of N. Alex
 2006-11-26, 00:03 #27 ixfd64 Bemusing Prompter     "Danny" Dec 2002 California 249510 Posts It seems that researchers have been making quite some progress on developing quantum computers, as seen here. :) Last fiddled with by ixfd64 on 2006-11-26 at 00:04
2008-07-27, 12:10   #28
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

23518 Posts
(1) I need more details about the Shor's algorithm

Quote:
 Originally Posted by R.D. Silverman Shor's algorithm is correct and it works. 15 has indeed been factored on a 4-qubit quantum computer.
I want to know more about the Shor's algorithm.
I know that it is in the complexity class BQP, i.e. quantum polynomial time algorithm.

How long does it take so to factor a GNFS 100 or a GNFS 150 on a quantum computer (whose speed is compatible to that of a Pentium 4 or a Core 2 Duo) by using the Shor's algorithm?

A GNFS 120 takes about 5 days on a Pentium 4 at 2.8 GHz, and that
Core 2 Duo is four times faster than a Pentium 4 processor.

Last fiddled with by Raman on 2008-07-27 at 13:04 Reason: up only so

 2008-07-27, 13:00 #29 Raman Noodles     "Mr. Tuch" Dec 2007 Chennai, India 3×419 Posts (2) Something is wrong with the AKS algorithm? I have read that the AKS algorithm is a deterministic polynomial time algorithm to test the primality of a number, that had been discovered by 3 IIT Kanpur students in August 2002. The paper was being entitled as 'PRIMES IS IN P', a suitable title, indeed, where P is the complexity class, i.e. deterministic polynomial-time. The condition is being written as p is prime if and only if (x-a)p=(xp-a) mod p Now that let p be a Carmichael number, for example 561 On the left hand side, since p is a Carmichael number, (x-a)p mod p = (x-a) On the right hand side, xp mod p = x so, (xp-a) mod p = (x-a) So, this algorithm holds so well (LHS = RHS) for all the Carmichael Numbers, which is not at all valid! Please clarify it up to me Last fiddled with by Raman on 2008-07-27 at 13:24 Reason: that, which was being.
2008-07-27, 14:56   #30
xilman
Bamboozled!

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

2·73·17 Posts

Quote:
 Originally Posted by Raman I want to know more about the Shor's algorithm. I know that it is in the complexity class BQP, i.e. quantum polynomial time algorithm. How long does it take so to factor a GNFS 100 or a GNFS 150 on a quantum computer (whose speed is compatible to that of a Pentium 4 or a Core 2 Duo) by using the Shor's algorithm? A GNFS 120 takes about 5 days on a Pentium 4 at 2.8 GHz, and that Core 2 Duo is four times faster than a Pentium 4 processor.
We don't know.

Factoring a 400-bit integer will require a quantum machine with around a thousand qubits (at least 799 and probably more) and we've no real idea how to build one or how fast it will work. The state of the art at the moment is factoring a 4-bit number.

Your question is, in some sense, equivalent to asking how long it would take to factor a 15,000 digit number. For this question, other than "a long time" we just don't know.

Paul

Last fiddled with by xilman on 2008-07-27 at 14:56

2008-07-27, 14:58   #31
jasonp
Tribal Bullet

Oct 2004

32×5×79 Posts

Quote:
 Originally Posted by Raman How long does it take so to factor a GNFS 100 or a GNFS 150 on a quantum computer (whose speed is compatible to that of a Pentium 4 or a Core 2 Duo) by using the Shor's algorithm?
A quantum factoring algorithm has an exponential running time until you build a quantum computer big enough to run it on your desired input. With Shor's algorithm we are very far from being able to do that, for RSA numbers of nontrivial size.

2008-07-28, 10:33   #32
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

4E916 Posts

Quote:
 Originally Posted by xilman Factoring a 400-bit integer will require a quantum machine with around a thousand qubits (at least 799 and probably more) and we've no real idea how to build one or how fast it will work. The state of the art at the moment is factoring a 4-bit number.
Ok, fine. I understand the current situation of the Shor's algorithm.

It is used to prove, i.e. confirm the primality of any given number.

Is the condition really this one?
p is prime if and only if
(x-a)p = (xp-a) mod p

If yes, it holds good so for all the Carmichael Numbers, whereas it shouldn't if it were a primality proving algorithm.

Last fiddled with by Raman on 2008-07-28 at 10:39

2008-07-28, 11:46   #33
bsquared

"Ben"
Feb 2007

3,733 Posts

Quote:
 Originally Posted by Raman But, what about the AKS algorithm. Did both of you skip up reading about it?

Well, I'm pretty sure jasonp has done his homework w.r.t AKS: http://images.apple.com/acg/pdf/aks3.pdf

 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:02.

Mon Feb 6 10:02:03 UTC 2023 up 172 days, 7:30, 1 user, load averages: 1.27, 1.12, 1.01