Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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 at 15:25
    
@daniel i think i am, but how is r/2 =-1 leading to r=-2? –  Sara May 5 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) –  Sara May 6 at 4:48
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.