Törmäys

Tarkastellaan vielä aiemman tehtävän hajautusfunktiota:

$$(c_0 A^{n-1} + c_1 A^{n-2} \cdots + c_{n-1} A^0) \bmod M$$

Parametrit ovat samat kuin aiemmin eli $A=23$ ja $M=2^{32}$.

Toteuta tiedostoon collision.py funktio find_other, jolle annetaan parametrina merkkijono. Funktion tulee palauttaa jokin toinen merkkijono, jolla on sama hajautusarvo.

Funktiolle annettava merkkijono muodostuu merkeistä a-z ja siinä on enintään $100$ merkkiä. Funktion tulee palauttaa merkkijono, joka täyttää samat vaatimukset.

Funktion tulee toimia tehokkaasti ja palauttaa toinen merkkijono välittömästi.

def hash_value(string):
    # voit lisätä tämän funktion aiemmasta tehtävästä testaamista varten

def find_other(string):
    # TODO

if __name__ == "__main__":
    string1 = "kissa"
    string2 = find_other("kissa")
    print(string1, hash_value(string1)) # kissa 2905682
    print(string2, hash_value(string2)) # zfgjynuk 2905682

Yllä olevassa koodissa on esimerkki siitä, miten funktio find_other voisi toimia. Kun toteutat funktion itse, sen ei kuitenkaan tarvitse palauttaa juuri merkkijonoa zfgjynuk vaan minkä tahansa vaatimusten mukaisen merkkijonon, jonka hajautusarvo on oikea.