Skip to content

Instantly share code, notes, and snippets.

@LLFourn

LLFourn/collisions.raku

Created April 6, 2021 05:58
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save LLFourn/e6d7c1ad0b970fc6bcd642b25ad9a760 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save LLFourn/e6d7c1ad0b970fc6bcd642b25ad9a760 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. LLFourn created this gist Apr 6, 2021.
    54 changes: 54 additions & 0 deletions collisions.raku
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,54 @@
    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
    }