Shor's Factoring Algorithm - does it even work?

[akruppa]

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

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?

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.

[akruppa]

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

[ixfd64]

It seems that researchers have been making quite some progress on developing quantum computers, as seen here. :)

[Raman]

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.

[Raman]

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=(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,
(x-a)^p mod p = (x-a)

On the right hand side, x^p mod p = x
so, (x^p-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

[xilman]

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

[jasonp]

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.

More background reading here

[Raman]

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.

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
(x-a)^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.

[bsquared]

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