undo_modulo_multiplication.py

#!/usr/bin/env python

"""
Given the result of a multiplication and one of the factors, calculate the 
other factor

Arguments:
known_factor = the factor we're given
result = the result of the multiplication modulo some number
size_of_modulo_result = The number of bits in the result
Returns:
(missing_factor, size_in_bits)
"""
def undo_modulo_multiplication(known_factor, modulo_result, size_of_modulo_result):
    missing_factor = ''

    # Step 1: Shift the known_factor until the multiplier is odd
    # Apart from the rightmost 0 bits, each bit of the 'modulo_result' can give us one bit of the missing factor.
    right_shifts = 0
    while modulo_result % 2 == 0:
        modulo_result = modulo_result//2
        right_shifts += 1
    
    number_of_bits = size_of_modulo_result - right_shifts
    
    # Next repeatedly examine the rightmost bit of the result
    for i in xrange(number_of_bits):
        rightmost_result_bit = modulo_result % 2
        if rightmost_result_bit == 1:
            missing_factor = '1' + missing_factor
        else:
            missing_factor = '0' + missing_factor
        # Subtract the effect from this digit
        modulo_result -= rightmost_result_bit * known_factor
        modulo_result = modulo_result // 2

    # Now we have the (size_of_modulo_result - right_shifts) rightmost bits of the missing factor
    return missing_factor, number_of_bits

# Sample from https://jazzy.id.au/default/2010/09/21/cracking_random_number_generators_part_2.html
known_factor = int('10111011110111011001110011001101101', 2)
modulo_result = int('111110100011', 2)
size_of_modulo_result = len('111110100011')

missing_factor, size_in_bits = undo_modulo_multiplication(known_factor=known_factor, modulo_result=modulo_result, size_of_modulo_result=size_of_modulo_result)
print 'The last %d bits of the missing factor are: %s' % (size_in_bits, missing_factor)