1
$\begingroup$

At the end of this Wikipedia section, you can see that $$\gcd(|r-s|,n)=q$$ or $$\gcd(|r-s|,n)=p$$ holds. I don't understand why.

$\endgroup$
1
  • 3
    $\begingroup$ Take the equations for $r$ and $s$ given above the part you reference and write out $r-s$. $\endgroup$
    – yyyyyyy
    Dec 10, 2015 at 11:56

1 Answer 1

2
$\begingroup$

By following the above advice (taking the equations for r and s given in the article and writing r-s) you will notice that q is a divisor, therefore GCD(|r-s|,n) cannot be 1. There are only two options left since n is only divisible by q and p.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.