Function poly_tracemod

src/minisketch/tests/pyminisketch.py:238–251

Compute y + y^2 + y^4 + ... + y^(2^(field_size-1)) mod poly, where y = param*x.

(poly, param, gf)

    return [0 if i & 1 else gf.sqr(poly[i // 2]) for i in range(2 * len(poly) - 1)]

def poly_tracemod(poly, param, gf):
    """Compute y + y^2 + y^4 + ... + y^(2^(field_size-1)) mod poly, where y = param*x."""
    out = [0, param]
    for _ in range(gf.field_size - 1):
        # In each loop iteration i, we start with out = y + y^2 + ... + y^(2^i). By squaring that we
        # transform it into out = y^2 + y^4 + ... + y^(2^(i+1)).
        out = poly_sqr(out, gf)
        # Thus, we just need to add y again to it to get out = y + ... + y^(2^(i+1)).
        while len(out) < 2:
            out.append(0)
        out[1] = param
        # Finally take a modulus to keep the intermediary polynomials small.
        _, out = poly_divmod(out, poly, gf)
    return out

def poly_frobeniusmod(poly, gf):
    """Compute x^(2^field_size) mod poly."""