# Prove that Horner's method produce only 6 collisions on 50000 English words

Polynomial for producing hash values:

$$p(z)=a_0+a_1z+\cdots, a_{n-1}z^{n-1}$$

Honor's method for that polynomial:

$$p_0(z)=a_{n-1} \\ p_i(z)=a_{n-i-1}+zp_{i-1}(z), (i=1, \cdots, n-1)\\$$

Problem: For 50,000 English words and for $$z=33$$, we would get at most 6 collisions. So, how we can prove that please? Also, to calculate the hash using Honor's method, we split the key into a fixed length of size 8 bits, 16 bits or 32 bits, etc. Why we do this split for the key please?

• You probably mean “Horner”. Aug 26, 2021 at 15:59
• The number of collisions depends on the words. Perhaps it’s 6 collisions in expectation. The expected number of collisions depends on the length of the hash. Under the simplifying assumption that hashes are random, the expected number of collisions for $n$ words and $b$ bits is roughly $n^2/2^{b+1}$. Aug 26, 2021 at 16:02
• Also, I personally don’t split keys. If someone else is, you should ask them why they do it. Aug 26, 2021 at 16:03