|
Long division is an algorithm for
dividing two numbers, obtaining the quotient,
one digit
at a time. The same applies for polynomials. Let’s see an example with integers
and their binary representation (base 2 polynomials): 63/5 = [12 3] that reads”
prime number 64 divided by prime number 7 gives the pair [12 as quotient and 3
as its residual]”. It holds true because 12x5 + 3 = 63. As a positional number
63 ó [111111] and 5 ó [101] with their associated positional
polynomials
[111111] ó x^5 + x^4 + x^3 + x^2 + x^1 + x^0
[101] ó x^2 + x^0
Note: Replacing x’s by base/module 2 the polynomials results
reproduce 63 and 5 as you may check.
Warning: In this example we use regular
arithmetic operators by “product” and “sum”. In most cryptanalysis and logical
applications the pair “AND”, “XOR” operators are used instead.
[111111]/[[101] ó
x^5 + x^4 + x^3 + x^2 + x^1 + 1
divided by x^2 + 1
|
Step
|
Oper
|
x^5
|
x^4
|
x^3
|
x^2
|
X^1
|
1
|
|
|
x^2
|
0
|
1
|
|
1
|
Mult
|
x^5
|
0
|
x^3
|
0
|
0
|
0
|
|
quotient
|
x^3
|
x^2
|
|
|
1
|
Substr
|
0
|
x^4
|
0
|
x^2
|
X^1
|
1
|
|
|
|
|
|
|
2
|
Mult
|
|
x^4
|
0
|
x^2
|
0
|
0
|
|
|
|
|
|
|
2
|
Substr
|
|
0
|
0
|
0
|
X^1
|
1
|
|
|
|
|
|
Giving as result:
[(1100), (11)] ó [12 3]
[(1.x^3 + 1.x^2 + 0.x^1 +
0.x^0), (1.x^1 + 1)]
GF2
LFSR operations can be
mathematically understood finite fields, specifically GF2, Galois Fields 2.
Fields require that numbers that belong to them remain within the “family” when
operated by addition, subtraction, multiplication and division. As you may easily
check positive integers do not satisfy because when subtracted appear negative
Integers. On the contrary Real numbers will apply if we ignore the case of
division by 0. Finite fields deals with finite number of members. GF2 deals
with only two members: 0 and 1. These filed is well suited to understand
mathematically the functioning of LFSR;s,
Linear Feedback Shift Registers (see our document about LFSR’s).
Let’s see its use to
interpret a five bit LFSR ó [B4 B3 B2
B1 B0] with Tap bits in positions 2 and 4. Remember that Tap positions are
determined by the “Generator Polynomial” of the whole series, in this case of
(2^5 – 1) five bits states terms.
The generator polynomial
is determined from the location of the tap positions on the LFSR. The polynomial
is fifth order because there are five memory units. Bits 0 and 2 have taps meaning
the following polynomial: P(x) = x^5 = x^2 + x^0 = x^2 + 1 = x2 + 1. But on GF2
add and subtract is the same giving the Generator Polynomial G(x) = x^5 + x^2 +
1 = 0. Let’s see now how this LFSR works starting with the “seed” [00001].
Functioning: a) shifting
to the left; b) feedback bit entering as bit B4; c) output bit: always B0 of
“old” state that virtually “falls” outside.
Recursively any state S(j) could be obtained by multiplying x by S(j-1), for
example:
x^25 = x.(x^24) = x.(x^4 + x^3 + x^2 + x^1) = x^5 + x^4 + x^3 + x^2
= (1 + x^2) + x^4 + x^3 + x^2 = x^4 + x^3 + 1
11010111101
Correspondence between
states, remainders and “precise quotients” could be now analyzed. To accomplish
this task we proceed to divide the numerator polynomial by the generator
polynomial obtaining a “fraction” as follows:
x^4 + x^3 + 1 divided by x^5 + x^2 + 1 gives 0,1xxxxxxxxxxx… where
the “mantissa” [1xxxxxxxxxxx…] bounded to five bits will give us the “state”
S(j), in this case S(25).
Long Division Mechanics
in GF2
Being the quotient: [11010100001001…..….] with 1’s in positions 1,
2, 4, 6, 11, 14, ….. as
computed above representing the following x powers: x^-1, x^-2, x^-4, x^-6,
x^-11, x^-14, …, respectively. The division executes classically as we were
told when Childs, adding zeroes to the right of the virtual limit of units and
fractions (from the black zone in the table). In summary it is only one long
division, namely: in the first step x^j is divided by
the generator polynomial to define the Numerator Polynomial module the
Generator Polynomial, and then step 2 continuing the division of the
“remainder”, generating the corresponding “state” S(j) and if continuing the
whole states sequence. To illustrate this fact let’s execute the first step
classically taking into account that S(j) is x^j|mod(x^5 + x^2 + 1). In the table below we compute x^25|
mod(x^5 + x^2 + 1), depicted in black background. Quotient polynomial is not
shown here.
We invite you to fill the quotient below
Generator Polynomial.
|