# Tag Info

In the Naccache-Stern knapsack cryptosystem, it holds that $\gcd(s,p-1) = 1$. Hence, you can compute the inverse of $s$ modulo $p-1$ (the coprimality ensure the existence of such an inverse). Computing this inverse can be done with the extended Euclidean algorithm, which gives you $u,v$ such that $su + (p-1) v = 1$: as $su = 1 \bmod p-1$, $u$ is indeed the ...