Polynomial arithmetic

From Wikipedia, the free encyclopedia

Polynomial arithmetic includes basic mathematical operations such as addition, subtraction, and multiplication. These operations are defined naturally as if the variable $x$ was an element of $S$ . Division is defined similarly, but requires that $S$ be a field. Examples of fields include rational numbers, $Z p$ for $p$ prime, and real numbers. The set of all integers is not a field and does not support polynomial division.

[edit] Addition and subtraction

Addition and subtraction are performed by adding or subtracting corresponding coefficients. If

$f(x) = \sum_{i=0}^n a_ix^i; g(x) = \sum_{i=0}^m b_ix^i$

then addition is defined as

$f(x)+g(x)= \sum_{i=0}^m (a_i+b_i)x^i + \sum_{i=0}^n a_ix^i.$

[edit] Multiplication

Multiplication is performed much the same way as addition and subtraction, but instead by multiplying the corresponding coefficients. If $f(x) = \sum_{i=0}^n a_ix^i; g(x) = \sum_{i=0}^m b_ix^i$ then multiplication is defined as $f(x)\times g(x)=\sum_{i=0}^{n+m} c_ix^i$ where $c_k=a_0b_k+a_1b_{k+1}+\cdots+a_{k-1}b_1+a_kb_0$ . Note that we treat $a i$ as zero for $i > m$ and that the degree of the product is equal to the sum of the degrees to the two polynomials.

[edit] References

Stallings, William; : "Cryptography And Network Security: Principles and Practice", pages 121-126. Prentice Hall, 1999.

This article needs additional citations for verification.
Please help improve this article by adding reliable references. Unsourced material may be challenged and removed. (March 2008)