# 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}$ Commented Nov 12, 2020 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 Commented Nov 12, 2020 at 14:08

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? Commented Nov 12, 2020 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
Commented Dec 13, 2020 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. Commented Dec 13, 2020 at 17:13

Generate and output any arbitrary pair $$(x,y)$$.
There is always some $$f$$, which would fulfill the question and the follow-up question. It even works with fixing $$a=1$$, and looking for the appropriate $$b$$, s.t. your equations are fulfilled. And some $$b$$ always exist, regardless of $$x,y$$