Исследование хэш-функций

Для оптимизации коммутации пакетов используется специальная таблица коммутации, которая содержит соответствие номера порта, MAC-адреса и номера VLAN-а. Так как быстродействующая память стоит очень дорого, вместо исходных значений в таблице хранится хэш от MAC+VLAN.

В данном задании предлагается проверить, какова вероятность коллизий, то есть совпадения значения хэш-функции для различных исходных данных.

Нужно исследовать любую из хэш-функции: CRC32 или PJW-hash

Хэш считается от MAC-адреса либо от комбинации MAC+VLAN

Например для MAC = 00-12-34-FA-DC-33 (6 байт) значение CRC32 0xFEA517B4 (4272232372 в десятичной системе)

Необходимо найти коллизию - два разных MAC-адреса, дающих в результате один и тот же хэш.

Считается, что функция PJW даёт больше коллизий, чем CRC32, но стоит проверить это экспериментально.

Приложите исходный код программы, которая получает на вход MAC-адрес, считает для него хэш-функцию и выполняет перебор MAC-адресов в поисках коллизий. Так как перебор значений занимает много времени, оцените производительность своей программы (количество комбинаций в секунду).

Стоит предусмотреть выбор диапазона перебора для того, чтобы можно было запустить программу параллельно на нескольких компьютерах.

Решение нужно представить для любой из хэш-функций.