Manipulation of long binary values requires some special techniques. The polynomials notation lends itself to computation in hardware using only shift registers and exclusive-OR (XOR) gates. Once the mathematics of polynomials has been defined, the concept of prime polynomials can be introduced.
1. Binary values can be represented as polynomials with coefficents {0,1}.
For example, 110011 can be written as
and simplified as:
The order of a polynomial is the power of the highest non-zero coefficient. The above example shows a polynomial of "order 5".
2. Polynomials can be manipulated using the usual arithmetic rules, and these properites (closure, associative, commutative, etc) define a field.
Example 1: 110011 x 10 = 1100110 can be written as:
3. Polynomials always use modulus 2 arithmetic. This is equivalent to the exclusive-OR operation, as shown below.
0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 0
Example 2: 11 x 11 can be computed as:
11
x 11
----
11
+ 110
----
101 Note modulus 2 addition
and as a polynomial: Do not make the mistake of thinking "3 x 3 = 9". This is not your usual binary math!
Note the rules for subtraction follow from addition (if 1+1=0, then 0-1=1 !!), and are also equivalent to the exclusive-OR operation, as shown below.
0 - 0 = 0 0 - 1 = 1 1 - 0 = 1 1 - 1 = 0
With these rules in mind, the division (x2 + 1) / (x + 1) can be accomplished:
1 1 = x + 1
________
1 1 ) 1 0 1
1 1
----
1 1
1 1
----
0 no remainder
Therefore: x2 + 1 = (x + 1)(x + 1).
We say that (x + 1) is a factor of x2 + 1 . If a polynomial has no factors other than 1 and itself, it is a prime polynomial.
Note that 101 is not the decimal value 5, and 101 is not prime! [ Table of Factors ]
Since prime polynomials are of some importance, it is worthwhile to review some concepts of prime numbers in the familiar decimal world..
The prime numbers {2,3,5,7,11,13,17,19,23,29,31,37...} have no factors other than 1 and themselves.
To determine if a number such as 37 is prime, it can be tested against all possible factors from 2 to 37. In practice, we would immediately recognize EVEN numbers (is 100034 prime?) and proceed by testing for only ODD factors. Finally, we note that testing can stop when the square root of the number is reached.
To test if 37 is prime, we need only try {2,3,5}
Similarly, to test if 137 is prime, we need only try {2,3,5,7,9,11}
(Although we would probably not bother trying 9 after eliminating 3 as a factor.)
By recalling these rules, much unnecessary division can be avoided even when testing relatively large numbers. Further optimization of prime number testing is unnecessary at this level.
Following the logic outlined above, polynomials can readily be tested for possible factors:
If the lowest term in a polynomial is not 1, then x is a factor. This is equivalent to checking EVEN integers.
Example 3:
Consider the polynomial: 1100110 = = x6 + x5 + x2 + x
By inspection, this cannot be prime since 10 = = x is a factor.
Example 4:
Check if the following polynomial is prime:
1. Since the smallest term is 1, then x is not a factor.
2. The highest term is x7, terms up to x3 must be tested (corresponding to the square root).
We would need to test, at most, the following 'ODD' polynomials:
a. 11 : x + 1
b. 101 : x2 + 1 = (x+1)(x+1)
c. 111 : x2 + x + 1
d. 1001 : x3 + 1 = (x+1)(x2+x+1)
e. 1011 : x3 + x + 1
f. 1101 : x3 + x2 + 1
g. 1111 : x3 + x2 + x + 1 = (x+1)(x2+1)
Where some test divisions could be avoided if the obvious factorable terms are skipped, as shown above.
3. Proceed with test divisions. The first test division by (x+1) yields a zero remainder, and a factor is found. This polynomial is not prime.
1 0 1 1 1 1 1 = x6 + x4 + x3 + x2 + x + 1
-----------------
1 1 ) 1 1 1 0 0 0 0 1
1 1 modulo 2 subtraction!
---
0 1 0
0 1 1 subtract when the msb = 1
-----
1 0
1 1
---
1 0
1 1
---
1 0
1 1
---
1 1
1 1
---
0 remainder = 0
Therefore:
x7 + x6 + x5 + 1
= (x+1) (x6+x4+x3+x2+x+1)
Question: Can (x6 + x4 + x3 + x2 + x + 1) be further factored? Answer
The application of polynomials to the manipulation of binary numbers has a practical significance in the way in which the operations are actually performed in a digital circuit. Normally, it would be painstaking and slow to perform long division on large integers. The above example could be performed in hardware with simple XOR-gates and shift registers.
Observe the value 11 (highlighted) as the division proceeds below. This value is essentially being shifted across P(x). It has already been noted that subtraction is equivalent to XOR. Consequently, the division reduces to shifting 11 across P(x) and performing the XOR operation if the msb of both values equals 1.
1 0 1 1 1 1 1 = x6 + x 4 + x3 + x2 + x + 1
-----------------
1 1 ) 1 1 1 0 0 0 0 1
1 1 XOR
---
0 1
1 1 no!
---
0 1 0
1 1 XOR
-----
1 0
1 1 XOR
---
1 0
1 1 XOR
---
1 0
1 1 XOR
---
1 1
1 1 XOR
---
0 remainder = 0
23 SEP 98 - tervo@unb.ca
University of New Brunswick, Department of Electrical and Computer Engineering