1
$\begingroup$

Say that in $\mathbb{F}_{999,999,000,001}$ I have an equation $0 = ax - b$ where $a$ and $b$ are random values from the field.

Is it possible to solve this equation for $x$ using the Extended Euclidean Algorithm without a brute force search?

If instead I was in a finite field with order as a 254 bit prime, would this problem be intractable?

$\endgroup$

2 Answers 2

2
$\begingroup$

This is not intractable. Moreover a solution always exists provided $a\neq 0$ (if $a$ is zero the solution is $x=0$).

For any $p$ prime, any $a\neq 0,$ in the field $\gcd(a,p)=1,$ and thus $a^{-1}$ can be efficiently computed via the extended Euclidean algorithm. Thus $x=a^{-1}b$ is efficiently computable.

Both the gcd, and the multiplication have relatively low complexity (see comment by @fgrieu) essentially no worse than $O((\log p)^3).$

$\endgroup$
4
  • $\begingroup$ Thanks for the answer, if I had a multivariate linear polynomial like $0=ax + by - c$ would finding the root for $x$ and $y$ be similar or would it be much more complex? $\endgroup$
    – vimwitch
    Jan 22, 2023 at 18:28
  • $\begingroup$ The complexity of the multiplication is larger than $\mathcal O(\log p)$; at least $\mathcal O(\log p\log(\log p))$ in theory (Harvey and van der Hoeven's result), up to $\mathcal O((\log p)^2)$ by elementary algorithms. The complexity of GCD is larger, I think $\mathcal O((\log p)^2\log(\log p))$ to $\mathcal O((\log p)^3)$. $\endgroup$
    – fgrieu
    Jan 22, 2023 at 19:05
  • $\begingroup$ Thanks, I was being a bit sloppy. $\endgroup$
    – kodlu
    Jan 22, 2023 at 19:09
  • 1
    $\begingroup$ For 2 variables, fix $y=y_0$ and apply given idea to find $x.$ The complexity for each fixed $y$ is as before. $\endgroup$
    – kodlu
    Jan 22, 2023 at 19:17
-1
$\begingroup$

denote your field by $K$ and let $p= 999 999 000 001$. what do you think about $ x= b a^{-1} $ when this quantity is well defined? clearly this requires that $a$ to be invertible mod $p$ this means that this linear equation to have a unique solution $x =ba^{-1} \mod p$ if and only if $gcd(a,p) = 1$

since this is efficiently computable then this problem is not intractable. when $gcd(a,p) \not= 0$ this means that $gcd(a,p) = p$ because $p$ is prime and so $ax-b = pkx - b = -b$ for any $k \in \mathbb{Z}$, and hence the equation becomes $0 = -b$ this is only true when $b=0$, if $b$ is not a zero then this linear equation has no solutions in $K$.

$\endgroup$
2
  • $\begingroup$ in $𝑝𝑘𝑥−𝑏$ what is the $k$ variable? $\endgroup$
    – vimwitch
    Jan 22, 2023 at 17:22
  • $\begingroup$ $k$ is some constant from $\mathbb{Z}$ $\endgroup$
    – Don Freecs
    Jan 22, 2023 at 18:06

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.