2
votes
1answer
79 views

Concrete FFT polynomial multiplication example

I have read a number of explanations of the steps involved in multiplying two polynomials using fast fourier transform and am not quite getting it in practice. I was wondering if I could get some help ...
0
votes
1answer
57 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 ...
2
votes
0answers
41 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$ ...
2
votes
3answers
401 views

Polynomial bounds?

Q1: Is the function $$\lceil{\lg n}\rceil!$$ polynomial bounded? Q2: Is the function $$\lceil{\lg\lg n}\rceil!$$ polynomially bounded? $$\lg = \log_2$$ Polynomially bounded: $f(n)$ is polynomially ...
2
votes
1answer
454 views

Calculating CRC code

I think I may be under a misconception. When calculating the CRC code, how many bits do you append to the original message? Is it the degree of the generator polynomial (e.g. x^3+1 you append three ...
1
vote
2answers
482 views

Why do we need Taylor polynomials?

This question doubles as "Is my understanding of what a Taylor polynomial is for, correct?" but In order to write out a Taylor polynomial for a function, which we will use to approximate said function ...
3
votes
2answers
241 views

How to multiply two polynomials represented by values at distinct points?

I have two polynomials of degree $d$. However, I do not have equations for them. I simply have $d + 1$ distinct points on each polynomial. How would I find the product of these polynomials without ...
1
vote
1answer
140 views

Deciding if a polynomial equals zero, once again.

We have a polynomial $p(x_1,\ldots,x_n)$ of degree $n$ whose coefficients are integers in $[-2^n,2^n]$. The polynomial is given to us as a ``black box'' - that is, we can ask someone what ...
0
votes
4answers
197 views

Deciding if a polynomial equals zero

We have a polynomial $p(x_1,\ldots,x_n)$ of degree $d$ whose coefficients are integers in $[-B,B]$. The polynomial is given to us as a "black box'' - we pick a point $x \in \mathbb{R}^n$ and someone ...
5
votes
2answers
5k views

Reed Solomon Polynomial Generator

I am developing a sample program to generate a 2D Barcode. And i am using reed solomon error correction code. By Going through this article i am developing the program. But i couldn't understand how ...
0
votes
1answer
176 views

inverse polynomial

I am reading from some notes on cryptography and came across this sentence: "We call a function f negligible in k if it asymptotically approaches zero faster than any inverse polynomial in k i.e., ...
2
votes
3answers
199 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 ...
8
votes
3answers
663 views

Karatsuba vs. Schönhage-Strassen for multiplication of polynomials

I am wondering how to most effectively multiply two polynomials with several 100's of coefficients, each coefficient having 1000-2000 decimal digits. I know Schönhage-Strassen begins to outperform ...
3
votes
1answer
93 views

An efficient way to check whether a polynomial (under certain condition) is absolutely equal to zero or not

We have a function $f$ of $N$ variables which is the product of $M$ polynomials: $$f(x_1,x_2,\ldots, x_N) = P_1 \cdot P_2 \cdots P_M.$$ Each $P_i$ is a polynomial of at most three variables ...