# Is it possible to solve a linear polynomial in a finite field

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?

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).$$

• 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? Jan 22, 2023 at 18:28
• 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)$.
– fgrieu
Jan 22, 2023 at 19:05
• Thanks, I was being a bit sloppy. Jan 22, 2023 at 19:09
• For 2 variables, fix $y=y_0$ and apply given idea to find $x.$ The complexity for each fixed $y$ is as before. Jan 22, 2023 at 19:17

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

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