Shor's Factoring Algorithm - does it even work?
 

[url]http://www.answers.com/main/ntquery;jsessionid=2g1j7jrn1rbn8?method=4&dsid=2222&dekey=Shor%27s+algorithm&gwp=8&curtab=2222_1&sbid=lc02a[/url]

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

More crap:

[URL=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]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[/URL]

don't know why anyone would post something like this.

[QUOTE=Citrix][url]http://www.answers.com/main/ntquery;jsessionid=2g1j7jrn1rbn8?method=4&dsid=2222&dekey=Shor%27s+algorithm&gwp=8&curtab=2222_1&sbid=lc02a[/url]

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[/QUOTE]
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

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

[QUOTE=Citrix]

It look like crap to me.

[/QUOTE]

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.

[QUOTE=Citrix]More crap:

[URL=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]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[/URL]

don't know why anyone would post something like this.[/QUOTE]

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.

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

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

[QUOTE=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[/QUOTE]
The classical part is in expected polynomial time [b]if[/b] 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 [b]specific[/b] 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

[QUOTE=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.[/QUOTE]
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

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

[QUOTE=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[/QUOTE]
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

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

[QUOTE=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[/QUOTE]

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

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.

[QUOTE=R.D. Silverman]15 has indeed been factored on a 4-qubit quantum computer.[/QUOTE]

Just for clarification:
The article stated 7-qubits. Which one is correct?

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

Alex

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.

Please remove the word crap from the title. It was a misunderstanding on my part.
(Rename it quantum computing perhaps)

Thankyou,
Citrix

Done.

Alex

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.

[QUOTE=akruppa]Done.[/QUOTE]
Wuss. :mad:

I quote:

[quote=Citrix]Is there any merit to this method? It look like crap to me.[/quote]

[QUOTE=ewmayer]Wuss. :mad:
[/QUOTE]

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?

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.

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

It seems that researchers have been making quite some progress on developing quantum computers, as seen [url=http://en.wikipedia.org/wiki/Timeline_of_quantum_computing]here[/url]. :)

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

[quote=R.D. Silverman;64080]
Shor's algorithm is correct and it works. 15 has indeed been factored on a
4-qubit quantum computer.
[/quote]

I want to know more about the Shor's algorithm.
I know that it is in the complexity class [B]BQP[/B], 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.

(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 [COLOR=Black]discovered[/COLOR] by 3 IIT Kanpur students in August 2002.

The paper was being entitled as 'PRIMES IS IN P', a suitable title, indeed, where [B]P [/B]is the complexity class, i.e. deterministic polynomial-time.

The condition is being written as
p is prime if and only if
(x-a)[sup]p[/sup]=(x[sup]p[/sup]-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)[sup]p[/sup] mod p = (x-a)

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

[QUOTE=Raman;138400]I want to know more about the Shor's algorithm.
I know that it is in the complexity class [B]BQP[/B], 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.[/QUOTE]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

[QUOTE=Raman;138400]
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?
[/QUOTE]
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 [url="http://www.scottaaronson.com/blog/?p=208"]here[/url]

[quote=xilman;138404]
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.
[/quote]

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? :wink:
It is used to [I]prove[/I], i.e. confirm the primality of any given number.

Is the condition really this one?
[FONT=Comic Sans MS][SIZE=3] p is prime if and only if[/SIZE][/FONT]
[FONT=Comic Sans MS][SIZE=3](x-a)[sup]p[/sup] = (x[sup]p[/sup]-a) mod p[/SIZE][/FONT]

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

[quote=Raman;138432]

But, what about the AKS algorithm. Did both of you skip up reading about it? :wink:
[FONT=Comic Sans MS][/FONT]

[/quote]


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

[QUOTE=bsquared;138433]Well, I'm pretty sure jasonp has done his homework w.r.t AKS: [URL]http://images.apple.com/acg/pdf/aks3.pdf[/URL][/QUOTE]

I didn't answer because I'm not familiar with the theory (and don't feel like changing that right now). AKS basically involves a single big exponentiation of a finite field polynomial, repeated however many times it takes to remove the possibility of the input having factors. The big research question is how often that one primitive should be repeated. A, K and S prove that the number of primitives is cubic in the number of bits in the input, and Bernstein shows that for 'most' numbers it's quadratic. That seems to be the limit of current research that I'm aware of. AKS is a very cool algorithm that's computationally essentially useless; the coolness comes from the simplicity of the tools it needs to work.

PS: Raman, the main identity is not over integers mod p, but polynomials mod the polynomial x^r, with coefficients mod p; the algorithm is computationally expensive because those polynomials have huge degree

[QUOTE=jasonp;138437] ... limit of current research that I'm aware of. AKS is a very cool algorithm that's computationally essentially useless; the coolness comes from the simplicity of the tools it needs to work.
[/QUOTE]

Just to fill-in more of the relevant background, on the computational side,
ecpp has expected degree 4 runtime (the same as the AKS variants), but
is the current method-of-choice in practice. There have been a few
c. 10,000-digit (random) numbers proved prime; and Franke-et-al have the
top two, c. 15,000-digits and c. 20,000-digits.

The report above is the first I've seen of AKS hitting even 300-digits. Is
there a more current update on an AKS record? Aside from collecting
evidence of how far away it is from being able to hit the 10,000-digit range.

On the coolness part; provable, deterministic polyn time was the AKS
theorem. And (unlike Fermat) using tools that everyone else had been
looking at, just put together better. There was a public effort to see
whether we might have overlooked something similar for factoring, or
other problems considered hard; but if anyone found something, especially
something that would work in practice, they're not telling. -Bruce

21 factored with "Quantum Adiabatic Algorithm"
 

I found this recent paper :[URL="http://arxiv.org/abs/0808.1935"]http://arxiv.org/abs/0808.1935[/URL]

What next? Factor 33? :wink:

[QUOTE=paulunderwood;139389]I found this recent paper :[URL="http://arxiv.org/abs/0808.1935"]http://arxiv.org/abs/0808.1935[/URL]

What next? Factor 33? :wink:[/QUOTE]Maybe. An plausible alternative is 65, that being the next two-factor integer greater than the next larger power of two.


Paul

[quote=paulunderwood;139389]
I found this recent paper :[URL]http://arxiv.org/abs/0808.1935[/URL]

What next? Factor 33? :wink:
[/quote]

Huh! Think of going exponentially!

A small Mersenne or Repunit
followed up by the Series of Fermat Numbers! :smile:
fifth, sixth, seventh, eighth Fermat Numbers,

followed by GNFS 100, 120, 140...

I think that it would already be hopefully long before reaching even RSA 129
It would be in fact a long term goal! :wink:

Quantum computing means that the bits overlapping one over the other?