# RSA polynomial cubic root

Let's suppose we are given a linear polyonmial

\begin{align}f(x) = ax + b\end{align}
where a and b is known which satisfies this equation

\begin{align}y^3 - f(x) \equiv 0\mod(n) \end{align} where n is RSA modulus.

Is there any way to solve for pair(x,y)?

Follow-up question: If there is restriction where only those values of x are allowed for which \begin{align}f(x)

• In $y^3 - f(x) \equiv 0 \pmod{n}$, how are $x$ and $y$ related? Are you looking for any $(x, y)$ pair that satisfies the equation? Is $x$ a known constant? Or, did you mean $y^3 - f(y) \equiv 0 \pmod{n}$ – poncho Nov 12 '20 at 14:04
• yeah @poncho I am looking for any valid pair of (x,y) where x and y are natural numbers. I will update the question – Saurav Kumar Singh Nov 12 '20 at 14:08

## 1 Answer

Is there any way to solve for pair(x,y)?

If you're looking for an arbitrary pair, it's easy (assuming $$a \ne 0$$).

• Pick an arbitrary $$y$$

• Solve for $$f(x) = y^3$$; that'd be $$x = a^{-1}(y^3 - b) \pmod{n}$$

You're done.

• If we had to find for smallest value possible of x, then can we do it? – Saurav Kumar Singh Nov 12 '20 at 14:35
• why do u think that x will not be smallest? when You stated ${f(x)<n}$, and a, b are constant. – SSA Dec 13 '20 at 6:42
• @SauravKumarSingh: if $y$ happened to have a cube root modulo $n$ (which it will quite a lot of the time), then a solution with $x=0$ will be minimal. However, finding that solution would imply solving the RSA problem with $e=3$; that's a hard problem. – poncho Dec 13 '20 at 17:13