Information About

Shor's Algorithm
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...



The algorithm is significant because it implies that Public Key Cryptography might be easily broken, given a sufficiently large quantum computer. RSA , for example, uses a Public Key ''N'' which is the product of two large Prime Number s. One way to crack RSA encryption is by factoring ''N'', but with classical algorithms, factoring becomes increasingly time-consuming as ''N'' grows large; more specifically, no classical algorithm is known that can factor in time O((log ''N'')''k'') for any ''k''. By contrast, Shor's algorithm can crack RSA in Polynomial Time . It has also been extended to attack many other public key cryptosystems.

Like many quantum computer algorithms, Shor's algorithm is Probabilistic : it gives the correct answer with high probability, and the probability of failure can be decreased by repeating the algorithm. However, since a proposed answer (in particular primality) is polynomial time verifiable, the algorithm can be modified to work in expected polynomial time with zero error.

Shor's algorithm was discovered in 1994 by Peter Shor . Seven years later, in 2001 , it was demonstrated by a group at IBM , which factored 15 into 3 and 5, using a quantum computer with 7 Qubits .


Procedure


The problem we are trying to solve is that, given an Integer ''N'', we try to find another integer ''p'' between ''1'' and ''N'' that divides ''N''.

Shor's algorithm consists of two parts:

# A reduction of the factoring problem to the problem of Order-finding , which can be done on a classical computer.
# A quantum algorithm to solve the order-finding problem.


Classical part



  1. Pick a pseudo-random number ''a'' < ''N''

  2. Compute Gcd (''a'', ''N''). This may be done using the Euclidean Algorithm .

  3. If gcd(''a'', ''N'') ≠ 1, then there is a nontrivial factor of ''N'', so we are done.

  4. Otherwise, use the period-finding subroutine (below) to find ''r'', the Period of the following function:

    :f(x) = a^x\ \mbox{mod}\ N,
    i.e. the smallest integer ''r'' for which
    f(x+r) = f(x).

  5. If ''r'' is odd, go back to step 1.

  6. If ''a'' ''r''/2 ≡ -1 (mod ''N''), go back to step 1.

  7. The factors of ''N'' are gcd(a''r''/2 ± 1, ''N''). We are done.




Quantum part: Period-finding subroutine:



  1. Start with a pair of input and output Qubit registers with log2''N'' qubits each, and initialize them to

  N^{-1/2} \sum_y e^{2\pi i x y/N} \lefty ight angle</math>
  :<math> N^{-1} \left \sum {x:\, F(x) f(x_0)} e^{2\pi i x y/N} ight^2
  N^{-1} \left \sum_{b} e^{2\pi i (x_0 + r b) y/N} ight^2
  '''Proof:''' For Simplicity, Denote (''a'' <sup>''r'' / 2</sup> &minus 1) And (''a'' <sup>''r'' / 2</sup> + 1) By ''u'' And ''v'' Respectively ''N'' ''uv'', So ''kN'' ''uv'' for some integer ''k'' Suppose gcd(''u'', ''N'') = 1 then ''mu'' + ''nN'' = 1 for some integers ''m'' and ''n'' (this is a property of the Greatest Common Divisor ) Multiplying both sides by ''v'', we find that ''mkN'' + ''nvN'' = ''v'', so ''N'' ''v'' By contradiction, gcd(''u'', ''N'') &ne 1 By a similar argument, gcd(''v'', ''N'') &ne 1