Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm working with Shor's algorithm and I have a question regarding the following step

$$a^r -1 = (a^{r/2}+1)(a^{r/2}-1)=0 \pmod n$$

Now what is going to be the result if ${r/2}$ was -1? this will mean it's going to be like this: $(1/a+1)(1/a-1)$ Will it also be $= 0 \pmod n$?

share|improve this question
Sure, but $r$ is positive and $r/2=-1$ lends to $r=-2$. Aren't you confused with $a^{r/2} \equiv -1 (\mod n)$? – daniel May 4 '14 at 15:25
@daniel i think i am, but how is r/2 =-1 leading to r=-2? – Scarl May 5 '14 at 15:22
@daniel however, if r wasn't even then we should return to the first step of the classical part right? as in choose a different a where a<N (N= the number we want to factor) – Scarl May 6 '14 at 4:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.