| This function will compute what 6 5-bit
| values to XOR into the last 6 input values,
| in order to make the checksum 0. These
| 6 values are packed together in a single
| 30-bit integer. The higher bits correspond
| to earlier values.
|
| The input is interpreted as a list of
| coefficients of a polynomial over F = GF(32),
| with an implicit 1 in front. If the input is
| [v0,v1,v2,v3,v4], that polynomial is v(x)
| = 1x^5 + v0x^4 + v1x^3 + v2x^2 + v3x
| + v4. The implicit 1 guarantees that
| [v0,v1,v2,…] has a distinct checksum from
| [0,v0,v1,v2,…].
|
| The output is a 30-bit integer whose 5-bit
| groups are the coefficients of the remainder of
| v(x) mod g(x), where g(x) is the Bech32
| generator, x^6 + {29}x^5 + {22}x^4 + {20}x^3
| + {21}x^2 + {29}x + {18}. g(x) is chosen in
| such a way that the resulting code is a BCH
| code, guaranteeing detection of up to 3 errors
| within a window of 1023 characters. Among the
| various possible BCH codes, one was selected to
| in fact guarantee detection of up to 4 errors
| within a window of 89 characters.
|
| Note that the coefficients are elements of
| GF(32), here represented as decimal numbers
| between {}. In this finite field, addition is
| just XOR of the corresponding numbers. For
| example, {27} + {13} = {27 ^ 13} = {22}.
|
| Multiplication is more complicated, and
| requires treating the bits of values themselves
| as coefficients of a polynomial over a smaller
| field, GF(2), and multiplying those polynomials
| mod a^5 + a^3 + 1. For example, {5} * {26}
| = (a^2 + 1) * (a^4 + a^3 + a) = (a^4 + a^3 + a)
| * a^2 + (a^4 + a^3 + a) = a^6 + a^5 + a^4
| + a = a^3 + 1 (mod a^5 + a^3 + 1) = {9}.
|
| During the course of the loop below, c
| contains the bitpacked coefficients of the
| polynomial constructed from just the values of
| v that were processed so far, mod g(x).
|
| In the above example, c initially corresponds
| to 1 mod g(x), and after processing 2 inputs of v,
| it corresponds to x^2 + v0x + v1 mod g(x). As
| 1 mod g(x) = 1, that is the starting value for c.
|
| The following Sage code constructs the
| generator used:
|
| B = GF(2) # Binary field
| BP. = B[] # Polynomials over the binary field
| F_mod = b5 + b3 + 1
| F. = GF(32, modulus=F_mod, repr=‘int’) # GF(32) definition
| FP. = F[] # Polynomials over GF(32)
| E_mod = x2 + F.fetch_int(9)*x + F.fetch_int(23)
| E. = F.extension(E_mod) # GF(1024) extension field definition
| for p in divisors(E.order() - 1): # Verify e has order 1023.
| assert((ep == 1) == (p % 1023 == 0))
|
| G = lcm([(e**i).minpoly() for i in range(997,1000)])
|
| print(G) # Print out the generator
|
| It demonstrates that g(x) is the least common
| multiple of the minimal polynomials of
| 3 consecutive powers (997,998,999) of
| a primitive element (e) of GF(1024).
|
| That guarantees it is, in fact, the generator
| of a primitive BCH code with cycle length 1023
| and distance 4. See
| https://en.wikipedia.org/wiki/BCH_code for more
| details.