Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm having a bit of trouble working through an example in the RSA entry on Wikipedia.

At step 5, $d$ is calculated as $2753$. However, $d$, which is the multiplicative inverse of $e$, can be calculated by applying Bézout to $$ de - k\phi(n)=1 ,$$ correct? When I run that calculation using Wolfram Alpha, I get $-367$. I'm assuming that I'm doing something wrong and that the Wikipedia entry is correct.

share|improve this question
add comment

1 Answer 1

You (and Wolfram Alpha) got the right answer, so it is very likely that you set up things correctly. Wikipedia also got the right answer. For note that $-367\equiv 2753\pmod{3120}$. (In the Wikipedia article, $\phi(n)=3120$, and we are calculating the inverse of $17$ modulo $\phi(n)$.)

Any two numbers that have the same remainder on division by $3120$ are treated as being "the same" modulo $3120$. So for example $5873$ would also be a correct answer. Wikipedia chose to give the smallest positive integer that works. Wolfram Alpha chose to give the number of smallest absolute value that works. There are legitimate arguments in favour of each choice.

share|improve this answer
    
Ah, okay. That was a really helpful answer. Thank you very much! –  dap Nov 14 '11 at 6:38
add comment

Your Answer

 
discard

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

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