# Questions tagged [polynomials]

The tag has no usage guidance.

95 questions
Filter by
Sorted by
Tagged with
111 views

### I would like to know if there is a closed form expression from taking the reciprocal of a polynomial

I would like to know if there is a closed form expression from taking the reciprocal of a polynomial so that I can apply polynomial division to deconvolution using parallel fork-join multithreading. ...
198 views

### Algorithm for finding roots of a polynomial modulo prime powers

Given a polynomial $f$ with integer coefficients and a prime power $p^i$, I wish to find a root of $f$ modulo $p^i$, provided one exists, in polynomial or randomized polynomial time in the size of the ...
4k views

### Polynomial generator required to detect single bit error in Cyclic Redundancy Check codes

I was reading about CRC coding from two books: Data Communication and Networking by Forouzan Page 294 Computer Network by Tanenbaum Page 188 They use following notations: $d(x)$: dataword to be ...
62 views

180 views

173 views

### Proof of Minsky Papert Symmetrization technique

I frequently hear about the Minsky-Papert Symmetrization technique in many papers with a reference to the book of Minsky. I could not locate the book online. Could someone supply me a proof of the ...
69 views

### Multiplication of two or more algebraic quantities [closed]

Recently, I was facing the problem how to multiply to two or more algebraic quantities in c++. For example, if the two algebraic quantities are $$x^2-2x+3, \text{and } x-5$$ then the result of ...
35 views

### Comparing coefficients of boolean functions

Let a real polynomial representing a boolean function be $P(x_1,\dots,x_n) = \sum_{a\in\{0,1\}^n}c_ax^a = \sum_{a\in\{0,1\}^n}p(a)\prod_{i\in 1_a}x_i\prod_{j\in \bar{1}_a}(1-x_j)$ where $1_a$ is the ...
77 views

### efficient algorithms for factoring polynomials [closed]

Does anyone know what are the most efficient algorithms for factoring polynomials in a field of characteristic zero, i.e, a field that may contain infinitely many elements. I'm mainly concerned within ...
198 views

### How to find degree of polynomial represented as a circuit?

I know very little about arithmetic circuits, so maybe it is something well-known. Given a small circuit consisted of $\{1,x,-,+,*\}$ defining one variable polynomial. Let be additionally known that ...
57 views

### Polynomials and NSA [closed]

I'm looking for some applications of criteria of irreducibility of integer polynomials inside and outside mathematics. I was reading the of CV Filaseta, a great researcher in this area and he has ...
428 views

### Do you know of a brute-force algorithm for optimizing polynomial expressions? [closed]

For instance, given the polynomial expression $xy + x + y + 1$ it will output $(x+1)(y+1)$. Thanks!
75 views

A polynomial map is equal to another polynomial map iff they take on the same values at each point. So this is different from formal polynomials. So since in $\Bbb{Z}_p$, $x^{p-1} = 1$ for all $x \... 2answers 370 views ### Understanding Intel's algorithm for reducing a polynomial modulo an irreducible polynomial I'm reading this Intel white paper on carry-less multiplication. It describes multiplication of polynomials in$\text{GF}(2^n)$. On a high level, this is performed in two steps: (1) multiplication of ... 3answers 7k views ### Finding constants C and k for big-O of fraction of polynomials I am a teaching assistant on a course for computer science students where we recently talked about big-O notation. For this course I would like to teach the students a general method for finding the ... 2answers 410 views ### Testing whether a determinant polynomial is identically zero Suppose we are given matrices$A_1, \ldots, A_k$which are$n \times n$matrices with rational entries and are asked to determine whether the polynomial${\rm det}(\alpha_1 A_1 + \alpha_2 A_2 + \cdots ...
I need to evaluate a polynomial of degree n at the n cube roots of unity. Simple evaluation would take $O(n^2)$ time. I know that polynomial evaluation can be done in $O(n\log n)$ time using FFT. But ...