lazyhash

scratch_4.py

from functools import partial
from hashlib import md5
from timeit import timeit


def int2pmat(number, side=35):
    """Convert number into permutation matrix.

    Pads to side. If None, no padding.

    Parameters
    ----------
    number
    side

    Returns
    -------

    """
    available = list(range(side))
    mat = []
    for i in range(side, 0, -1):
        number, r = divmod(number, i)
        mat.append(available.pop(r))
    mat.extend(available)
    return mat


def pmat2int(matrix):
    """Convert permutation matrix to number.

    Parameters
    ----------
    matrix

    Returns
    -------

    """
    radix = len(matrix)
    available = list(range(radix))
    i = 1
    res = 0
    for row in matrix:
        idx = available.index(row)
        del available[idx]
        res += idx * i
        i *= radix
        radix -= 1
    return res


def pmat_mult(a, b):
    """Multiply two permutation matrices (of the same size?).

    Parameters
    ----------
    a
        list of positive integers plus zero
    b
        list of positive integers plus zero

    Returns
    -------

    """
    return [b[-row - 1] for row in a]


def lazyhash(msg: bytes):
    """Algebraic hash function: incremental/decremental, associative etc.
    Provide all non-abelian group niceties over permutation matrix multiplication."""
    r = reversed(range(35))
    for b in msg:
        r = pmat_mult(r, int2pmat(b))  # HINT: a byte is just an int for Python.
    return pmat2int(r)


txt = b'asd'*40
t = timeit(partial(lazyhash, txt), number=10000)
h = lazyhash(b'asd')
print(1000000* t / 10000, 'us       <- lazyhash')

t = timeit(lambda:md5(txt), number=10000)
print(1000000* t / 10000, 'us       <- MD5')