$\begingroup$

So, my task is to find d if $p=5, q=11, e=17$. Here I've tried:

• Find $n=p\cdot q = 5*11 = 55$
• Find $\phi(n) = (p-1)(q-1)=(5-1)(11-1) = 40$
• Euclidean algorithm: $$ 40=2\cdot 17+6 \\ 17 = 2\cdot 6 + 5 \\ 6 = 1*5 + 1 $$
• The last one $$ 6-1*5=1 \\ 6 - 1(17-2\cdot 6)=1 \\ (40-2\cdot 17) - 1(17-2\cdot(40-2\cdot 17)) $$ The next step is to simplify the expression, and get something like $e\cdot d + \phi(n)\cdot x = 1$. But how can I get such simplified expression? I've tried to open brackets etc, but I haven't got such expression.

Thanks.

$\endgroup$ 1

2 Answers

$\begingroup$

$$\begin{align*} \left(40-2\cdot 17\right) - 1\cdot\left[17-2\cdot\left(40-2\cdot17\right)\right] &= 1\\ 40-2\cdot 17 - 17 + 2\cdot 40 -4\cdot 17 &= 1\\ 3\cdot 40 -7\cdot17 &= 1 \end{align*}$$

---

Or break the brackets early, which I usually prefer: $$\begin{align*} 6-1\cdot5 &= 1\\ 6-1\cdot(17-2\cdot 6) &= 1\\ 3\cdot6-1\cdot 17 &= 1\\ 3\cdot(40-2\cdot 17)-1\cdot17 &= 1\\ 3\cdot 40 -7\cdot17 &= 1 \end{align*}$$

$\endgroup$ 1 $\begingroup$

Could you clarify what 'd' is? Anyway, from my interpretation of d (I think it is an integer such that $17d+40x=1$). $$gcd(17,40)=(m,n)\\=>gcd(17,6)=(m,n-2m)\\=>gcd(5,6)=(m-2(n-2m),n-2m)=(5m-2n,n-2m)\\=>gcd(5,1)=(5m-2n,3n-7m)$$ Therefore $3n-7m=1=>3*40-7*17=1$. Hence $d=-7$

$\endgroup$ 1

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy