Shor's factoring algorithm help I'm having a little trouble fully understanding the final steps of Shor's factoring algorithm.

Given an $N$ we want to factor, we choose a random $x$ which has order $r$.

The first step involves setting up the registers and applying the Hadamard operator. The second step a linear operator is applied. The third step the second register is measured (I believe this step can be performed later instead). The fourth step the discrete Fourier transform is applied to the first register. Then we measure the first register.

Here's where I'm a little hazy:

We get a measurement in the form $\mid j , x^k \textrm{mod} N \rangle $.

From this we can find the convergents of the fraction $ \frac{j}{2^q} $ , the convergents are possible values of the order $ r $. Here do we just try all the convergents $ &lt; N $ and if we don't find $ r $ as one of the convergents do we just start again?

Also how does the probability for possible values $ j $ differ? They way I see it they should all have the same probability but Shor's paper says this isn't the case?

Just a little confused as some papers seem to say different things.

Thanks.
From this we can find the convergents
  of the fraction $j/2^q$ , the convergents
  are possible values of the order $r.$
  Here do we just try all the
  convergents $&lt;N$ and if we don't find $r$
  as one of the convergents do we just
  start again?


You could; the algorithm works fairly fast if you do. If you want to reduce the expected number of quantum steps, you could also do some other tests; for example you should check whether $r$ is a small multiple of one of the convergents. But if you don't find $r$ after these extended tests, you need to start again.


  Also how does the probability for
  possible values $j$ differ? They way I
  see it they should all have the same
  probability but Shor's paper says this
  isn't the case?


I don't know whether I can help you more with this, because you haven't given me enough information for me to tell why you're confused. The probability for each value of $k$ in the fraction $k/r$ is (very nearly) the same. However, depending on exactly where $k/r$ falls between the adjacent values of $j/2^q$ and $(j+1)/2^q$, the probabilities of the specific values of $j$ differ.