What you describe with composite numbers would not work: data structures like IBLTs make sense when you want to store a small set S from a large universe U, and

What you describe with composite numbers would not work: data structures like IBLTs make sense when you want to store a small set S from a large universe U, and you want to use a number of bits that is linear in S and sublinear in U. In your example, just storing the static lookup table with one prime number for each key in the universe costs about |U| log |U| bits. Furthermore, each cell needs to store a product of these numbers, and even if you can bound with k the number of keys colliding in the same cell, you need k log |U| bits for each cell. This is very inefficient, and if you think about it you can achieve the same functionality with a standard hash table, which takes less space. In general, every time you think "I could use prime factorization to store sets", there is usually a more efficient solution, probably involving bitvectors. The usage scenario of IBLTs is quite different from the usual scenario of storing key-value mappings: it is useful when you have an algorithm that adds and delete keys, and at any time during the execution of the algorithm the number of distinct keys can be arbitrarily large, but you know that at the end of the algorithm the number of distinct keys is "small". With a standard hash table, you would need a space that is proportional to the maximum number of distinct elements reached during the execution of the algorithm; with IBLTs you only need space that is proportional to the final set size. A toy example is the following: someone tells you a set of n numbers, and then tells you again all the numbers in the set except for k; you want to return the k missing numbers. With a hash table you would need O(n) space, with a IBLT you just need O(k). To achieve this, they use a standard trick in Bloom-like data structures (and perfect hashes, etc.): the property that there is always a cell with exactly one element; this property is preserved when you remove that one element, so there will be another cell with exactly one element, and so on, until you can retrieve all of them. This property is guaranteed with random hash functions with the right table size, and can be proved by showing that the hypergraph induced by the hash mappings is "peelable", which is a generalization of a standard graph with no cycles, i.e. a tree: in a tree there is always a node with degree 1, and when you remove that you leave at least another node with degree 1, and so on.