Score:1

Crypto

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

vimwitch

1/22/24, 3:32 PM

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?

2 + 0

multivariate-cryptography

Score:2

Crypto

kodlu

1/22/24, 6:01 PM

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

+ 4

vimwitch

1/22/24, 6:28 PM

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?

fgrieu

1/22/24, 7:05 PM

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](https://doi.org/10.4007%2Fannals.2021.193.2.4)), 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)$.

kodlu

1/22/24, 7:09 PM

Thanks, I was being a bit sloppy.

kodlu

1/22/24, 7:17 PM

For 2 variables, fix $y=y_0$ and apply given idea to find $x.$ The complexity for each fixed $y$ is as before.

Score:-1

Crypto

Don Freecs

1/22/24, 3:57 PM

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

+ 2

vimwitch

1/22/24, 5:22 PM

in $−$ what is the $k$ variable?

Don Freecs

1/22/24, 6:06 PM

$k$ is some constant from $\mathbb{Z}$

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Is it possible to solve a linear polynomial in a finite field

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.