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

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

2 Answers 2

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

$\endgroup$
3
  • $\begingroup$ If we had to find for smallest value possible of x, then can we do it? $\endgroup$
    – Saurav
    Commented Nov 12, 2020 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
    Commented Dec 13, 2020 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
    Commented Dec 13, 2020 at 17:13
0
$\begingroup$

The answer is:

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.