Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
In the algorithm(link), for calculated n and chosen secret key s, we need to calculate $\sqrt[s]{p_{i}} \bmod p $.
As an example in original research paper (link) , For a given $p=9700247$ and $s=5642069$, It is given that $\sqrt[s]{2} \bmod p = 8567078 , \sqrt[s]{3} \bmod p = 5509479$ and so on.
So how to calculate this $\sqrt[s]{p_{i}} \bmod p $.
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 inverse of $s$ modulo $p-1$.
As $p$ is a prime, its multiplicative subgroup has order $p-1$, hence $\sqrt[s]{p_i} \bmod p = p_i^{s^{-1} \bmod p-1} \bmod p = p_i^u \bmod p$. So, once you've computed $u$ from the extended Euclidean algorithm, finding the $s$-th root of $p_i$ modulo $p$ is reduced to computing a modular exponentiation.
