Я наверное тупой
Но я быстро не могу придумать ответ на такой вопрос (в связи с этим):

Есть число N, есть A_{i, 0<=i< k} случайных целых чисел, в диапазоне [0..N). k <= \sqrt{N}.
Находится наименьшее p, такое что не существует i,j из [0..k), таких что
i/=j & A_i mod p = A_j mod p

(хэш-функцию без конфликтов)

Что можно сказать о ожидаемой величине p?

Понятно, что p = N всегда подходит.