Полиномиальное хеширование строк: как выбрать основание и модуль, чтобы не словить коллизию?

Хеш строки — это значение многочлена h = Σ s[i] * base^i mod M. Правила выбора:

1. База должна быть больше размера алфавита и взаимно проста с модулем. Для строчных латинских base = 131 или 137 (а не 31 — слишком мала, выше шанс коллизий на коротких алфавитах). Лучше брать случайную базу в диапазоне, скажем, [256, M) при старте программы — это ломает заранее заготовленные анти-хеш тесты.

2. Модуль — большое простое. 1e9+7 работает, но при сравнении ~10^5 подстрок вероятность коллизии по парадоксу дней рождения уже заметна (~q^2 / M). Поэтому либо двойное хеширование (два разных модуля), либо один модуль 2^61 - 1 (Mersenne) — он почти 2^61, и одиночная коллизия крайне маловероятна.

const uint64_t M = (1ULL << 61) - 1;          // простое Мерсенна
uint64_t base;                                 // выбрать случайно при старте

uint64_t mulmod(uint64_t a, uint64_t b) {      // умножение по mod 2^61-1
    __uint128_t c = ( __uint128_t)a * b;
    uint64_t lo = (uint64_t)(c & M), hi = (uint64_t)(c >> 61);
    uint64_t r = lo + hi;
    return r >= M ? r - M : r;
}

Препроцессинг префиксных хешей — O(n), сравнение любой пары подстрок потом — O(1).