# Tagged Questions

27 views

### Do there exist polynomials not computable in polynomial time?

Motivation: Computing a problem in $k$ memory slots Do there exist polynomials in $R = \Bbb{Z}_p[z_1, \dots, z_k]$ that can't be computed in time polynomial in $k,p$? Thanks... Good luck! Edit. I ...
17 views

### Any problem computable in $k$ memory slots can be computed with polynomials.

Let our memory slots be represented by elements of $\Bbb{Z}_p$ for a prime $p$. $k$ memory slots would be $k$ copies of the ring: $R = (\Bbb{Z}_p)^k$. Suppose that for a problem $f : X \to Y$, ...
19 views

19 views

### finding the least non-zero of a multivariable polynomial

Let $P(x_1,x_2,...,x_m)$ be a homogeneous polynomial of degree n, with integers coefficients. How can you find the least* $a=(a_1,a_2,...,a_m)$, where $a_i$ are positive integers and $P(a)!\neq 0$? ...
84 views

### How to choose the starting point in Newton's method?

How to choose the starting point in Newton's method ? If $p(x)=x^3-11x^2+32x-22$ We only learnt that the algorithm $x_{n+1}:=x_n-\frac{f(x_n)}{f'(x_n)}$ converges only in some ...
144 views

### Understanding Intel's white paper algorithm for multiplication in $\text{GF}(2^n)$?

I'm reading this Intel white paper on carry-less multiplication. For now, suppose I want to do multiplication in $\text{GF}(2^4)$. We are using the "usual" bitstring representation of polynomials ...
54 views

### Finding out the coeffcient next to $x^2$ in $(\cdots(x-2)^2-2)^2\cdots-2)^2$.

In need to find out the coefficient next to $x^2$ in polynomial $(\cdots(x-2)^2-2)^2\cdots-2)^2$, where we nest the expression $(x-2)^2$ n times. Meaning that for $n=1$ we get $(x-2)^2$, for $n=2$ we ...
46 views

### Find coefficients of polynomial that has zeros at certain points

Given a list of values z0, z1, ..., zn-1 (possibly with repetitions), show how to find the coefficients of a polynomial P(x) of degree-bound n + 1 that has zeros only at z0, z1, ..., zn-1 (possibly ...
31 views

### algorithm to separate the roots of a polynom

I need an algorithm to separate the roots of a polynom. The degree of the polynom is n (10 < n < 20) and the polynom has the same number of roots as it's degree. All roots are real. I need to ...
51 views

### Polynomial composition

I have a polynomial of degree at least 4. How can I test if it is the composition of two other polynomials of degree at least 2? (Any polynomial is the composition of two polynomials if you allow one ...
62 views

### Efficient polynomial evaluation using idea of fast fourier transform

Please would anyone suggest an efficient algorithm ($O(n \log n)$) to evaluate a polynomial at all the $n$th roots of unity, where $n$ is not a power of $2$?
71 views

### Algorithm for a n x n grid of squares

Say we have a puzzle where by there are $n^2$ squares and each of the 4 sides of each square has a colour. The aim of the puzzle is to see if the squares can be arranged in such a way that when 2 ...
36 views

### LLL and factoring polynomials in $\Bbb Z[x]$

Given a degree $2k$ reducible polynomial $f(x)=\sum_{i=0}^{2k}a_ix^i\in\Bbb Z[x]$ with $gcd(a_{2k},\dots,a_0)=1$ that is known to be of the form $f_1(x)f_2(x)$ with $deg(f_i(x))=\frac{deg(f(x)}{2}=k$ ...
102 views

### Convert CRC to result of reversed polynomial?

Looking at the Wikipedia page for CRCs I see that they list a bunch of standard CRC polynomials along with the Reversed Polynomials of each. If I have a value that was calculated with a certain ...
24 views

### Compute all the directional derivatives of a trivariate polynomial function quickly

Given a trivariate polynomial $A\in\mathbb{R}[x,y,z]$, a direction $\vec v\in\mathbb{R}^3$ and a point $p\in \mathbb{R}^3$, what is the fastest way to compute the directional deriviatives ...
57 views

### Polynomial Question

Find polynomials $A(x)$ and $B(x)$ such that $A(x)P(x) + B(x)Q(x) = x + 1$ for all $x$ where $P(x) = x^4 - 1$ and $Q(x) = x^3 + x^2$. I'm stumped on this question. I know that I'm supposed to apply ...
208 views

### Prove that the Euclidean algorithm for gcd works with polynomials

Given the algorithm $E$: ...
100 views

### If I know that a polynomial (of order $k \gt 2$) has at most $1$ positive real root - can I find that easily?

[update 2] Urgghh - the time-consumption really stems only from the construction of the h-order polynomial. The time for finding the roots (only 10 to 20 times Newton-iteration because of my nice ...
74 views

### Bounding a bicubic polynomial

My actual situation is working with bicubic polynomials, (that is, polynomials of the form $\sum_{i=0}^3 \sum_{j=0}^3 a_{i,j} x^iy^j$) defined on the unit square $[0,1]^2$ (actually these are ...
52 views

### How to solve the polynomial equation $\sum_{i=1}^{i=m} \frac{l_i}{l_i - x} = n$?

Let m and n be strictly positive integers, and a set of m real positive numbers $$l_{i, i \in \{ 1, m \}}.$$ I want to solve numerically: $$\sum_{i=1}^{i=m} \frac{l_i}{l_i - x} = n$$ finding the m ...
46 views

### algorithm for Bezier curve with eleven control points

I would like to know the algorithm/ polynomial equation for a Bezier curve with eleven control points. Thanks in advance.
173 views

### Solve a set of non linear Equations on Galois Field

I have the following set of equations: $$M_{1}=\frac{y_1-y_0}{x_1-x_0}$$ $$M_{2}=\frac{y_2-y_0}{x_2-x_0}$$ $M_1, M_2, x_1, y_1, x_2, y_2,$ are known and they are chosen from a $GF(2^m).$ I want to ...
413 views

### Quickest way to determine a polynomial with positive integer coefficients

Suppose that you are given a polynomial $p(x)$ as a black box (i.e. some oracle, to which you feed $x$ and it returns $p(x)$). It is known that the coefficients of $p(x)$ are all positive integers. ...
88 views

32 views

145 views

### Computing the power of real algebraic numbers

I'm looking for an efficient algorithm to compute the $n$-th power $\alpha^n$ of a real algebraic number $\alpha$ given by an interval representation for $n \in \mathbb{N}$. An interval representation ...
64 views

### What is the most efficient algorithm for constructing an irreducible polynomial?

Theorem: Assuming that the generalized Riemann hypothesis is true, there is a deterministic polynomial time algorithm to find an irreducible polynomial of degree $n$ over $\mathbb{F_p}$ The ...
188 views

### Math/CS Algorithm Analysis Question

I've placed this on the Math Stack Exchange even though it is really a CS question because it is the math that is stumping me. Please note, I'm not asking you to do this problem for me, just to make ...
80 views

### Splitting a multiplication into multiple smaller steps, reaching the same result

Suppose I have a number, x, which should be doubled every second. If one had a function which is called exactly once every second, the solution would be simple: All you would have to do was ...
182 views

### Algorithm to check if a polynomial is positive in a given interval

I'm writing a program where I have a 3-dimensional polynomial (3 variables) of which I have to check if it is positive in a given product of 3 intervals (a volume). I found a paper which solved this ...
131 views

### Understanding an algorithm for computing a matrix polynomial

I'm trying to understand this algorithm by Charles Van Loan for evaluating a matrix polynomial $p(\mathbf A)=\sum\limits_{k=0}^q b_k \mathbf A^k=b_0\mathbf I+b_1\mathbf A+\cdots$ (where $\mathbf A$ is ...
293 views

### Is there an algorithm to find the roots of high-order polynomials?

It is not generally possible to determine the roots of a polynomial whose grade is bigger than 4 in terms of roots and basic operations. But I heard, that it is possible to give a criteria whether a ...
585 views

### Algorithm(s) for computing an elementary symmetric polynomial

I've run into an application where I need to compute a bunch of elementary symmetric polynomials. It is trivial to compute a sum or product of quantities, of course, so my concern is with computing ...
I have 2 polynomials $p_1(x_1,\ldots,x_n)$ and $p_2(x_1,\ldots,x_n)$, of which I have to compute the product, with a special property: The exponent of each variable is always either $0$ or $1$, where ...
As we all know, Sturm's axioms have completely solved the problem for finding the number of roots in an arbitrary interval $[a,b]$, using the derivative and forms a Sturm set. Now my question ...