Function cashAddressPolynomialModulo

Perform the CashAddress polynomial modulo operation, which is based on the Bech32 polynomial modulo operation, but the returned checksum is 40 bits, rather than 30.

A.K.A. PolyMod

Remarks

Notes from C++ implementation: This function will compute what 8 5-bit values to XOR into the last 8 input values, in order to make the checksum 0. These 8 values are packed together in a single 40-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 + v3*x + v4. The implicit 1 guarantees that [v0,v1,v2,...] has a distinct checksum from [0,v0,v1,v2,...].

The output is a 40-bit integer whose 5-bit groups are the coefficients of the remainder of v(x) mod g(x), where g(x) is the cashaddr generator, x^8

• [19]*x^7 + [3]*x^6 + [25]*x^5 + [11]*x^4 + [25]*x^3 + [3]*x^2 + [19]*x
• [1]. g(x) is chosen in such a way that the resulting code is a BCH code, guaranteeing detection of up to 4 errors within a window of 1025 characters. Among the various possible BCH codes, one was selected to in fact guarantee detection of up to 5 errors within a window of 160 characters and 6 errors within a window of 126 characters. In addition, the code guarantee the detection of a burst of up to 8 errors.

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 bit-packed 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 (x), and after processing 2 inputs of v, it corresponds to x^2 + v0*x + v1 mod g(x). As 1 mod g(x) = 1, that is the starting value for c.