2
$\begingroup$

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 $.

$\endgroup$
2
$\begingroup$

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.

| improve this answer | |
$\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.