I use two bitsets to store two polynomials. I want one of them to be divided by 2nd and I want to get remainder after division. For example if I would like it on the paper:
w1= 110011010000000
w2 = 1111001
101000100
110011010000000 : 1111001
1111001
--1111110
1111001
----1110000
1111001
---100100 = remainder
Very few CPUs have builtin instructions for GF(2) division like this, so you'll need to implement it yourself with shifts and xors. Basically, you implement it exactly like you did it on paper -- shift the divisor up until its top bit matches that of dividend, then xor and shift back down, recording each position where you need an xor as a bit of the quotient. If all the polynomials in question fit in a single word, you can just use unsigned integer types for it. Otherwise, you'll need some multiprecision bitset type. The C++ std::bitset can be used for this, despite its problems (no easy way to convert between bitsets of different sizes, no bitscan functions).
template<size_t N> int top_bit_set(const bitset<N> &a) {
int i;
for (i = N-1; i >= 0; i--)
if (a.test(i)) break;
return i;
}
template<size_t N>
bitset<N> gf2_div(bitset<N> dividend, bitset<N> divisor, bitset<N> &remainder) {
bitset<N> quotient(0);
int divisor_size = top_bit_set(divisor);
if (divisor_size < 0) throw divide_by_zero();
int bit;
while ((bit = top_bit_set(dividend)) >= divisor_size) {
quotient.set(bit - divisor_size);
dividend ^= divisor << (bit - divisor_size); }
remainder = dividend;
return quotient;
}
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments