0
votes
0answers
34 views

All my notes together on $\Bbb{Z}_p$-theoretic comp. complexity theory.

Def 1. A $\Bbb{Z_p}^k$-machine is a theoretical computer with $k$ data memory slots and $p$ is a prime number. All the operations on the machine are done one at a time in the ring $\Bbb{Z}_p$. No ...
0
votes
1answer
43 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 ...
0
votes
1answer
19 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$, ...
0
votes
1answer
19 views

Is there a way to compute if(i < j) k := (a + b)c with polynomials over $\Bbb{Z}_p$?

Let $p$ be a prime and let all variables be in $\Bbb{Z}_p$. Then you can write the result of if(i > 0) k = (a + b)c; (C code) as a polynomial $k := ...
0
votes
0answers
9 views

Are these computational models equivalent?

Let $f : X \to Y$ be a problem that you want to compute. Say we have an $O(1)$-computable maps, $\phi, \psi$, such that $X \xrightarrow{\phi} (\Bbb{Z}_n)^k \xrightarrow{\psi} Y$. After all, ...
0
votes
0answers
36 views

Existence of a det. poly-time algo for problem $f: X \to Y$.

$f : X \to Y$ is a deterministic polynomial-time algorithm for problem inputs $x \in X$ and problem outputs $f(x) = y \in Y \iff $there exists a polynomial $P_f \in \Bbb{Z}[x_1]$ such that $C\cdot ...
0
votes
0answers
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$? ...
1
vote
3answers
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 ...
5
votes
2answers
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 ...
4
votes
2answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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$?
0
votes
1answer
72 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 ...
2
votes
0answers
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$ ...
3
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
2answers
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 ...
2
votes
1answer
208 views
2
votes
3answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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.
1
vote
2answers
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 ...
9
votes
2answers
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. ...
1
vote
2answers
88 views

Factoring any single-variable polynomial in $\mathbb C$

The fundamental theorem of algebra says $$ \forall p(x):\mathbb C \to \mathbb C,\ p(x) = a\prod_{n=0}^m\big(b_nx+c_n\big) $$ where $p(x)$ is a single-variable polynomial, and $\{a;m\}\cup\{\forall ...
3
votes
1answer
52 views

Computational Complexity of Algorithms

I want to know if the following proposition is correct or not? For any integer k, there exists an problem P for which, the minimum possible time complexity of any solution algorithm is ...
1
vote
1answer
76 views

what if geometric sequence + geometric sequence

I wrote a program that basicly can find the formula of the sequence that created with any-degree equation. For example if you give my program that sequence: [1926, 2811, 833240, 28778265, 398155842, ...
2
votes
2answers
89 views

Prove that consecutive Legendre Polynomials do not have a common root.

I am using the following definition of Legendre Polynomials: $P_0(x)=1$ $P_1(x)=x$ $\displaystyle P_{k+1}(x)=\frac{2k+1}{k+1}x P_k(x)-\frac{k}{k+1} P_{k-1}(x)$ Q: Prove that for no $k\in ...
0
votes
1answer
32 views

Distinct-degree factorization

I'm trying to understand distinct-degree factorization from Wikipedia. I'm trying the algorithm on paper with $q=9$ and $f(x) = (x+4)(x+5) = x^2+2 \in F_{q}$. We start with $i=1$. I calculate $g = ...
1
vote
0answers
60 views

Positive Semidefiniteness of a polynomial.

I have a multivariate polynomial $p(x_1,\ldots,x_n)$ and I wish to check if it is positive semidefinite over $R^n$. I can always choose any direction $\vec{v}$ and check that the univariate polynomial ...
3
votes
1answer
285 views

Recursive FFT java implementation

Given below is my java program for FFT. For the input {0,2,3,-1} its returns a false output in complex point representation. ...
0
votes
1answer
103 views

Multiplying Polynomials with fewer coefficient multiplications

Not sure how this works! Apparently it can be done in 5-6 multiplications Show how to multiply two degree 2 polynomials using fewer multiplications of coefficients than the naive algorithm.
5
votes
1answer
422 views

Finding all roots of polynomial system (numerically)

I want to numerically find all the roots of a system of polynomials (n equations in n variables). Since I can compute the Jacobian for the system (analytically or otherwise), I can use the Newton ...
3
votes
1answer
232 views

Roots of rational equation with multiple variables?

Let's say we have a rational polynomial in $k$ variables. We are only interested in rational solutions. If $k = 1$, name the variables ${x}$, if $k = 2$, name them ${x,y}$. For $k = 1$, it can be ...
1
vote
1answer
55 views

minimizing multiplications in computing a polynomial expression

I am looking for an algorithm which presents a given polynomial in many variables (given as a sum of monomials) in a form with the smallest number of multiplications of variables. For example ...
1
vote
1answer
146 views

Trying to sort the coefficients of the polynomial $(z-a)(z-b)(z-c)…(z-n)$ into a vector

So I have a factored polynomial of the form $(z-a)(z-b)(z-c)\ldots(z-n)$ for $n$ an even positive integer. Thus the coefficient of $z^k$ for $0 \le k < n$ will be the sum of all distinct $n-k$ ...
2
votes
1answer
135 views

Algorithms for deciding whether a function over a finite ring is polynomial or not?

Let $R$ be a finite ring, and $f$ be a function from $R$ to $R.$ Suppose I want to know whether $f$ can be represented as a polynomial or not? Are there any good algorithms for finding this out?
2
votes
0answers
70 views

Construction of polynomials with non-commutative elements.

I have a simple set of polynomials which I know how to construct for each integer $n$, but I havn't been able to write them down in terms of concrete sums and products. For $n\in\mathbb N_+$, we have ...
1
vote
2answers
311 views

Solution of Diophantine equation for polynomials

I'm trying to solve this polynomial Diophantine equation for $R$ and $S$: $ AR + BS = G $ where $A(x) = a_0x^{n_a} + a_1x^{n_a-1} + a_2x^{n_a-2} + ... + a_{n_a}$ $B(x) = b_0x^{n_b} + b_1x^{n_b-1} + ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
2
votes
3answers
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 ...
0
votes
3answers
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 ...
3
votes
2answers
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 ...
4
votes
1answer
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 ...
4
votes
3answers
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 ...
9
votes
2answers
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 ...
1
vote
1answer
208 views

Efficient calculation of polynomial product

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