Function poly_sqr

src/minisketch/tests/pyminisketch.py:228–236

Return the square of polynomial poly.

(poly, gf)

    return a

def poly_sqr(poly, gf):
    """Return the square of polynomial poly."""
    if len(poly) == 0:
        return []
    # In characteristic-2 fields, thanks to Frobenius' endomorphism ((a + b)^2 = a^2 + b^2),
    # squaring a polynomial is easy: square all the coefficients and interleave with zeroes.
    # E.g., (3 + 5*x + 17*x^2)^2 = 3^2 + (5*x)^2 + (17*x^2)^2.
    # See https://en.wikipedia.org/wiki/Frobenius_endomorphism.
    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."""