A collision experiment related to https://mailmanlists.org/pipermail/dlc-dev/2021-March/000065.html

collisions.raku

sub MAIN(Int \m, Int \n, Int :$samples = 10_000) {
    my \q = 2 ** 19 - 1;
    my \m-n =  m ** n;

    # experiment should be done over a prime field so that it mirrors reality
    say "q = {q} (is-prime: {q.is-prime})";
    say "samples = {$samples}, m = {m}, n = {n}, m ^ n = {m-n}";

    sub count-collisions(@table) {
        # This line of code:
        # 1. creates the cartesian product of the columns
        # 2. sums each of the products
        # 3. removes each duplicate sum
        # 4. subtract number of non-duplicate sums from m^n
        m-n - ([X+] @table).unique.elems;
    }

    # the random oracle samples 0..q
    my &H = -> *@ { (^q).roll };

    my @hash-trails;
    my @half-hash-trails;
    my @uniform-trails;
    for ^$samples {
        # hash
        {
            my @table = (^n).map: -> \i { (^m).map: -> \j { H(i,j) } };
            @hash-trails.push: count-collisions(@table);
        }

        # half hash
        {
            my @table = (^n).map: -> \i {
                my \h = H(i);
                (^m).map( -> \j { (j * h) mod q })
            };
            @half-hash-trails.push: count-collisions(@table);
        }
        # uniform
        @uniform-trails.push: m-n - (^m-n).map({ H() }).unique.elems;
    }


    say "     uniform hash half-hash";
    say "----------------------";
    say "max: { @uniform-trails.max } { @hash-trails.max } { @half-hash-trails.max }";
    say "min: { @uniform-trails.min } { @hash-trails.min } { @half-hash-trails.min }";
    say "avg: { @uniform-trails.sum / $samples } { @hash-trails.sum / $samples } { @half-hash-trails.sum / $samples }";
    say "med: { median(@uniform-trails) } { median(@hash-trails) } { median(@half-hash-trails) }"
}

sub median(@list) {
    @list.sort[(*-1) div 2, * div 2].sum / 2
}