0
$\begingroup$

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)<n \end{align}$$

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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}$ $\endgroup$ – poncho Nov 12 '20 at 14:04
  • $\begingroup$ yeah @poncho I am looking for any valid pair of (x,y) where x and y are natural numbers. I will update the question $\endgroup$ – Saurav Kumar Singh Nov 12 '20 at 14:08
0
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ If we had to find for smallest value possible of x, then can we do it? $\endgroup$ – Saurav Kumar Singh Nov 12 '20 at 14:35
  • $\begingroup$ why do u think that x will not be smallest? when You stated ${f(x)<n}$, and a, b are constant. $\endgroup$ – SSA Dec 13 '20 at 6:42
  • $\begingroup$ @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. $\endgroup$ – poncho Dec 13 '20 at 17:13

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.