gagannagpal68's blog

How to break this hash function on arrays?
By gagannagpal68, history, 5 years ago, In English

My hash has 3 fields

f1 = size of interval

f2 = sum of array elements over interval(a[i] +a[i+1]...a[j])

f2 = sum of squares of array elements over interval(a[i]^2 + a[i+1]^2 .. a[j]^2).

if all 3 matches, then elements are indeed same. Can this be broken?

P.S. While in attempt to solve D from previous contest(https://mirror.codeforces.com/contest/1284/problem/D). I was looking for this question.

  • Vote: I like it
  • -25
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by gagannagpal68 (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

(5, 12, 10) and (6, 8, 13) have the same hash.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    I think adding a cube power may make this hash a perfect hash.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Sorry to disappoint you, but probably not. It can be shown by a simple Dirichlet. There are a lot more arrays of size 1000 than there are possible outputs for your hash if you bound the numbers by let's say 1000.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        On a contest, lets say we choose 3 random powers.

        I guess that would be optimistically a good hash?

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It will be perfect only if you consider at least $$$n$$$ distinct powers.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Adding powers up to k can easily be hacked with a test with n=2^(k+2).

      → Reply