#!/usr/bin/env python3
import random, math

def ceil_binlog(x):
    return math.ceil(math.log(x, 2))

# just multiplication
def mul(x_in, y):
    x = x_in
    z = 0
    for i in range(ceil_binlog(y)):

        if (y >> i) & 1:
            z=z+x

        x = x << 1

    assert z==x_in*y # self-test
    return z

# multiplication modulo $m$
# another version: \url{https://en.wikipedia.org/wiki/Modular_arithmetic#Example_implementations}
def mul_mod(x_in, y_in, m):
    # hack/kludge. not practical. but for demonstration. keep initial x and y mod m:
    x = x_in % m
    y = y_in % m
    z = 0
    for i in range(ceil_binlog(y)):

        if (y >> i) & 1:
            # be sure z and x mod m
            assert z<m and x<m
            z=z+x # <- 'core' operation

        x = x << 1

        # if x overflown, keep it mod m
        if x > m:
            x = x - m
        assert x<m # be sure...

        # same for z
        if z > m:
            z = z - m
        assert z<m # be sure...

    assert z==(x_in*y_in) % m # self-test
    return z