bit_deltas.sage

# The idea is to track the current value of the kernel, and update it according to
#     kernel *= (1 + delta_i' y_i) / (1 - delta_i' y_i),
# which we verify with the constraint
#     kernel(g x) * (1 - delta_i(g x) y_i) = kernel(x) * (1 + delta_i(g x) y_i),
# where delta_i is a succinctly evaluable polynomial defined by bit_delta(i, n) below.

p = 2^31 - 2^27 + 1
F = GF(p)
g = F.multiplicative_generator()
R.<t> = F[]

# The "canonical" generator of order n.
def generator(n):
    assert g.multiplicative_order() % n == 0
    return g^(g.multiplicative_order() / n)

# The "canonical" subgroup of order n.
def subgroup(n):
    g_n = generator(n)
    return [g_n^i for i in range(n)]

# Selects the i'th element of the "canonical" subgroup of order n.
# This is normalized, so it returns 1 on the selected point, 0 on others.
def lagrange_selector(i, n):
    g = generator(n)
    unnormalized = (t^n - 1) / (t - g^i)
    weight = 1 / product(g^i - g^j for j in range(n) if j != i) # could be precomputed
    return weight * unnormalized

# Returns a polynomial encoding the delta for the i'th bit, i.e. bit_i minus its previous value.
# We treat the least significant bit as having index 0.
def bit_delta(i, n):
    half_cycle_len = 2^i
    cycle_len = 2 * half_cycle_len
    num_cycles = n / cycle_len
    switched_on = lagrange_selector(half_cycle_len, cycle_len)
    switched_off = lagrange_selector(0, cycle_len)
    pattern = switched_on - switched_off
    return pattern(t^num_cycles) # repeat the pattern

# Converts p - 1 to -1, just for brevity.
def to_signed(delta):
    if delta == p - 1:
        return -1
    else:
        return delta

if __name__ == '__main__':
    bits = 5
    n = 2^bits
    for i in range(bits):
        print('bit {} deltas: {}'.format(i, [to_signed(bit_delta(i, n)(x)) for x in subgroup(n)]))