hashmultiplier.py

from __future__ import print_function, division

from sage.all import ZZ, Mod, Matrix
from sage.modules.free_module_integer import IntegerLattice

ZZx = ZZ['x']


def hex(n):
    return "0x" + ZZ(n).str(16)


def algdep_padic(alpha, n, q):
    alpha = Mod(alpha, q)
    M = Matrix(n + 2, 1, [ZZ(alpha**i) for i in range(n+1)] + [q])
    K = M.left_kernel()
    L = IntegerLattice([b[:n+1] for b in K.basis()])
    pol = ZZx(list(L.shortest_vector()))
    if pol.leading_coefficient() < 0:
        return -pol
    else:
        return pol


def optimize(alpha0, fixedbits, bits, maxdeg):
    print("*** Optimizing for {} bits ending with {} ***".format(bits, hex(alpha0)))

    q = 2**bits

    maxnorms = {}

    for deg in range(1, maxdeg+1):
        maxnorm = 0
        for alpha in range(alpha0, q, 2**fixedbits):
            pol = algdep_padic(alpha, deg, q)
            N = sum(c*c for c in pol)
            if N >= maxnorm:
                maxnorm = N
        maxnorms[deg] = maxnorm
        print("deg {} max norm = {}".format(deg, maxnorm))
    print("")

    bestfrac = 0.5
    bestalpha = 0
    for alpha in range(alpha0, q, 2**fixedbits):
        frac = 1.0
        L = []
        for deg in range(1, maxdeg+1):
            pol = algdep_padic(alpha, deg, q)
            N = sum(c*c for c in pol)
            frac = min(frac, float(N / maxnorms[deg]))
            if frac < bestfrac:
                break
            L.append(N)
        else:
            bestfrac = frac
            bestalpha = alpha
            print("{}: norms={} frac={}".format(hex(alpha), L, bestfrac))
    print("")

    return bestalpha


alpha = 0xb
prevbits = 4

for (bits, deg) in [(16, 6), (32, 12), (48, 18), (64, 24)]:
    alpha = optimize(alpha, prevbits, bits, deg)

    print("Optimal polynomials:")
    for deg in range(1, deg+1):
        pol = algdep_padic(alpha, deg, 2**bits)
        print(pol)
    prevbits = bits
    print("")