Вычисление хеш-функции (коэффициенты степени 1000+) и коллизии

[FasterHarder]

Всем хай! Сходу к делу!

Есть такая хеш-функция h(s) = (s1 * b^(n-1) + s2 * b^(n-2) + ... + s(n-1) * b + sn) mod K
s - строка символов, соот-но s1 - 1ый символ строки (s[0]), s2- 2ой символ строки (s[1]) и т.д. sn - последний символ строки.

В целом проблем нет с нахождением этого полинома, например, по схеме Горнера, если бы не одно НО(!), коэффициент b = 1300, K = 105 908 104

Тип данных double терпит где-то порядок 10^300, ну, грубо если
Самый мощный тип целочисленный С++ (например) где-то 10^17, ну, грубо если
Для вещественных чисел в том же С++ не определена ариф.операция % (возможно, есть какие-то спец.функции типа modf, fmod и пр.).

Как победить здесь переполнение (в идеале для long int, чтобы была возможность взять %), например, если подается входная строка из 5000 символов??
Вроде есть такое, что (A + B) mod C = ( (A mod C) + (B mod C) ) mod C, может это как-то поможет здесь, не знаю
---------------------------------------

2 момент. Нужно найти 2 различные строки, для которых заданная хеш-функция вернет одинаковый хеш, т е H(s1) = H(s2).
Кроме перебора ничего не вижу. Подскажите, как обнаружить коллизию не используя перебор хаотичный.

Подскажите как быть-то? Буду признателен

[Akina]

Цитата FasterHarder @ 20.02.22, 04:38

b = 1300, K = 105 908 104

Меньше куба - так что предел = 1300 * 105908104 = 137680535200 ~ 2^37, bigint/long за глаза.
А считать - с заду наперёд, и сразу по модулю.

[FasterHarder]

Цитата Akina @ 20.02.22, 12:58

сразу по модулю.

я уже понял, что здесь вся фишка в вычислении возведения степень по модулю. Тогда и переполнения нет и длинная арифметика не нужна, одни плюсы)

[OpenGL]

Цитата FasterHarder @ 20.02.22, 04:38

Нужно найти 2 различные строки, для которых заданная хеш-функция вернет одинаковый хеш, т е H(s1) = H(s2).

Это эквивалентно задаче "найти строку, хеш которой равен нулю, а коды её символов - небольшие числа". Тогда, прибавив к любой строке эту строку (под прибавлением понимается суммирование кодов символов, стоящих в соответствующих позициях), мы получим две разные строки с одним хешем.
Наверняка эта задача как-то относительно легко решается, но я не знаю стандартного метода для неё.