An algorithm has to store several keys generated by an adversary in a hash…

Concept: A hash function h maps keys to one of m slots; a collision happens when two distinct keys land in the same slot. If h is a single FIXED, publicly known function (e.g. a chosen division or multiplication rule), an adversary who supplies the keys can reverse-engineer that rule and pick keys that are guaranteed to collide. Universal hashing avoids this by drawing h uniformly at random, at run time, from a family H that satisfies Pr[h(x) = h(y)] ≤ 1/m for every pair of distinct keys x ≠ y — a bound that holds no matter which keys were chosen, because the adversary cannot know in advance which h will be drawn.

Applying it to this question:

1. With k > m keys chosen by the adversary and a fixed division rule h(k) = k mod m, the adversary can pick k keys that are all congruent modulo m, sending every one of them into the same slot — a guaranteed worst-case chain of length k.

2. The multiplication rule is still a single deterministic function once its constant is fixed, so an adversary who knows that constant can invert the arithmetic and construct the same kind of colliding key set; it spreads a random workload well but gives no guarantee against an adversarial one.

3. Choosing between the division and multiplication rule based on whether k is prime still commits to one fixed deterministic rule at a time, so it inherits the exact same weakness — primality of k has no bearing on collision resistance against an adversary.

4. Universal hashing draws h from H at random, independent of how the adversary chose the keys. By the guarantee above, for ANY two of the k keys the collision probability is at most 1/m, so the expected number of colliding pairs across all k keys is at most k(k-1)/(2m), and the expected number of OTHER keys landing in any one key's slot is at most (k-1)/m — exactly the same bound you would get from a uniformly random set of keys. In other words, universal hashing guarantees the adversary can do no better than random chance, regardless of which keys are chosen; it does not make the load factor k/m disappear, but it removes the adversary's ability to force a WORSE-than-random outcome.

Cross-check: this matches the classical result (CLRS-style analysis): under universal hashing every key's expected number of colliding keys is O(1 + k/m) — the SAME order as under a fully random hash function — regardless of which keys the adversary submits. Fixed deterministic hash functions are exactly what real-world algorithmic-complexity (hash-flooding) attacks exploit, which is why production systems adopted randomized/keyed hashing (e.g. SipHash) for this reason.

Therefore, universal hashing — picking the hash function at random from a family with the 1/m pairwise-collision guarantee — is the only one of the four strategies that provably prevents an adversary from doing worse to us than a random set of keys would.