All Questions
9
questions
0
votes
0
answers
20
views
How to understand 'the problem of determining the exact number of monomials in P(x) given by a black box is #P-Complete'
In this paper:https://dl.acm.org/doi/pdf/10.1145/62212.62241, what's given is $P(x)$ a (sparse) multivariate polynomial with real(or complex) coefficients.
The author claimed two things.
It is known ...
- 61
1
vote
0
answers
63
views
If a function interpolates as a polynomial on arithmetic progressions, is it a polynomial function?
Let $F$ be a finite field of size $q$, and let $d<q$. It is well known that for every sequence $x_0,x_1,\ldots, x_{d+1}$ of distinct elements in $F$, there is a sequence $a_1,\ldots,a_d$ of ...
- 111
0
votes
0
answers
54
views
What happens to the degree of the quotient polynomial if the divison is not clear?
Let's say that I have one polynomial $a(x)$ of degree $n$ with coefficients over $\mathbb{F}_p$, where $\mathbb{F}_p$ is a finite field of size $p$.
Asuming that $(x - r) \mid a(x)$ (i.e., that $r \in ...
- 321
1
vote
0
answers
262
views
What algorithms exist for Polynomial Interpolation of arbitrary degree in two variables.
Is there a way to take a set of points $((x_0, x_1), y)$ of arbitrary length and interpolated them into a polynomial of pre-defined degree.
So we would have a function $y = f(x_0, x_1) = (a_0) + (a_1 ...
- 11
3
votes
1
answer
144
views
Expected number of monomials in a random function over finite fields
Let $f : \{1,2\}^n \rightarrow \mathbb{Z}_3$ be a function from the multiplicative subgroup of order $2$ of $\mathbb{Z}_3$ over $n$ variables ($\{1,2\}^n$) to $\mathbb{Z}_3$, such that each coordinate ...
- 75
2
votes
1
answer
2k
views
Polynomial interpolation over Finite Field
Let $\mathbb{F}_p$ be a finite field (p is prime), and consider $V = \mathrm{Span}(\{1, x^2, x^3, x^5, x^6\}) \subset \mathbb{F}_p[x]$. What is the bound on $p$, such that there exists an ...
- 157
2
votes
1
answer
797
views
Interpolation of a rational function
Assume I am given two polynomials $f(x)$ and $g(x)$ with coefficients from a field $\mathbb{F}_p$, where $p$ is a prime.
Now I know that the set of these polynomials is a ring and not a field, meaning ...
- 287
1
vote
0
answers
97
views
Polynomial Evaluation
My question is to some extent related to cryptography, but I'd like the mathematicians answer my question, please (as their answers are usualy more clearer than cryptographers).
Consider I have a ...
- 227
1
vote
1
answer
1k
views
Using Lagrange's Interpolation Formula to show that boolean functions over finite fields are polynomials
Let $F_2$ be the set of all the functions from the finite field $GF(2^n)$ of $2^n$ elements to $GF(2)$. I am reading a textbook that proves that the elements of $F_2$ can be represented by polynomials;...
- 532