1
$\begingroup$

In the search for the private key of a Merkle–Hellman knapsack cryptosystem. I have encountered the following relationship: $$b=a^{-1}\pmod m$$ I have found $b=2017$ and $m=65535$ and the modular inverse equation can be written as: $$2017=a^{-1}\pmod {65535}$$ I want to find $a$, but came only with a brute force solution and I have troubles understanding this type of equation.

$\endgroup$
3
$\begingroup$

Use the extended Euclidean algorithm to find integers $a$ and $b$ such that $$ 2017a + 65535b = 1 . $$

Then $2017$ is the inverse of $a$.

$\endgroup$
0
$\begingroup$

$$ \gcd( 65535, 2017 ) = ??? $$

$$ \frac{ 65535 }{ 2017 } = 32 + \frac{ 991 }{ 2017 } $$ $$ \frac{ 2017 }{ 991 } = 2 + \frac{ 35 }{ 991 } $$ $$ \frac{ 991 }{ 35 } = 28 + \frac{ 11 }{ 35 } $$ $$ \frac{ 35 }{ 11 } = 3 + \frac{ 2 }{ 11 } $$ $$ \frac{ 11 }{ 2 } = 5 + \frac{ 1 }{ 2 } $$ $$ \frac{ 2 }{ 1 } = 2 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccc} & & 32 & & 2 & & 28 & & 3 & & 5 & & 2 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 32 }{ 1 } & & \frac{ 65 }{ 2 } & & \frac{ 1852 }{ 57 } & & \frac{ 5621 }{ 173 } & & \frac{ 29957 }{ 922 } & & \frac{ 65535 }{ 2017 } \end{array} $$ $$ $$ $$ \begin{array}{ccc} \frac{ 1 }{ 0 } & \mbox{digit} & 32 \\ \frac{ 32 }{ 1 } & \mbox{digit} & 2 \\ \frac{ 65 }{ 2 } & \mbox{digit} & 28 \\ \frac{ 1852 }{ 57 } & \mbox{digit} & 3 \\ \frac{ 5621 }{ 173 } & \mbox{digit} & 5 \\ \frac{ 29957 }{ 922 } & \mbox{digit} & 2 \\ \frac{ 65535 }{ 2017 } & \mbox{digit} & 0 \\ \end{array} $$

So, you see, by the main property of continued fraction convergents, which is that the little 2 by 2 determinants of consecutive convergents are $\pm 1,$ such as $32 \cdot 2 - 65 \cdot 1 = -1,$ or $65 \cdot 57 - 1852 \cdot 2 = 1,$ at the end

$$ 65535 \cdot 922 - 2017 \cdot 29957 = 1. $$ Or, $$ 65535 \cdot 922 + 2017 \cdot (-29957) = 1. $$ If preferred, we can carefully adjust the 922 by -2017, adjust the -29957 by +65535, for $$ 65535 \cdot (-1095) + 2017 \cdot 35578 = 1. $$

$\endgroup$

Your Answer

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

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