20051026, 19:36  #23  
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Quote:
Alex 

20061022, 14:47  #24 
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? 
20061118, 17:03  #25 
1867_{16} 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. 
20061119, 23:30  #26 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Wrong, it needs (at least) 2N1 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 
20080727, 12:10  #28  
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
2351_{8} Posts 
(1) I need more details about the Shor's algorithm
Quote:
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 20080727 at 13:04 Reason: up only so 

20080727, 13:00  #29 
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 polynomialtime. The condition is being written as p is prime if and only if (xa)^{p}=(x^{p}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, (xa)^{p} mod p = (xa) On the right hand side, x^{p} mod p = x so, (x^{p}a) mod p = (xa) 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 20080727 at 13:24 Reason: that, which was being. 
20080727, 14:56  #30  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
2·7^{3}·17 Posts 
Quote:
Factoring a 400bit 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 4bit 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 20080727 at 14:56 

20080727, 14:58  #31  
Tribal Bullet
Oct 2004
3^{2}×5×79 Posts 
Quote:
More background reading here 

20080728, 10:33  #32  
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
4E9_{16} Posts 
Quote:
But, what about the AKS algorithm. Did both of you skip up reading about it? 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 (xa)^{p} = (x^{p}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 20080728 at 10:39 

20080728, 11:46  #33  
"Ben"
Feb 2007
3,733 Posts 
Quote:
Well, I'm pretty sure jasonp has done his homework w.r.t AKS: http://images.apple.com/acg/pdf/aks3.pdf 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Alternativelygifted factoring algorithm  Prime95  Miscellaneous Math  72  20151026 00:14 
Shor's Algorithm  flouran  Math  3  20091027 09:31 
Prime Factoring Algorithm  Visu  Math  66  20080512 13:55 
Faster Factoring Algorithm?  Citrix  Factoring  6  20071223 11:36 
A new prime factoring algorithm?  Visu  Factoring  22  20061109 10:43 