Взломать хеш
На некоторых соревнованиях по программированию решения соперников можно взламывать: прислать тест, на котором чужое решение ошибается. Вы читаете решение соперника и видите, что строки в нём сравниваются полиномиальным хешем: основание b записано в коде, модуль M — тоже. Иногда модуля нет вовсе, и хеш просто переполняет 64-битное беззнаковое число, то есть M = 2⁶⁴.
Хеш строки s из букв s₀s₁…sL−1 считается так:
h = 0
for c in s:
h = (h * b + ord(c)) mod M
где ord — код буквы в ASCII: у a — 97, у z — 122. Постройте две разные строки с одинаковым хешем.
Вход
Одна строка: два числа b и M. Модуль M — либо 18446744073709551616 (то есть 2⁶⁴), либо простое число, не большее 2³¹ − 1. Основание: 1 ≤ b < M.
Выход
Две строки из строчных латинских букв a–z длиной от 1 до 2048 каждая. Строки должны различаться, а их хеши по модулю M — совпадать. Длины могут быть разными. Подойдёт любой такой ответ.
Примеры
Пример 1
131 18446744073709551616
abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababba baababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaab
Пример 2
31 1000000007
pkoqhrtlal wbmbhveana
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 13 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Два случая устроены совсем по-разному. Начните с простого модуля около миллиарда: сколько случайных строк нужно перебрать, чтобы у двух из них совпал хеш? Вспомните задачу о днях рождения.
2Подсказка 2
Для 2⁶⁴ перебор безнадёжен: нужно около 2³² строк. Зато 2⁶⁴ — не простое. Если основание чётное, что происходит с b⁶⁴ по модулю 2⁶⁴? А если нечётное — посмотрите на строки Туэ — Морса: a и b, затем ab и ba, abba и baab, каждая следующая — склейка двух предыдущих.
3Подсказка 3
Хеш склейки XY равен h(X) · b|Y| + h(Y). Выразите разность хешей Sk и Tk через разность для k − 1 и посчитайте, сколько раз в ней двойка.
4Идея
Три случая. Простой модуль M ≤ 2³¹ − 1: хеши случайных строк ведут себя как случайные числа, и среди k строк совпадение вероятнее отсутствия уже при k ≈ 1,18 √M — не больше шестидесяти тысяч строк. 2⁶⁴ и чётное основание: b⁶⁴ делится на 2⁶⁴, и всё, что стоит левее последних 64 букв, из хеша пропадает. 2⁶⁴ и нечётное основание: строки Туэ — Морса из 1024 букв.
5Разбор
Простой модуль. Генерируем случайные строки из десяти букв, считаем хеши и кладём их в словарь, пока какой-нибудь хеш не встретится второй раз у другой строки. При M = 2³¹ − 1 в среднем хватает около шестидесяти тысяч строк, при 10⁹ + 7 — около сорока тысяч.
2⁶⁴, чётное основание. Строки «a» и «b», к каждой приписано 64 буквы z. Первая буква входит в хеш с множителем b⁶⁴, а он делится на 2⁶⁴, потому что в b есть хотя бы одна двойка.
2⁶⁴, нечётное основание. S₀ = a, T₀ = b, Sk+1 = SkTk, Tk+1 = TkSk. Для разности Dk = h(Sk) − h(Tk) получается Dk+1 = Dk(b2k − 1), и D₀ = −1. Множитель b − 1 чётный, b² − 1 делится на 8, а каждый следующий — на 2 хотя бы на раз больше предыдущего. Всего двоек не меньше 1 + 3 + 4 + … + 11 = 64 при k = 10. Строки из 1024 букв, ответ не зависит от основания.
5+Решение
6Сложность
Для простого модуля — O(√M) строк по десять букв и столько же памяти под словарь: в худшем тесте около шестидесяти тысяч. Для 2⁶⁴ — O(1): ответ один на все нечётные основания и один на все чётные.
7Типичные ошибки
- Перебор и для 2⁶⁴. Задача о днях рождения требует около 1,18 · 2³² ≈ 5 · 10⁹ строк. За отведённое время перебор не успевает и печатает две строки с разными хешами.
- Одна и та же строка дважды. Совпадение хеша в словаре проверяют для разных строк: случайный генератор может выдать одну строку повторно.
- Буквы вне a–z. Строки Туэ — Морса удобно строить из 0 и 1 — замените их буквами a и b, это только сдвигает коды, разность хешей та же.
- Хеш по модулю 2⁶⁴ в Python. Числа в Python не переполняются: если проверяете ответ у себя, берите остаток явно,
% 2**64.