Hlavní navigace

Názor k článku Vlastimil Klíma: Zcela nový koncept hašovacích funkcí od anonym - Problém P/NP jsem v diskusi ani v článku...

Článek je starý, nové názory již nelze přidávat.

  • 13. 11. 2006 13:33

    bez přezdívky
    Problém P/NP jsem v diskusi ani v článku nezmínil, nevyužívám je. Když už se ale do toho pustili jiní diskutující, proč se jich nezeptáte?

    Já bych nebyl proti, kdyby se ukázalo, že pro konkrétní instanci hašovací funkce je problém nalezení její kolize NP-úplný problém. Nedokazuje to nic, dává to jen lepší reference, :-)
    A to z důvodu, který sám uvádíte pomocí symbolu O(1.000000001^n).

    Teorie složitosti rozděluje problémy do tříd. V každé třídě jsou problémy přibližně (řádově) stejně složité. Jejich složitost se uvádí jako funkce jejich rozměru, parametru. Třeba u hašovací funkce je parametrem n počet bitů hašovacího kódu. Zatím známe algoritmy, které umí nalézt vzor (resp.kolizi) k zadané haši se složitostí 2^n (resp.2^(n/2)). To je exponenciální složitost (nikoli lineární...). Proto tento problém nemůže patřit do třídy P, kde mají algoritmy složitost nejvýše polynomiální vzhledem k n, tj. třeba n^3 apod.

    Jedna z nesložitějších tříd problémů je třída NP-úplných problémů. Nikdo se nebude zlobit, když jeho kryptografické konstrukce budou odpovídat problémům z této třídy. Na druhé straně se tomu nepřikládá takový praktický význam, právě z důvodu, který uvádíte. Přikládá se tomu ale význam teoretický.

    Pokud vás zajímají definice, například v on-line příručce na str. 57 - 63, http://www.cacr.math.uwaterloo.ca/hac/about/chap2.pdf