<SYSTEM_TASK:>
Solve the following problem using Python, implementing the functions described below, one line at a time
<END_TASK>
<USER_TASK:>
Description:
 def compute_canonical_key_ids(self, search_amplifier=100):
 """ A canonical key id is the lowest integer key id that maps to a particular shard. The mapping to canonical key ids depends on the number of shards. Returns a dictionary mapping from shard number to canonical key id. This method will throw an exception if it fails to compute all of the canonical key ids. """

        canonical_keys = {}
        num_shards = self.num_shards()
        # Guarantees enough to find all keys without running forever
        num_iterations = (num_shards**2) * search_amplifier
        for key_id in range(1, num_iterations):
            shard_num = self.get_shard_num_by_key(str(key_id))
            if shard_num in canonical_keys:
                continue
            canonical_keys[shard_num] = str(key_id)
            if len(canonical_keys) == num_shards:
                break

        if len(canonical_keys) != num_shards:
            raise ValueError("Failed to compute enough keys. " +
                             "Wanted %d, got %d (search_amp=%d).".format(
                                 num_shards, len(canonical_keys),
                                 search_amplifier))

        return canonical_keys