# Usage of the nth-root function in cryptography

Having offered a fast integer nth-root algorithm to a bigint library that is also used for cryptography I was asked if it does its work in constant time, so I took a look at the literature to see how other programmers solved that problem and found—nothing.

That leads to the question: is there any cryptographic algorithm out there—and in use— that needs an integer nth-root function?

EDIT: "integer nth-root function" here means a plain, vanilla truncating nth-root function $$k = \lfloor m^{1/n} \rfloor$$ with the restrictions $$\{k, m, n\} \in \mathbb{Z}$$ and $$n > 0$$.

• Are you asking about the n-th root function over a finite ring, a finite field, or over the reals? May 25 '19 at 11:14
• @GeoffroyCouteau Not the reals in this case (I don't think a truncating nth-root function would make much sense but I might err, of course) but I'm completely open to any hint. I can save a lot of work (and headaches) if there is no algorithm known to the experts that uses a nth-root function. I can still add it later if somebody complains but it is cheaper if I can spare that work for now. May 25 '19 at 11:26
• The reason why I ask is because some cryptosystems do use modular n-th roots over a ring - RSA decryption is an e-th root modulo $p*q$, Paillier decryption involves an n-th root modulo $n^2$, etc. May 25 '19 at 11:43
• Integer $n^{\mathit{th}}$ root is very useful for breaking stupid uses of RSA. Fortunately the serious uses of it, like RSA-KEM for encryption, are not vulnerable to this. But nobody cares if an attack runs in constant time. May 25 '19 at 14:27
• well then my answer to your question would be "not that I know of", but additional opinions of other members might be preferable :) May 25 '19 at 18:37